Nac093 El Estadio de Futbol Prob 3 del IX concurso nacional de la OMI
Historia
Como buen mexicano, Karel es un aficionado al fútbol. Al llegar a Morelia se ha enterado que el estadio de fútbol se
encuentra en la cima del Cerro Quinceo.
Desgraciadamente, Karel no conoce el camino a dicho cerro, por lo que tu deberás escribir un
programa que le ayude a encontrarlo.
Problema
Deberás escribir un programa que le permita a Karel llegar al punto más alto del Cerro Quinceo desde su posición inicial.
Consideraciones
Karel se encuentra en el origen mirando al norte.
En el mundo de entrada se representa un mapa del Cerro de Quinceo como un rectángulo (puede que el largo del cerro sea diferente a su ancho) cuya esquina inferior izquierda esta en la posición (1,1).
En cada casilla de dicho rectángulo hay al menos un beeper, el número de beepers en cada casilla indica la altura del cerro en ese punto.
La altura máxima en cualquier punto del cerro no sobrepasará los 99 beepers.
Si Karel se sitúa en el extremo oeste del mapa, sin importar la fila, podrá avanzar hacia el este y la altura ira siempre creciendo hasta llegar a una altura máxima de esa fila, a partir de ese punto si se sigue avanzando hacia el este la altura ira siempre decreciendo.
De igual manera sucede con las columnas, si Karel se sitúa en el extremo sur del mapa, sin importar la columna, podrá avanzar al norte, la altura ira siempre creciendo hasta encontrar una fila con altura máxima, a partir de ese momento si se sigue avanzando hacia el norte, los valores de altura irán siempre decreciendo.
El mapa cuenta además con la singularidad de que todas las columnas tienen su máxima altura en la misma fila, al igual que todas las filas tienen su máximo en la misma columna.
Para la evaluación de este problema únicamente importa la posición final de Karel, no importa su orientación ni los beepers del mapa.