Camí en un tauler P30895
Considereu un tauler n × n, amb n senar. Des de cada casella, ens podem moure a qualsevol de les (com a molt) quatre caselles adjacents horitzontalment o verticalment. Cada casella té un cert cost positiu que cal pagar quan s’hi passa. Calculeu el cost mínim d’anar de qualsevol casella de la perifèria fins al centre del tauler.
Entrada
L’entrada consisteix en diversos casos, cadascun amb n, seguida d’una matriu n × n. Podeu suposar que n és un nombre senar entre 1 i 499, i que tots els costs són nombres enters entre 1 i 1000.
Sortida
Per a cada cas, escriviu el cost mínim d’anar des de la perifèria fins al centre del tauler.
Public test cases
Input
1 42 3 1 2 3 4 5 6 7 8 9 9 999 1 999 999 999 999 999 999 999 999 2 999 6 5 4 3 2 999 999 3 999 7 999 999 999 1 999 999 4 999 8 999 999 999 9 999 999 5 999 9 1 999 999 8 999 999 6 999 999 999 999 999 7 999 999 7 999 999 999 999 999 6 999 999 8 9 1 2 3 4 5 999 999 999 999 999 999 999 999 999 999
Output
42 7 136
Information
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++ Python
- User solutions
- C++ Python