Ski P84876


Statement
 

pdf   zip

thehtml

De repente, el ski se ha puesto de moda en Barcelona. Aprovechando las nevadas recientes, la gente se dedica a buscar una calle (nevada) con suficiente pendiente y se lanza esquiando desde arriba del todo, con el objetivo de llegar a la parte de abajo de la calle tan rápidamente como sea posible. ¡Ayúdales a encontrar el mejor camino!

La calle es una cuadrícula de N filas de M columnas. Por cada casilla se da el tiempo (en décimas) que se tarda en atravesarla. El esquiador empieza en cualquier casilla de la primera fila, y únicamente puede desplazarse hacia abajo, en línea recta (la casilla inmediatamente inferior a la que ocupa) o en diagonal (la que queda a la izquierda o a la derecha de la anterior casilla). Cada desplazamiento en diagonal penaliza con una décima adicional. El esquiador no puede salir de la cuadrícula.

Entrada

Una secuencia de casos de prueba. Cada caso de pruebas está formado por dos números N, M>0 separados por un espacio, y N líneas de M dígitos (0-9) cada una con los tiempos (en décimas) que tarda el esquiador en cruzar la casilla. Dos casos de prueba se separarán por una línea en blanco.

Salida

Una única línea por cada caso de pruebas, con el mínimo número de décimas necesario para realizar todo el descenso.

Puntuación

  • TestA:  ‍ Una entrada con 100 casos de prueba con N,M<10.  ‍40 Puntos ‍
  • TestB:  ‍ Una entrada con 10 casos de prueba con N,M<500.  ‍60 Puntos ‍
Public test cases
  • Input

    1 9
    876545678
    
    5 2
    82
    46
    00
    49
    36
    
    3 4
    1119
    9560
    0022
    
    5 5
    00009
    01099
    90999
    99099
    99909

    Output

    4
    14
    4
    3
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++