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.
​
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 ieșire
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.
Restricții si precizări
-
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
Heading 1
Implementare
#include <iostream>
#include <fstream>
#include <queue>
#define dim 177
using namespace std;
ifstream f ("alee.in");
ofstream g ("alee.out");
int dx[] ={0,1,0,-1};
int dy[] ={-1,0,1,0};
short a[dim][dim], n , x , y , k,start_x,start_y,stop_x,stop_y;
void read()
{
f >> n >> k;
for(int i = 1;i <= k;i++)
f >> x >> y , a[x][y] = -1;
f >> start_x >> start_y >> stop_x >> stop_y;
}
bool bun(int x,int y)
{
if(a[x][y] != 0)
return false;
if(x > n || x < 1 || y > n || y < 1)
return false;
return true;
}
void lee()
{
int new_x,new_y;
queue < pair < int,int > > Q;
Q.push(make_pair(start_x , start_y));
a[start_x][start_y] = 1;
while(not Q.empty())
{
x = Q.front().first;
y = Q.front().second;
Q.pop();
if(x == stop_x && y == stop_y)
break;
for(int i = 0;i <= 3;i++)
{
new_x = x + dx[i];
new_y = y + dy[i];
if(bun(new_x,new_y))
Q.push(make_pair(new_x,new_y)) , a[new_x][new_y] = a[x][y] + 1;
}
}
}
int main()
{
read();
lee();
g << a[stop_x][stop_y];
return 0;
}