Caminos en una matriz (con programación dinámica)
Los caminos desde el extremo superior izquierdo (posición (1,1)) hasta el extremo inferior derecho (posición (3,4)) en la matriz
|
1 2 3 |
( 1 6 11 2 ) ( 7 12 3 8 ) ( 3 8 4 9 ) |
moviéndose en cada paso una casilla hacia la derecha o abajo, son los siguientes:
|
1 2 3 4 5 6 7 8 9 10 |
[1,6,11,2,8,9] [1,6,11,3,8,9] [1,6,12,3,8,9] [1,7,12,3,8,9] [1,6,11,3,4,9] [1,6,12,3,4,9] [1,7,12,3,4,9] [1,6,12,8,4,9] [1,7,12,8,4,9] [1,7, 3,8,4,9] |
Definir la función
|
1 |
caminos :: Matrix Int -> [[Int]] |
tal que caminos m es la lista de los caminos en la matriz m desde extremo superior izquierdo hasta el extremo inferior derecho, moviéndose en cada paso una casilla hacia la derecha o abajo. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> caminos (fromLists [[1,6,11,2],[7,12,3,8],[3,8,4,9]]) [[1,6,11,2,8,9], [1,6,11,3,8,9], [1,6,12,3,8,9], [1,7,12,3,8,9], [1,6,11,3,4,9], [1,6,12,3,4,9], [1,7,12,3,4,9], [1,6,12,8,4,9], [1,7,12,8,4,9], [1,7, 3,8,4,9]] λ> length (caminos (fromList 12 12 [1..])) 705432 |
Read More «Caminos en una matriz (con programación dinámica)»