Fișierul intrare/ieșire	insule.in, insule.out	Sursă	OJI 2009 clasa a 10-a
Autor	Nistor-Eugen Moț	Adăugată de	Coman Mara • Mstar_Angel
Timp de execuție pe test	0.1 sec	Limită de memorie	2048 KB
Scorul tău	N/A	Dificultate	1

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Insule ( clasa a 10-a )

Arhipelagul RGB este format din insule care aparțin țărilor R, G și B. Putem reprezenta harta arhipelagului ca o matrice cu n linii și m coloane cu elemente din mulțimea {0, 1, 2, 3}. Un element egal cu 0 reprezintă o zonă acoperită de apă; un element egal cu 1 reprezintă o zonă de pământ aparținând unei insule din țara R, iar un element egal cu 2 reprezintă o zonă de pământ aparținând unei insule din țara G, iar un element egal cu 3 reprezintă o zonă de pământ aparținând unei insule din țara B.
Se consideră că două elemente ale matricei sunt vecine dacă ele au aceeași valoare și fie sunt consecutive pe linie, fie sunt consecutive pe coloană. Două elemente aparțin aceleiași insule dacă ele sunt vecine sau dacă se poate ajunge de la un element la celălalt pe un drum de-a lungul căruia oricare două elemente consecutive sunt vecine.
Pentru a încuraja relațiile de colaborare dintre țările R și G, se dorește construirea unui pod care să unească o insulă aparținând țării R de o insulă aparținând țării G. Podul trebuie să respecte următoarele condiții:

• să înceapă pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparținând țării R;
• să se termine pe o zonă cu apă consecutivă pe linie sau coloană cu o zonă aparținând țării G;
• să traverseze numai zone acoperite cu apă;
• oricare două elemente consecutive ale podului trebuie să fie vecine;
• lungimea podului să fie minimă (lungimea podului este egală cu numărul de elemente traversate de pod).

Cerință

Dată fiind harta arhipelagului să se determine câte insule aparțin fiecărei țări, precum și lungimea minimă a unui pod care să satisfacă condițiile din enunt.

Date de intrare

Fișierul de intrare insule.in conține pe prima linie numerele naturale n și m, separate prin spațiu. Pe următoarele n linii este descrisă harta arhipelagului. Pe fiecare dintre aceste n linii sunt scrise câte m valori din mulțimea {0, 1, 2, 3}; valorile nu sunt separate prin spații.

Date de ieșire

Fișierul de ieșire insule.out va conține o singură linie pe care vor fi scrise patru numere naturale separate prin spații NR NG NB Lg, unde NR reprezintă numărul de insule aparținând țării R, NG numărul de insule aparținând țării G, NB numărul de insule aparținând țării B, iar Lg lungimea minimă a podului.

Restricții

• 1 < n, m ≤ 100
• Se garantează că pe hartă există cel puțin un element 1, un element 2 și un element 0.
• Începutul și sfârșitul podului pot să coincidă.
• Pentru datele de test există întotdeauna soluție.

Exemplu