Problema 1
Piedras
piedras.pas, piedras.c, piedras.cpp
Dorothy, desesperada por el lento caminar de sus grandes amigos, el hombre de paja, el León y el Señor de hoja de Lata, se adelanto dejando en cada paso una piedrita más que en su paso anterior. Oz les brindó a sus amigos un mapa indicando la cantidad de piedras que puso Dorothy en su camino, pero son bastante atolondrados y no lo entienden. Por lo cual se te pide que hagas una lista de las coordenadas que deben seguir, para encontrar a la pequeña niña.
Problema
|
Dado un mapa con la cantidad de piedras en cada cuadrante, debes encontrar el camino de longitud máxima que tenga primero 0 piedras, luego 1 piedra, luego 2 piedras, etc. Hasta que ya no puedas continuar. Puedes pasar de una celda a otra solamente si tienen una arista en común. En la figura de la izquierda sólo se puede recorrer el camino hasta siete piedras, ya que la casilla que tiene 7 y 8 no son adyacentes. |
Entrada
El primer renglón tiene dos enteros, la cantidad de renglones m y la cantidad de columnas n (0 < m, n ≤ 170) del mapa. Después siguen m renglones con n enteros en cada uno.
Salida
Deberá haber tantos renglones como la longitud máxima del camino. En cada renglón deberás de poner la coordenadas de cada casilla en el orden en que se recorre. La coordenada debe tener primero el renglón y luego la columna. El camino es único.
Ejemplo
| entrada | salida |
| 4 5 13 2 3 9 8 0 1 4 7 10 15 12 5 6 11 16 18 17 19 20 |
2 1 2 2 1 2 1 3 2 3 3 3 3 4 2 4 |
| Concurso: | ICPC - 6 Concurso Interno de la Universidad Bonaterra. 26/Mayo/2006 |
| Propuesto por: | Óscar Dávalos Orozco |
| Ayuda: | entradas, salidas, sugerencias |
| Soluciones: | piedras.pas, piedras.c, piedras.cpp |