Fișierul intrare/ieșire tari.in, tari.out Sursă Curs IQ Academy
Autor autor necunoscut Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.1 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii