Caminando entre Montañas


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Swift, VB

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\) (1 \leq N \leq 10). Estos mapas se describen en una cuadrícula donde la altura de cualquier punto (0 \leq A[i][j] \leq 9). 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 [1,1] al [x, y] siempre viajando hacia adelante o hacia abajo con longitud 1. La casilla [1,1] 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 N, que indica las dimensiones del mapa. Luego, siguen N líneas con exactamente N dígitos, que representan el mapa. Finalmente una línea con el punto final [x, y].

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

There are no comments at the moment.