Page 9 - MATINF Nr.2

Concursul de Informatic˘a Programming Day 9

Clasa a X-a

Problema 1 – accesibil
ˆ
Intr-un sat de form˘a dreptunghiular˘a, cu dimensiunile n × m, exist˘a mai multe terenuri. Un
teren reprezint˘a o zon˘a format˘a din parcele de dimensiune 1×1 vecine pe orizontal˘a sau vertical˘a
(ˆıntre oricare dou˘a parcele exist˘a un drum format din deplas˘ari pe orizontal˘a s , i/sau vertical˘a
care s˘a treac˘a numai prin acel teren).

Fiecare teren este reprezentat pe hart˘a printr-un num˘ar natural, mai exact fiecare parcel˘a
apart , inˆand terenului este marcat˘a prin num˘arul respectiv. Deoarece administrat , iei locale nu-i
plac numerele mari, aceasta a decis c˘a pot exista mai multe terenuri identificate prin acelas , i
num˘ar, cu condit , ia ca aceste terenuri s˘a nu fie vecine (s˘a nu aib˘a parcele vecine pe orizontal˘a
sau pe vertical˘a), astfel ˆıncˆat s˘a nu existe nicio confuzie.

Unele terenuri sunt pozit , ionate bine, altele mai put , in bine. Fiecare locuitor ˆıs , i dores , te s˘a
poat˘a s˘a ajung˘a din exteriorul satului la terenul s˘au, f˘ar˘a a trece peste terenul altui locuitor,
adic˘a s˘a existe un drum de la orice parcel˘a a terenului s˘au la una din cele patru margini ale
satului, drum care s˘a treac˘a numai prin parcele ale terenului s˘au. Un astfel de teren se numes , te
accesibil s , i este visul fiec˘arui locuitor.

Cerint , ˘a
Dˆandu-se harta satului, sub forma unei matrice n × m ce cont , ine pe fiecare pozit , ie cˆate un
num˘ar de identificare, s˘a se determine:

1. num˘arul de terenuri din sat;
2. num˘arul de terenuri accesibile.

Date de intrare

Fis , ierul de intrare accesibil.in cont , ine pe prima linie un num˘ar natural p. Pentru toate
testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe a doua linie se afl˘a numerele n s , i m separate printr-un spat , iu.

Pe urm˘atoarele n linii se afl˘a cˆate m numere descriind harta satului.

Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire accesibil.out se va scrie un singur num˘ar natural repre-
zentˆand num˘arul de terenuri din sat.
Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire accesibil.out se va scrie un singur num˘ar natural repre-
zentˆand num˘arul de terenuri accesibile.

Restrict , ii s , i preciz˘ari

1. 3 ≤ n, m ≤ 1000
2. 0 ≤ valorile de pe hart˘a ≤ 100
3. Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 50% din punctaj