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

13 2 3 9 8
0 1 4 7 10
15 12 5 6 11
16 18 17 19 20
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


World of πer