Moldovan Mihai (mihai_moldovan) Se dă o rețea de N * M calculatoare, dispuse sub forma unei matrici cu N linii și M coloane, numerotate începând cu 1, între care se pot transfera informații.
Fiecare calculator funcțional are asociat un cod, număr natural. Calculatoarele defecte sunt marcate cu -1 și nu pot participa la transferul de informație.
Transferul de informație între două calculatoare funcționale se face direct, dacă acestea sunt vecine, sau indirect, prin intermediul altor calculatoare funcționale. Două calculatoare sunt vecine dacă se află pe aceeași linie și coloane adiacente sau pe aceeași coloană și linii adiacente, adică calculatorul de la poziția (i, j) este vecin cu cel de la pozițiile: (i + 1, j), (i - 1, j), (i, j + 1) sau (i, j - 1).
Costul transferului de informație între două calculatoare vecine funcționale este 0, dacă cele două coduri diferă prin cel mult un bit în reprezentarea binară, respectiv 1, în caz contrar. Costul transferului de informație între două calculatoare care nu sunt vecine este suma costurilor transferurilor directe intermediare.
Cerința
Scrieți un program care să determine costul minim necesar pentru transferul informației de la calculatorul de pe poziția (1, 1) la cel de pe poziția (N, M).
Date de intrare
Fișierul de intrare bitmove.in va conține pe prima linie numerele naturale N și M, cu semnificația din enunț, iar pe următoarele N linii câte M numere întregi, separate prin câte un spațiu, reprezentând codurile calculatoarelor (sau -1 pentru cele defecte).
Date de ieșire
Fișierul de ieșire bitmove.out va conține costul cerut.
Restricții și precizări
1 ≤ N, M ≤ 1500- codurile numerice ale calculatoarelor funcționale sunt numere naturale din intervalul \([1, 2^{31} – 1]\)
- se garantează că pe pozițiile
(1, 1)și(N, M)vom avea calculatoare funcționale - se garantează că există cel puțin o succesiune de calculatoare funcționale care asigură transferul informației de la poziția
(1, 1)la poziția(N, M) - pentru teste în valoare de 16 puncte,
N = 1, M > 1sauM = 1, N > 1 - pentru teste în valoare de 14 puncte, există o singură posibilitate de a ajunge de la
(1, 1)la(N, M), restul calculatoarelor fiind defecte - pentru teste în valoare de 40 puncte oricare două numere din celule adiacente diferă prin mai mult de un bit,
N * M ≤ 1.000.000 - pentru încă 15 puncte,
N * M ≤ 1.000.000
Exemplu:
bitmove.in
5 4 5 4 -1 6 1 3 2 7 -1 3 -1 -1 7 5 4 4 6 6 2 5
bitmove.out
1
Explicație
