Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-07-09 07:49:09.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:alee.in, alee.outSursăOJI 2007, Clasa a 10-a
AutorMarinel SerbanAdăugată degabitzish1Gabriel Bitis gabitzish1
Timp execuţie pe test0.025 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Alee

Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari. Parcul are forma unui patrat cu latura de n metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in N*N zone patrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice patratice cu N linii si N coloane. Liniile si respectiv coloanele sunt numerotate de la 1 la N. Elementele matricei corespund zonelor patrate de latura 1 metru. O astfel de zona poate sa contina un copac sau este libera. Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de 1 metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta.

Cerinta

Scrieti un program care sa determine numarul minim de dale necesare pentru construirea unei alei continue de la o poarta la cealalta.

Date de intrare

Fisierul de intrare <i>alee.in</i> contine pe prima linie doua valori naturale N si M separate printr-un spatiu, reprezentand dimensiunea parcului, respectiv numarul de copaci care se gasesc in parc. Fiecare dintre urmatoarele M linii contine cate doua numere naturale X si Y separate printr-un spatiu, reprezentand pozitiile copacilor in parc (X reprezinta linia, iar Y reprezinta coloana zonei in care se afla copacul). Ultima linie a fisierului contine patru numere naturale X1 Y1 X2 Y2, separate prin cate un spatiu, reprezentand pozitiile celor doua porti (X1, Y1 reprezinta linia si respectiv coloana zonei ce contine prima poarta, iar X2, Y2 reprezinta linia si respectiv coloana zonei ce contine cea de a doua poarta).

Date de iesire

Fisierul de iesire <i>alee.out</i> va contine o singura linie pe care va fi scris un numar natural care reprezinta numarul minim de dale necesare pentru construirea aleii.

Restrictii

  • 1 ≤ N ≤ 175
  • 1 ≤ M ≤ N*N
  • Aleea este continua daca oricare doua placi consecutive au o latura comuna.
  • Aleea incepe cu zona unde se gaseste prima poarta si se termina cu zona unde se gaseste cea de a doua poarta.
  • Pozitiile portilor sunt distincte si corespund unor zone libere.
  • Pentru datele de test exista intotdeauna solutie.

Exemplu

<table class="example" cellspacing="0"><tr><th>alee.in</th><th>alee.out</th></tr><tr><td>
8 6
2 7
3 3
4 6
5 4
7 3
7 5
1 1 8 8<br />
</td><td>15</td></tr></table>

Explicatie

O modalitate de a construi aleea cu numar minim de dale este:
O O O _ _ _ _ _
_ _ O O _ _ X _
_ _ X O _ _ _ _
_ _ _ O O X _ _
_ _ _ X O _ _ _
_ _ _ _ O O _ _
_ _ X _ X O O _
_ _ _ _ _ _ O O

(cu X am marcat copacii, cu _ zonele libere, iar cu O dalele aleii).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?