Camí en un tauler X13208

Statement

html

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 des del centre del tauler fins a qualsevol casella de la perifèria.

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 del centre del tauler fins a qualsevol casella de la vora 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
Other languages: English
Official solutions: C++
User solutions: C++