Cerința

Gigel este elev în clasa a XII-a la Liceul Teoretic “Ion Luca” din Vatra Dornei. Acesta, știind că urmează examenul de Bacalaureat și că nu a învățat nimic, s-a hotărât să plece de acasă să își găsească un rost în lume. După zile bune de mers, lipsit de energie, flămând și însetat, acesta a făcut un popas și s-a gândit că era mai bine să nu plece de acasă, motiv pentru care s-a hotărât să se întoarcă. Este cunoscut faptul că în pădurile dornene locuiesc atât Yeti, cât și Bigfoot, precum și mulți vârcolaci. Gigel, fiind un dornean adevărat, cunoaște coordonatele zonelor unde aceștia locuiesc și dorește să se întoarcă acasă pe drumul cel mai scurt, evitându-i pe aceștia.

Cunoscând suprafața regiunii în care se află Gigel și casa acestuia (care poate fi reprezentată printr-un tablou bidimensional cu n linii și m coloane, în care fiecare zonă are coordonatele x și y), coordonatele casei (X1, Y1) și coordonatele locului de popas (X2, Y2), coordonatele zonelor în care locuiesc Yeti (XY, YY) și Bigfoot (XB, YB), precum și coordonatele (X, Y) ale celor K zone în care locuiesc vârcolacii, se cere să îl ajutați pe Gigel să găsească lungimea D a celui mai scurt drum spre casă.

Date de intrare

Fișierul de intrare gigelajungeacasa.in conține pe prima linie trei numere naturale N, M și K, pe linia a doua patru numere naturale X1, Y1, X2 și Y2, pe a treia linie patru numere naturale XY, YY, XB și YB, iar pe următoarele K linii câte o pereche de două numere naturale X și Y. Semnificațiile sunt cele precizate în enunț.

Date de ieșire

Fișierul de ieșire gigelajungeacasa.out va conține un singur număr natural D, pe prima linie, reprezentând lungimea drumului minim spre casa lui Gigel.

Restricții și precizări

• 1 ≤ N, M ≤ 1000
• 0 ≤ K ≤ 14000
• Gigel poate merge pe oricare din direcțiile N, NE, E, SE, S, SV, V și NV.

Exemplu

gigelajungeacasa.in

6 4 5
1 1 6 3
6 1 4 2
3 1
3 2
3 3
5 3
5 4

gigelajungeacasa.out

6

Explicație

Cel mai scurt drum din locul de popas al lui Gigel până la casa acestuia, ocolind vârcolacii, pe Yeti și pe Bigfoot, are lungimea 6.

#include <bits/stdc++.h>
using namespace std;
ifstream cin("gigelajungeacasa.in");
ofstream cout("gigelajungeacasa.out");
const int di[]={-1 , -1 , -1 , 0 , 1 , 1 , 1 , 0 };
const int dj[]={-1 , 0 , 1 , 1, 1 , 0 , -1 , -1};
int n , m , a[1002][1002] , x[100001] , y[100001] , q , xy , yy , xb , yb , r , p;
int ip , jp , is , js;///coordonatele

bool inside(int i , int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}
int main()
{
    ///citire
    cin >> n >> m >> q;
    cin >> is >> js >> ip >> jp;
    cin >> xy >> yy >> xb >> yb;
    for(int i = 1 ; i <= q ; ++i) cin >> r >> p , a[r][p]=1;
    ///LEE
    int st = 1 , dr = 1;///capetele cozii
    a[ip][jp] = 1;///pornirea
    x[1]=ip;
    y[1]=jp;
    while(st <= dr && a[is][js]==0)
    {
        int i= x[st] , j = y[st];///poz curenta
        for(int k = 0 ; k < 8 ; k++)
        {
            ///caculam pozitiie urmatoare
            int ii = i+di[k];
            int jj = j+dj[k];
            if(inside(ii , jj) && a[ii][jj]==0)
            {
                dr++;///crestem coada
                x[dr]=ii;
                y[dr]=jj;
                a[ii][jj]=a[i][j]+1;///cu 1 mai departe
            }
        }
        st++;///avans in coada
    }
    cout << a[is][js]-1;
    return 0;
}