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 alee.in 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 alee.out 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

alee.inalee.out
8 6
2 7
3 3
4 6
5 4
7 3
7 5
1 1 8 8
15

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 sunt marcati copacii, cu _ zonele libere, iar cu O dalele aleii).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content