Problem 3488: Medve

Cel mai scurt drum liber de urși

Să ne imaginăm un „munte” format din $n$ niveluri ( $i=1, 2, …, n$ ), unde fiecare nivel este reprezentat printr-o matrice binară $m \times m$ . În fiecare matrice, valorile de $1$ indică punctele care fac parte din munte, iar valorile de $0$ formează zonele din afara muntelui. Se știe că atât grupurile de $1$ , cât și cele de $0$ sunt conexe, considerând că două elemente sunt vecine dacă au o latură comună.

În plus, nivelurile muntelui sunt „concentrice”, în sensul că pozițiile cu $1$ de pe nivelul $i$ ( $i=2, …, n$ ) sunt acoperite de $1$ -urile de pe nivelul $i−1$ . În matricea de pe ultimul nivel există un singur $1$ , care reprezintă vârful muntelui.

Deoarece punctele din interiorul fiecărui nivel sunt considerate periculoase pentru că ar putea fi zone frecventate de urși, ne dorim să urmăm această strategie:

pornim de la orice punct de pe marginea nivelului $0$ ;
pentru fiecare nivel, traversăm de la marginea nivelului curent la marginea nivelului următor în cel mai mic număr de pași, pe ultimul nivel, ajungem la vârf;
traversarea marginilor este considerată sigură, deoarece urșii nu se apropie de ele din cauza fricii de înălțimi. În schimb, trecerea prin zonele interioare sunt considerată periculoasă.

Cerință

Determinați câți pași periculoși trebuie efectuați pentru a ajunge de la baza muntelui la vârf, urmând strategia descrisă.

Date de intrare

Prima linie a fișierului de intrare medve.in conține un număr întreg $t$ - numărul de teste.
Prima linie a fiecărui test conține două numere întregi $n$ și $m$ - numărul de niveluri și dimensiunea matricelor
Următoarele $n \cdot m$ linii conțin câte $m$ valori binare separate prin spații, reprezentând elementele matricelor.

Date de ieșire

Pentru fiecare test, scrieți pe o linie separată în medve.out numărul total de pași periculoși.

Restricții și precizări

$1 \leq t \leq 3$
$1 < n < 100$ ;
$3 < m < 100$ ;

Exemplu

medve.in

1
3 10
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 1 1 1 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

medve.out

Explicație

Exemplul de intrare constă dintr-un singur caz de test ( $t=1$ ), care reprezintă un munte format din 3 niveluri, codificat prin matrici de dimensiune $10 \times 10$ . Pe primul nivel, există un singur pas periculos pentru a ajunge la marginea nivelului 2 ( $[3,9]→[3,8]$ ). Pe nivelul 2, un alt pas periculos este necesar pentru a ajunge la poziția vârfului de pe nivelul 3 ( $[5,5]→[5,6]$ ).

Medve