Számlabirintus

Adott egy számlabirintus, amelyet egy 0 és 9 közé eső számokat tartalmazó kétdimenziós tömbként reprezentálunk, ahogy az alábbi ábrán látható. A labirintust egymásra merőleges irányokban (azaz észak, dél, kelet és nyugat felé) haladva járhatjuk be. Ha az egyes mezőket költségértékeknek tekintjük, érdekes kihívás lehet annak a legkisebb költségnek a meghatározása, amennyivel eljuthatunk a labirintus egy adott belépési pontjától egy adott kilépési pontjáig.

A feladatod, hogy meghatározd azt a legkisebb költséget, amennyivel eljuthatunk egy N × M-es számlabirintus bal felső sarkából a jobb alsó sarkáig, ahol 1 ≤ N, M ≤ 999. A fent látható példában a megoldás 24.

A bemenet specifikációja

A bemenet számos labirintust tartalmaz. Az első sorban egy pozitív egész szám áll, amely a labirintusok számát adja meg. Az egyes labirintusokat a következőképpen definiáljuk: az első sor a labirintus sorainak a számát (N), a második sor a labirintus oszlopainak a számát (M) adja meg, a következő N sor pedig a labirintus egyes sorait írja le, amelyekben az egyes számok egy-egy szóközzel vannak elválasztva egymástól.

A kimenet specifikációja

Minden labirintusra egyetlen sort kell a kimenetre írni, amely a keresett legkisebb költséget tartalmazza.

Példa bemenet

1. 2
2. 4
3. 5
4. 0 3 1 2 9
5. 7 3 4 9 9
6. 1 7 5 5 3
7. 2 3 4 2 5
8. 1
9. 6
10. 0 1 2 3 4 5

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 24
2. 15

letöltés szöveges állományként