Cerința

Jaina se află în Theramore Isle și trebuie să ajungă la mentorul ei, Antonidas. Aceștia se află într-o matrice pătratică de dimensiune n x n, în poziții de coordonate cunoscute.

Jaina se poate deplasa în oricare dintre cele 8 direcții. Astfel, dacă inițial ea se găsește în celula de coordonate (x, y), poate ajunge în oricare dintre celulele (x-1, y-1), (x-1, y), (x-1, y + 1), (x, y + 1), (x + 1, y + 1), (x + 1, y), (x + 1, y - 1) sau (x, y - 1) făcând exact un pas.

În anumite celule se află câte o sursă de energie. Fiecare sursă emite raze în patru direcții (N, E, S, V), fiecare rază ajungând până la marginea matricei.

Când Jaina pășește pe o astfel de rază, ea se teleportează obligatoriu în celula sursei razei respective, deci nu este posibilă trecerea dincolo de aceste raze decât prin punctul sursă. Teleportarea este automată și instantanee și nu se consideră ca fiind un pas al Jainei.

Antonidas vă roagă să o ajutați pe Jaina să ajungă la el, efectuând un număr minim de pași!

Date de intrare

Fișierul de intrare jaina.in conține pe prima linie numărul n, iar pe a doua linie 4 numere naturale separate prin spații, care semnifică coordonatele celulei în care se află Jaina și coordonatele celulei în care se află Antonidas. ( 2 perechi linie-coloană )

A treia linie conține numărul m de surse de energie.

Pe următoarele m linii se află câte două numere naturale x y, reprezentând coordonatele fiecărei surse.

Date de ieșire

Fișierul de ieșire jaina.out va conține pe prima linie numărul nrp, reprezentând numărul minim de pași pe care Jaina trebuie să-i efectueze pentru a ajunge la Antonidas.

Restricții și precizări

• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 10
• Orice celulă are dimensiunea 1x1
• În cazul în care Jaina se află la intersecția a două raze de surse diferite, aceasta se va teleporta la sursa de linie minimă.
• Nu există două surse care să se afle pe aceeași linie sau pe aceeași coloană.
• Se garantează că există soluție pentru toate testele.
• Antonidas promite că o să fiți răsplătiți cu o minge de foc dacă găsiți răspunsul corect la această problemă.
• Deoarece Jaina este disperată, limitele de memorie sunt foarte mari, însă pe viitor nu este garantat acest lucru!

Exemplu

jaina.in

4
2 1 4 4 
1
3 3

jaina.out

2

Explicație

Numărul de pași necesari în acest caz este 2.

#include <bits/stdc++.h>

using namespace std;

ifstream cin("jaina.in");
ofstream cout("jaina.out");

const int di[] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dj[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int n , ip , jp , is , js , t , ii , jj;
int a[101][101] , b[101][101];

struct poz
{
    int i , j;
}v[11];

queue <poz> Q;
int inside(int i , int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= n;
}

void lee()
{
    poz r;
    r.i = ip;
    r.j = jp;
    Q.push(r);
    a[ip][jp] = 1;
    while(!Q.empty())
    {
        r = Q.front();
        for(int d = 0 ; d < 8 ; d++)
        {
            int inou = r.i + di[d];
            int jnou = r.j + dj[d];
            if(inside(inou,jnou))
                if(b[inou][jnou] == 0)
                    if(a[inou][jnou] == 0)
                    {
                        Q.push({inou , jnou});
                        a[inou][jnou] = a[r.i][r.j] + 1;
                    }
                    else;
                else
                {
                    int raza = b[inou][jnou];
                    if(a[v[raza].i][v[raza].j] == 0)
                    {
                        Q.push({v[raza].i , v[raza].j});
                        a[v[raza].i][v[raza].j] = a[r.i][r.j] + 1;
                    }
                }
        }
        Q.pop();
    }
}

int main()
{
    cin >> n >> ip >> jp >> is >> js >> t;
    for(int i = 1 ; i <= t ; i++)
        cin >> v[i].i >> v[i].j;
    for(int i = 1 ; i <= t ; i++)
    {
        for(int k = 1 ; k <= n ; k++)
        {
            if(b[v[i].i][k] == 0) b[v[i].i][k] = i;
            if(b[k][v[i].j] == 0) b[k][v[i].j] = i;
        }
    }
    lee();
    cout << a[is][js] - 1;
}