Camí en un tauler P30895


Statement
 

pdf   zip

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 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++
    User solutions
    C++