Copiado al portapapeles
Descripción
Ruben esta muy feliz, acaba de retirar mucho dinero del banco, él estaba caminando en direccion a su casa, de pronto se dio cuenta que varios ladrones le estan siguiendo, entonces Ruben se asusto y empezo a correr, pero Ruben no se dio cuenta que las calles tienen forma de laberinto, asi que como estaba asustado choco con varias paredes, finalmente los ladrones lograron su objetivo, golpearon a Ruben y se escaparon con todo el dinero.
Ruben el proximo mes debe volver a retirar dinero del banco, como él ya no quiere ser asaltado y llegar a casa lastimado, te pide que encuentres todos los caminos posibles para llegar a su casa saliendo el banco, como puede haber varios caminos de la misma longitud te pide que listes los caminos ordenados lexicograficamente.
Se te proporcionara un tablero $A$ de $n$ filas y $m$ columnas, cada casilla $A_{ij}$, solo contendra valores $1$ y $0, 1$ representa una pared en el laberinto, $0$ representa un espacio libre para caminar, como Ruben quiere llegar a casa lo mas antes posible solo puede moverse hacia abajo $(A)$ y hacia la derecha $(D)$.
El banco se encuentra en la posicion $A_{11}$, y la casa de Ruben se encuentra en la posicion $A_{nm}$, se garantiza que estas dos posiciones estaran inicialmente con $0$.
La cadena $s = s_1s_2s_3...s_n$ es lexicograficamente menor a $t = t_1t_2t_3...t_m$, si $n < m$ y $s_1 = t_1, s_2 = t_2, s_3 = t_3, ... , s_n = t_n$ o existe un número $p$ tal que $ p \leq min(n, m)$ y $s_1 = t_1, s_2 = t_2, ... ,s_{p - 1} = t_{p - 1}$ y $s_p < t_p$. Por ejemplo, $"aaa"$ es es menor lexicograficamente a $"aaaa"$, $"abb"$ es menor lexicograficamente a $"abc"$.
Entrada
La entrada tiene dos números enteros $n, m (1 \leq n, m \leq 10)$.
Luego vienen $n$ lineas, cada linea tiene $m$ enteros, donde $A_{ij} \in \{0, 1\}$
Salida
Debe listar todos los caminos posibles para salir del laberinto, ordenados lexicograficamente de menor a mayor. Cada camino debe estar de la siguiente manera:
path number: $i$, $i$ denota el camino $i$ - ésimo.
Todo el tablero debe estar encerrado por el caracter $'*'$.
El tablero $i$ - ésimo solo contendra caracteres $'.'$ y $'\#'$, donde $'.'$ denota la ruta a seguir para salir del laberinto, las demas casillas deben estar con $'\#'$.
Si no existe ningun camino debe imprimir "NO HAY POSIBILIDAD DE SALIR DEL LABERINTO".
Para mas detalles vea el siguiente ejemplo.
Ejemplo Entrada
3 3 0 0 0 0 1 0 0 0 0
Ejemplo Salida
path number: 1 ***** *.##* *.##* *...* ***** path number: 2 ***** *...* *##.* *##.* *****
Ayuda
Si trasamos los dos caminos anteriores siguiendo direcciones.
El camino $1$ sigue las siguientes direcciones $AADD$.
El camino $2$ sigue las siguientes direcciones $DDAA$.