Fișierul intrare/ieșire | tari.in, tari.out | Sursă | Curs IQ Academy |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Teodor Plop • teodor94 |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
Țări
Avem un continent reprezentat printr-o hartă dreptunghiulară (matrice) cu M linii și N coloane. Celulele din matrice au valori 0 sau 1, unde 0 reprezintă că celula este în teritoriul unei țări, iar 1 reprezintă celulă de graniță. Se poate circula dintr-o celulă într-o altă celulă adiacentă în una din cele 4 direcții: (N, S, E, V).
Să se elimine exact 1 celulă de graniță astfel încât numărul de țări rămase să fie cât mai mic. Să se afișeze acest număr.
Date de intrare
Fișierul de intrare tari.in conține pe prima linie numerele naturale M, N. Urmează M linii care conțin câte N caractere fiecare, 0 sau 1, având semnificația din enunț.
Date de ieșire
În fișierul de ieșire tari.out conține un singur număr natural, reprezentând numărul minim de țări după eliminarea unei celule de tip graniță.
Restricții
- 1 ≤ M, N ≤ 500
- Atenție! Continentul poate fi format dintr-o singură țară
- Pe continent există cel puțin o celulă aparținând teritoriului unei țări
Exemple
tari.in | tari.out | Explicații |
---|---|---|
5 5 01010 00100 10111 01100 01100 |
3 |
Pe continent sunt inițial 5 țări. Eliminând celula de graniță de pe poziția (2, 3) (rândul al doilea, coloana a treia), se vor uni trei țări diferite într-una singură. Deci din cele 5 țări inițiale, rămânem cu 3. |
5 5 00000 11110 00000 01111 00000 |
1 |
Pe continent există o singură țară. Indiferent ce bucată de graniță alegem să eliminăm, numărul țărilor rămâne același. |