Cost mínim en un tauler P75734


Statement
 

pdf   zip

thehtml

Considereu un tauler n × m, on cada casella conté el cost de passar-hi. Heu de començar a la fila de dalt (0) i acabar a la fila de baix (n−1) amb el mínim cost possible, fent sempre moviments que incrementin la fila on us trobeu. En general, només us podeu moure a caselles adjacents (verticalment o en diagonal), amb una excepció: teniu dret a fer un màxim de k salts de cavall dels escacs (sempre cap avall, fins a quatre opcions possibles).

Entrada

L’entrada consisteix en diversos casos, només amb nombres naturals. Cada cas comença amb n, m i k, seguides d’n files amb m costs. Suposeu que n i m estan entre 1 i 100, que k està entre 0 i 100, i que els costs estan entre 0 i 104.

Sortida

Per a cada cas, escriviu el mínim cost d’anar des de la fila de dalt fins a la fila de baix fent com a màxim k salts de cavall. Podeu començar i acabar a les columnes que vulgueu.

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
    Catalan
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++