Soluții trimise

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.

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).