Caminos en una retícula (con programación dinámica)
Se considera una retícula con sus posiciones numeradas, desde el vértice superior izquierdo, hacia la derecha y hacia abajo. Por ejemplo, la retícula de dimensión 3×4 se numera como sigue:
|
1 2 3 4 5 |
|-------+-------+-------+-------| | (1,1) | (1,2) | (1,3) | (1,4) | | (2,1) | (2,2) | (2,3) | (2,4) | | (3,1) | (3,2) | (3,3) | (3,4) | |-------+-------+-------+-------| |
Definir la función
|
1 |
caminos :: (Int,Int) -> [[(Int,Int)]] |
tal que caminos (m,n) es la lista de los caminos en la retícula de dimensión mxn desde (1,1) hasta (m,n). Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
λ> caminos (2,3) [[(1,1),(1,2),(1,3),(2,3)], [(1,1),(1,2),(2,2),(2,3)], [(1,1),(2,1),(2,2),(2,3)]] λ> mapM_ print (caminos (3,4)) [(1,1),(1,2),(1,3),(1,4),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(2,4),(3,4)] [(1,1),(1,2),(2,2),(2,3),(2,4),(3,4)] [(1,1),(2,1),(2,2),(2,3),(2,4),(3,4)] [(1,1),(1,2),(1,3),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(2,3),(3,3),(3,4)] [(1,1),(2,1),(2,2),(2,3),(3,3),(3,4)] [(1,1),(1,2),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(2,2),(3,2),(3,3),(3,4)] [(1,1),(2,1),(3,1),(3,2),(3,3),(3,4)] |
Read More «Caminos en una retícula (con programación dinámica)»