Fişierul intrare/ieşire:	lacuri.in, lacuri.out	Sursă	ONI 2007, clasa 9
Autor	Dan Grigoriu	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.125 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Lacuri

Pe un teren de formă pătrată sunt zone de uscat şi lacuri. Harta terenului este memorată într-un tablou bidimensional n*n cu valori 1 (apă) sau 0 (uscat). Liniile sunt numerotate de la 1 la n, de sus în jos şi coloanele de la 1 la n, de la stânga la dreapta. Fiecare lac este înconjurat de o suprafaţă de teren uscat. Excepţie fac doar lacurile situate la marginea terenului care sunt înconjurate de uscat doar prin interiorul terenului nu şi prin afara acestuia.

Cerinta

Se doreşte să se traverseze terenul pe uscat, de la poziţia (1,1) la poziţia (n,n), pe un drum de lungime minimă, mergând pas cu pas. La un pas, se ajunge de la un pătrăţel la altul învecinat cu el spre nord, est, sud sau vest.
Să se scrie un program care:

1. Determină numărul lacurilor care sunt de formă pătrată şi în acelaşi timp sunt „pline de 1”.
2. În cazul în care toate lacurile sunt de formă pătrată şi în acelaşi timp „pline de 1”, determinaţi un drum cu proprietatea de mai sus.

Date de intrare

Fişierul de intrare lacuri.in are pe prima linie numărul n, iar pe următoarele n linii este harta terenului (fiecare linie are n valori 0 sau 1, separate de câte un spaţiu).

Date de iesire

Fişierul de ieşire lacuri.out va conţine:

• pe prima linie: numărul de lacuri ce sunt de formă pătrată ÅŸi în acelaÅŸi timp „pline de 1”;
• în cazul în care toate lacurile sunt de formă pătrată ÅŸi în acelaÅŸi timp „pline de 1”, urmează liniile ce descriu drumul de lungime minimă ales. Fiecare linie din fiÅŸier conÅ£ine câte o pereche de coordonate ale poziÅ£iilor succesive prin care trece drumul (linia ÅŸi coloana, separate cu un spaÅ£iu), începând cu (1,1) ÅŸi terminând cu (n,n).

Restrictii

• 2 ≤ n ≤ 100
• PoziÅ£iile (1,1) ÅŸi (n,n) sunt sigur libere (cu valoarea 0).
• Dacă există mai multe soluÅ£ii se va afiÅŸa oricare dintre ele.
• Pot fi cel mult 100 de lacuri ÅŸi cel puÅ£in unul; dacă un lac este de formă pătrată, atunci 1 ≤ latura ≤ n-1.
• Indiferent de forma lor, lacurile sunt sigur „izolate”, adică nu se „ating” deloc de alt lac. * De exemplu, dacă un lac conÅ£ine poziÅ£ia (3,3), atunci un alt lac nu poate conÅ£ine vreuna din poziÅ£iile învecinate cu (3,3), adică: (2,3), (2,4), (3,4), (4,4), (4,3), (4,2), (3,2) ÅŸi (2,2).
  Pentru cerinţa a) se acordă 30% din punctaj, iar pentru cerinţa b) se acordă 70% din punctaj.

Exemplu

Explicatie

1. Prima linie conţine 4 (sunt 4 lacuri de formă pătrată şi „pline de 1”)
2. Deoarece toate cele 4 lacuri sunt de formă pătrată şi „pline de 1”, se scrie şi drumul ales: de la (1,1), (1,2), (1,3), (2,3), (3,3), ...., (6,6).

1. Dacă în poziţia (3,5) ar fi fost un 0, atunci lacul cu latura 3 nu ar mai fi fost „plin de 1” şi atunci prima linie ar fi conţinut doar valoarea 3 (ar fi fost doar 3 lacuri pătrate şi „pline de 1”).
2. În exemplul iniţial, dacă în poziţia (6,1) ar fi fost valorea 0, atunci nu ar fi fost toate lacurile pătrate (cel din stânga-jos nu ar fi fost pătrat) şi s-ar fi afişat doar un 3 în fişierul de ieşire.
3. În exemplul iniţial, dacă în poziţia (5,2) ar fi fost valoarea 0, atunci s-ar fi afişat doar un 3, pentru că lacul din stânga-jos nu ar fi un lac pătrat şi „plin de 1”.

Cum se trimit solutii?