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.05 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	2

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

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ță.

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 și K. 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 ≤ K ≤ 100
• 1 ≤ M, N ≤ 500
• Atenție! Continentul poate fi format dintr-o singură țară

Exemplu

Explicație

...