Cerința

Regele Arthur – Inimă de Leu, vrea să adune la castel toţi cavalerii Mesei Rotunde pentru a hotărî împreună soarta regatului. Dar cavalerii nu se află toţi în Camelot şi durează un timp până vor ajunge la castel din pădurea care înconjoară castelul.

Harta pădurii are forma unei matrici, cu m linii şi n coloane. Pentru fiecare cavaler care nu este în Camelot se cunosc coordonatele x y, reprezentând linia şi coloana din matrice în care se află iniţial cavalerul. Toţi cavalerii pornesc simultan spre castel, iar fiecare cavaler se deplasează după regula de deplasare a calului de la jocul de şah.

Cunoscând dimensiunile mxn ale matricei, coordonatele castelului şi cele ale cavalerilor, se cere să se determine:

1. numărul minim de mutări după care va ajunge la castel unul dintre cavaleri

Cerința

Regele Arthur – Inimă de Leu, vrea să adune la castel toţi cavalerii Mesei Rotunde pentru a hotărî împreună soarta regatului. Dar cavalerii nu se află toţi în Camelot şi durează un timp până vor ajunge la castel din pădurea care înconjoară castelul.

Harta pădurii are forma unei matrici, cu m linii şi n coloane. Pentru fiecare cavaler care nu este în Camelot se cunosc coordonatele x y, reprezentând linia şi coloana din matrice în care se află iniţial cavalerul. Toţi cavalerii pornesc simultan spre castel, iar fiecare cavaler se deplasează după regula de deplasare a calului de la jocul de şah.

Cunoscând dimensiunile mxn ale matricei, coordonatele castelului şi cele ale cavalerilor, se cere să se determine:

1. numărul minim de mutări după care va ajunge la castel unul dintre cavaleri
2. numărul minim de mutări după care toţi cavalerii se vor afla la castel.

De exemplu, în imaginea de mai sus este reprezentată harta sub forma unei matrici de tip 8x8, iar castelul are coordonatele 4 5 (linia 4 şi coloana 5), primul cavaler se află iniţial în punctul de coordonate 1 2 iar cel de al doilea în punctul 8 1. Primul cavaler va ajunge la castel din minim 2 deplasări, iar al doilea după minim 4 mutări Pentru prima întrebare răspunsul este 2, iar pentru a doua întrebare răspunsul este 4.

Date de intrare

Fișierul de intrare camelot.in conține pe prima linie numărul p, pentru toate testele de intrare numărul p putând avea doar valoarea 1 sau valoarea 2.

Pe cea de a doua linie sunt scrise numerele naturale m n k, separate prin câte un spaţiu, iar pe a treia linie se află coordonatele xc yc ale castelului. Pe următoarele k linii se află k perechi de numere întregi x[i] y[i] (1 ≤ i ≤ k), separate prin câte un spaţiu, reprezentând coordonatele cavalerilor.

Date de ieșire

Fișierul de ieșire camelot.out va conține pe prima linie:

• pentru p=1, pe prima linie se va scrie numărul minim de mutări după care va ajunge unul din cavaleri
• pentru p=2, pe prima linie se va scrie numărul minim de mutări după care vor ajunge toţi cavalerii

Restricții și precizări

• 5 ≤ m,n ≤ 1000
• 1 ≤ k ≤ 1000
• 1 ≤ x[i], xc ≤ m, 1 ≤ y[i], yc ≤ n, pentru orice 1 ≤ i ≤ k
• Eventualele intersecţii ale drumurilor cavalerilor nu influenţează rezultatele
• Pentru datele de test se garantează existenţa unei soluţii

Exemple:

camelot.in

1
8 8 2
4 5
1 2
8 1

camelot.out

2

camelot.in

2
8 8 2
4 5
1 2
8 1

camelot.out

4

Explicație

Vezi imaginea şi explicaţiile de mai sus

#include <bits/stdc++.h>


using namespace std;

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

const int dic[] = {-2 , -2 , -1 , -1 ,  1 , 1 ,  2 , 2};
const int djc[] = {-1 ,  1 , -2 ,  2 , -2 , 2 , -1 , 1};

int cer , n , m , k , a[1001][1001] , c , pmin = 99999999 , pmax , x , y;
struct poz
{
    int i , j;
}C[1001];
queue <poz> Q;
bool inside(int i , int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

int main()
{
    cin >> cer;
    cin >> n >> m >> k;
    int ir , jr;
    cin >> ir >> jr;
    for(int i = 1 ; i <= k ; i++)
    {
        cin >> x >> y;
        C[i] = {x , y};
        a[x][y] = -1;
    }
    Q.push({ir , jr});
    a[ir][jr] = 1;
    while(!Q.empty() && c < k)
    {
        poz r = Q.front();
        for(int i = 0 ; i < 8 ; i++)
        {
            int inou = r.i + dic[i];
            int jnou = r.j + djc[i];
            if(inside(inou , jnou) && a[inou][jnou] <= 0)
            {
                if(a[inou][jnou] == -1) c++;
                a[inou][jnou] = a[r.i][r.j] + 1;
                Q.push({inou , jnou});
            }
        }
        Q.pop();
    }

    for(int i = 1 ; i <= k ; i++)
    {
        if(a[C[i].i][C[i].j] < pmin) pmin = a[C[i].i][C[i].j];
        if(a[C[i].i][C[i].j] > pmax) pmax = a[C[i].i][C[i].j];
    }

    if(cer == 1) cout << pmin - 1;
    else cout << pmax - 1;

}