Fişierul intrare/ieşire:alee.in, alee.outSursăOJI 2007 clasa a 10-a
AutorMarinel SerbanAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.1 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Alee (clasa a 10-a)

Parcul oraşului a fost neglijat mult timp, astfel că acum toate aleile sunt distruse. Prin urmare, anul acesta Primăria şi-a propus să facă reamenajări. Parcul are forma unui pătrat cu latura de n metri şi este înconjurat de un gard care are exact două porţi. Proiectanţii de la Primărie au realizat o hartă a parcului şi au trasat pe hartă un caroiaj care împarte parcul în nxn zone pătrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice pătratice cu n linii şi n coloane. Liniile şi respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor pătrate de latură 1 metru. O astfel de zonă poate să conţină un copac sau este liberă. Edilii oraşului doresc să paveze cu un număr minim de dale pătrate cu latura de 1 metru zonele libere (fără copaci) ale parcului, astfel încât să se obţină o alee continuă de la o poartă la alta.

Cerinţă

Scrieţi un program care să determine numărul minim de dale necesare pentru construirea unei alei continue de la o poartă la cealaltă.

Date de intrare

Fişierul de intrare alee.in conţine pe prima linie două valori naturale n şi m separate printr-un spaţiu, reprezentând dimensiunea parcului, respectiv numărul de copaci care se găsesc în parc. Fiecare dintre următoarele m linii conţine câte două numere naturale x şi y separate printr-un spaţiu, reprezentând poziţiile copacilor în parc (x reprezintă linia, iar y reprezintă coloana zonei în care se află copacul). Ultima linie a fişierului conţine patru numere naturale x1 y1 ×2 y2, separate prin câte un spaţiu, reprezentând poziţiile celor două porţi (x1, y1 reprezintă linia şi respectiv coloana zonei ce conţine prima poartă, iar x2, y2 reprezintă linia şi respectiv coloana zonei ce conţine cea de a doua poartă).

Date de ieşire

În fişierul de ieşire alee.out se va afla o singură linie pe care va fi scris un număr natural care reprezintă numărul minim de dale necesare pentru construirea aleii.

Restricţii

  • 1 ≤ n ≤ 175
  • 1 ≤ m ≤ n*n
  • Aleea este continuă dacă oricare două plăci consecutive au o latură comună.
  • Aleea începe cu zona unde se găseşte prima poartă şi se termină cu zona unde se găseşte cea de a doua poartă.
  • Poziţiile porţilor sunt distincte şi corespund unor zone libere.
  • Pentru datele de test există întotdeauna soluţie.

Exemplu

alee.inalee.outExplicaţie
8 6
2 7
3 3
4 6
5 4
7 3
7 5
1 1 8 8
15
O modalitate de a construi aleea cu număr minim de dale este:
2 2 2 0 0 0 0 0
0 0 2 2 0 0 1 0
0 0 1 2 0 0 0 0
0 0 0 2 2 1 0 0
0 0 0 1 2 0 0 0
0 0 0 0 2 2 0 0
0 0 1 0 1 2 2 0
0 0 0 0 0 0 2 2
(cu 0 zonele libere, cu 1 am marcat copacii, iar cu 2 dalele aleii).
Trebuie sa te autentifici pentru a trimite solutii. Click aici