Caminos en una retícula

El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.

Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.
C

Para representar los caminos se definen los siguientes tipos de datos:

Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].

Definir las funciones

tales que

  • (caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

  • (nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

Soluciones

7 Comentarios

  1. Mediante búsqueda en espacios de estados (muy parecida a la de fracruzam):

Escribe tu solución