Cost mínim en un tauler P75734

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 10⁴.

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.