Probabil că toți cunoașteți povestea "Albă ca Zăpada și cei șapte pitici".
Ceea ce nu știți este că, într-o zi, când piticii lucrau în mină a avut loc un cutremur și toate puțurile care coborau în mină au fost distruse.
Albă ca Zăpada, văzând că piticii nu au ajuns seara acasă s-a hotărât să meargă să-i caute.
Ajungând la mină, și-a dat seama că nu se putea coborî și nu știa cum să-i scoată pe pitici cât mai repede de acolo deoarece trecuse ceva timp.
A găsit o hartă a minei pe care erau marcate zonele unde lucrau piticii și o mașină de săpat puțuri verticale.
Presupunând că niciuna dintre aceste zone nu a fost distrusă de cutremur, Albă ca Zăpada a hotărât să sape puțuri pentru a-i elibera pe pitici.
Ajutați-o pe Albă ca Zăpada să determine o modalitate de a săpa puțuri de lungime minimă pentru a-i scoate pe pitici din mină.
Fișierul de intrare DWARFS.IN conține pe prima linie două numere naturale M și N separate printr-un spațiu care reprezintă dimensiunile hărții.
Pe fiecare dintre următoarele M linii se află un șir de N numere care pot fi 0 sau 1 și care nu sunt separate prin spații. Cifra 1 indică faptul că pe hartă, acea celulă este acoperită de pământ, iar cifra 0 indică faptul că acea celulă nu este acoperită. O zonă în care se pot afla pitici este formată din celule adiacente pe verticală sau orizontală care au valoarea 0 pe hartă. Pe hartă, în locul puțurilor a fost trecută valoarea 1, deoarece acestea au fost distruse.
Fișierul de ieșire DWARFS.OUT trebuie să conțină un singur număr natural L care reprezintă suma lungimilor tuturor puțurilor săpate. Această sumă trebuie să fie cât mai mică posibil.
DWARFS.IN
8 10 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 DWARFS.OUT 5
În continuare este reprezentată harta care conține caracterul '*' în locurile în care s-au săpat puțuri.
Deci, lungimea minimă este egală cu numărul de celule marcate cu '*'.
1 1 * 1 1 * 1 1 1 1 1 1 0 1 1 * 1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 * 1 1 1 1 * 1 0 1 1 0 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
|