Caminando entre Montañas
La ciudad de Byteotia tiene un relieve muy colorido y en casi cualquier lugar de la ciudad se puede encontrar un mapa especificando cualquier terreno. Sorprendentemente, los mapas siempre tienen dimensiones \(N×N\) . Estos mapas se describen en una cuadrícula donde la altura de cualquier punto ( A[i][j] ). Shadow, el sheriff de la ciudad se ha topado con uno de estos mapas y quiere saber la cantidad mínima de calorías que cualquiera podría perder desde el punto al siempre viajando hacia adelante o hacia abajo con longitud . La casilla se encuentra en la esquina superior izquierda. Él sabe que uno puede perder muchas calorías cuando se avanza de un punto más bajo a otro más alto, igual a la diferencia de alturas de estos dos lugares. Al pasar de un punto más alto a uno más bajo o igual no se pierden calorías. ¿Puedes ayudar a Shadow a encontrar el camino?
Entrada
La primera línea tiene un número , que indica las dimensiones del mapa. Luego, siguen líneas con exactamente dígitos, que representan el mapa. Finalmente una línea con el punto final .
Salida
Un número que indica la cantidad mínima de calorías a perder durante el mejor camino.
Ejemplo de Entrada
3
756
458
924
3 3
Ejemplo de Salida
2
Comments