Cargando el móvil
La dependencia que tenemos con los móviles nos hace cargarlos todas las noches hasta el nivel máximo de la batería para no correr el riesgo de quedarnos sin él a mitad del día siguiente. Hay incluso gente que cuando durante el día ve un enchufe libre lo pone a cargar por lo que pueda pasar.
Yo soy uno de ellos.
Con los años he ido refinando mi técnica para no cargar la batería al máximo todas las noches. Con mis rutinas repetitivas perfectamente conocidas, tengo claro en qué momentos del día voy a poder hacer esas recargas parciales (y en cuántas unidades se incrementará la carga) y lo que me baja el nivel de batería entre cada una. Con esos datos, todas las noches calculo el nivel mínimo de batería con el que tengo que salir de casa al día siguiente para que éste nunca baje de mi umbral auto-impuesto de dos unidades.
Lo que aún no he conseguido dominar es ese mismo cálculo cuando salgo de la rutina establecida y tengo varias alternativas para hacer las cosas. Me sucede por ejemplo los días en los que estoy en ruta a otra ciudad a la que puedo llegar de distintas formas.
En mi primera aproximación al problema estoy suponiendo que quiero desplazarme por un "tablero de ajedrez", desde la esquina superior izquierda a la esquina inferior derecha. En cada "celda" o bien puedo cargar el móvil una cantidad concreta o bien no puedo y su nivel de carga desciende. Teniendo en cuenta que quiero ir por un camino que atraviese el mínimo número de celdas posible, ¿cuál es la carga mínima con la que tengo que salir para que el móvil nunca baje de esas dos unidades de carga?
Entrada
La entrada esta compuesta por distintos casos de prueba.
Cada caso de prueba comienza con una línea que contiene dos números: el número C de columnas y el número F de filas del tablero (ninguno de ellos supera las 100 unidades).
A continuación aparecen F líneas, una por cada fila. Cada una de ellas contiene C números, indicando la variación del nivel de carga que sufre el móvil al pasar por cada casilla de esa fila. Un número positivo indica cuánto puedo cargar en ella el móvil antes de tener que seguir mi camino, mientras que uno negativo indica que no hay enchufes y que la batería del móvil desciende su nivel de carga en esa cantidad. Se garantiza que las cantidades en las celdas origen y destino (esquina superior izquierda e inferior derecha) son siempre 0 y que los valores del resto no superan (en valor absoluto) 106.
Salida
Por cada caso de prueba se escribirá una línea con un único número: el nivel de batería con el que hay que salir para garantizar que podré llegar desde la esquina origen a la destino por el camino más corto que seleccionemos sin que el nivel de carga baje nunca de 2 unidades.
Entrada de ejemplo
5 1 0 -1 -1 -1 0 5 1 0 1 -1 -1 0 5 1 0 -1 -1 1 0 2 2 0 -3 -5 0
Salida de ejemplo
5 3 4 5