Coste mínimo en un tablero P75734


Statement
 

pdf   zip

thehtml

Considerad un tablero n × m, donde cada casilla contiene el coste de pasar por ella. Tenéis que comenzar en la fila de arriba (0) y acabar en la fila de abajo (n−1) con el mínimo coste posible, haciendo siempre movimientos que incrementen la fila donde os encontráis. En general, sólo podéis moveros a casillas adyacentes (verticalmente o en diagonal), con una excepción: podéis hacer un máximo de k saltos de un caballo de ajedrez (siempre hacia abajo, hasta cuatro opciones posibles).

Entrada

La entrada consiste en varios casos, sólo con números naturales. Cada caso empieza con n, m y k, seguidas de n filas con m costes. Suponed que n y m están entre 1 y 100, que k está entre 0 y 100, y que los costes están entre 0 y 104.

Salida

Para cada caso, escribid el mínimo coste de ir desde la fila de arriba hasta la fila de abajo haciendo como máximo k saltos de caballo. Podéis comenzar y acabar en las columnas que queráis.

Public test cases
  • Input

    3 4 1
    10 12 14 16
    70 60 50 40
    99 33 50 23
    
    1 1 3
    42
    
    4 7 3
    0 9 9 9 9 9 1
    9 9 9 9 1 9 1
    9 9 1 9 9 9 9
    9 9 9 1 9 9 9
    

    Output

    37
    42
    3
    
  • Information
    Author
    Salvador Roura
    Language
    Spanish
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++