== include(page="template/taskheader" task_id="lacuri") ==
Pe un teren de forma patrata sunt zone de uscat si lacuri. Harta terenului este memorata intr-un tablou bidimensional n*n cu valori 1 (apa) sau 0 (uscat). Liniile sunt numerotate de la 1 la n, de sus in jos si coloanele de la 1 la n, de la stanga la dreapta. Fiecare lac este inconjurat de o suprafata de teren uscat. Exceptie fac doar lacurile situate la marginea terenului care sunt inconjurate de uscat doar prin interiorul terenului nu si prin afara acestuia.
Pe un teren de forma patrata sunt zone de uscat si lacuri. Harta terenului este memorata intr-un tablou bidimensional $n*n$ cu valori $1$ (apa) sau $0$ (uscat). Liniile sunt numerotate de la $1$ la {$n$}, de sus in jos si coloanele de la $1$ la {$n$}, de la stanga la dreapta. Fiecare lac este inconjurat de o suprafata de teren uscat. Exceptie fac doar lacurile situate la marginea terenului care sunt inconjurate de uscat doar prin interiorul terenului nu si prin afara acestuia.
h2. Cerinta
Se doreste sa se traverseze terenul pe uscat, de la pozitia (1,1) la pozitia (n,n), pe un drum de lungime minima, mergând pas cu pas. La un pas, se ajunge de la un patratel la altul invecinat cu el spre nord, est, sud sau vest.
Se doreste sa se traverseze terenul pe uscat, de la pozitia ({$1,1$}) la pozitia ({$n,n$}), pe un drum de lungime minima, mergand pas cu pas. La un pas, se ajunge de la un patratel la altul invecinat cu el spre nord, est, sud sau vest.
Sa se scrie un program care:
# Determina numarul lacurilor care sunt de forma patrata si in acelasi timp sunt pline de 1.
# In cazul in care toate lacurile sunt de forma patrata si in acelasi timp pline de 1, determinati un drum cu proprietatea de mai sus.
# Determina numarul lacurilor care sunt de forma patrata si in acelasi timp sunt pline de {$1$}.
# In cazul in care toate lacurile sunt de forma patrata si in acelasi timp pline de {$1$}, determinati un drum cu proprietatea de mai sus.
h2. Date de intrare
Fisierul de intrare lacuri.in are pe prima linie numarul n, iar pe urmatoarele n linii este harta terenului (fiecare linie are n valori 0 sau 1, separate de cate un spatiu).
Fisierul de intrare $lacuri.in$ are pe prima linie numarul {$n$}, iar pe urmatoarele $n$ linii este harta terenului (fiecare linie are $n$ valori $0$ sau {$1$}, separate de cate un spatiu).
h2. Date de iesire
Fisierul de iesire lacuri.out va contine:
Fisierul de iesire $lacuri.out$ va contine:
* pe prima linie: numarul de lacuri ce sunt de forma patrata si in acelasi timp pline de 1;
* in cazul in care toate lacurile sunt de forma patrata si in acelasi timp pline de 1, urmeaza liniile ce descriu drumul de lungime minima ales. Fiecare linie din fisier contine cate o pereche de coordonate ale pozitiilor succesive prin care trece drumul (linia si coloana, separate cu un spatiu), incepand cu (1,1) si terminand cu (n,n).
* pe prima linie: numarul de lacuri ce sunt de forma patrata si in acelasi timp pline de {$1$};
* in cazul in care toate lacurile sunt de forma patrata si in acelasi timp pline de {$1$}, urmeaza liniile ce descriu drumul de lungime minima ales. Fiecare linie din fisier contine cate o pereche de coordonate ale pozitiilor succesive prin care trece drumul (linia si coloana, separate cu un spatiu), incepand cu ({$1,1$}) si terminand cu ({$n,n$}).
h2. Restrictii
* 2 ≤ n ≤ 100
* Pozitiile (1,1) si (n,n) sunt sigur libere (cu valoarea 0).
* $2 ≤ n ≤ 100$
* In pozitiile ({$1,1$}) si ({$n,n$}) este uscat (valoarea {$0$}).
* Daca exista mai multe solutii se va afisa oricare dintre ele.
* Pot fi cel mult 100 de lacuri si cel putin unul; daca un lac este de forma patrata, atunci 1 ≤ latura ≤ n-1.
* Indiferent de forma lor, lacurile sunt sigur izolate, adic nu se ating deloc de alt lac. De exemplu, daca un lac contine pozitia (3,3), atunci un alt lac nu poate contine vreuna din pozitiile invecinate cu (3,3), adica: (2,3), (2,4), (3,4), (4,4), (4,3), (4,2), (3,2) si (2,2).
Pentru cerinta 1 se acorda 30% din punctaj, iar pentru cerinta 2 se acorda 70% din punctaj.
* Pot fi cel mult $100$ de lacuri si cel putin unul; daca un lac este de forma patrata, atunci {$1 ≤ latura ≤ n-1$}.
* Indiferent de forma lor, lacurile sunt sigur izolate, adica nu se ating deloc de alt lac. De exemplu, daca un lac contine pozitia ({$3,3$}), atunci un alt lac nu poate contine vreuna din pozitiile invecinate cu ({$3,3$}), adica: ({$2,3$}), ({$2,4$}), ({$3,4$}), ({$4,4$}), ({$4,3$}), ({$4,2$}), ({$3,2$}) si ({$2,2$}).
* Pentru cerinta $1$ se acorda $30%$ din punctaj, iar pentru cerinta $2$ se acorda $70%$ din punctaj.
h2. Exemplu
table(example). |_. lacuri.in |_. lacuri.out |_. Explicatie |
table(example). |_. lacuri.in |_. lacuri.out |
| 6
0 0 0 0 0 0
0 1 0 1 1 1
h3. Explicatie
# Prima linie contine 4 (sunt 4 lacuri de forma patrata si pline de 1)
# Deoarece toate cele 4 lacuri sunt de forma patrata si pline de 1, se scrie si drumul ales: de la (1,1), (1,2), (1,3), (2,3), (3,3), ...., (6,6).
# Prima linie contine $4$ (sunt $4$ lacuri de forma patrata si pline de {$1$})
# Deoarece toate cele $4$ lacuri sunt de forma patrata si pline de {$1$}, se scrie si drumul ales: de la ({$1,1$}), ({$1,2$}), ({$1,3$}), ({$2,3$}), ({$3,3$}), ...., ({$6,6$}).
h3. Observatii
# Daca in pozitia (3,5) ar fi fost un 0, atunci lacul cu latura 3 nu ar mai fi fost plin de 1 si atunci prima linie ar fi continut doar valoarea 3 (ar fi fost doar 3 lacuri patrate si pline de 1).
# In exemplul initial, daca in pozitia (6,1) ar fi fost valorea 0, atunci nu ar fi fost toate lacurile patrate (cel din stanga-jos nu ar fi fost patrat) si s-ar fi afisat doar un 3 in fisierul de iesire.
# In exemplul initial, daca in pozitia (5,2) ar fi fost valoarea 0, atunci s-ar fi afisat doar un 3, pentru ca lacul din stanga-jos nu ar fi un lac patrat si plin de 1.
# Daca in pozitia ({$3,5$}) ar fi fost un {$0$}, atunci lacul cu latura $3$ nu ar mai fi fost plin de $1$ si atunci prima linie ar fi continut doar valoarea $3$ (ar fi fost doar $3$ lacuri patrate si pline de {$1$}).
# In exemplul initial, daca in pozitia ({$6,1$}) ar fi fost valorea {$0$}, atunci nu ar fi fost toate lacurile patrate (cel din stanga-jos nu ar fi fost patrat) si s-ar fi afisat doar un $3$ in fisierul de iesire.
# In exemplul initial, daca in pozitia ({$5,2$}) ar fi fost valoarea {$0$}, atunci s-ar fi afisat doar un {$3$}, pentru ca lacul din stanga-jos nu ar fi un lac patrat si plin de {$1$}.
== include(page="template/taskfooter" task_id="lacuri") ==
== SmfTopic(topic_id="...") ==
