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;

}