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

camelot.out

camelot.in

camelot.out

Explicație

Vezi imaginea şi explicaţiile de mai sus

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema camelot:

#include<fstream>
#include<queue>
using namespace std;
//deplasarile dupa cele 8 directii
int dx[]= {-1,-1,-2,-2,+1,+1,+2,+2};
int dy[]= {-2,+2,-1,+1,-2,+2,-1,+1};
//adrese castel si cavaleri
struct loc
{
    int x,y;
};
loc castel;
loc cavaleri[1001];
queue<loc> Coada;
//harta
int A[1001][1001];
int p,m,n,k;
int r1,r2;

void citire()
{
    loc adresa;
    ifstream fin("camelot.in");
    fin>>p>>m>>n>>k;
    fin>>castel.x>>castel.y;
    for(int i=1; i<=k; i++)
    {
        fin>>cavaleri[i].x>>cavaleri[i].y;
    }
    fin.close();
}

void rezolva()
{
    loc p,adresa;
    int i,x,y;
    Coada.push(castel);
    A[castel.x][castel.y]=1;
    while(!Coada.empty())
    {
        p=Coada.front();
        Coada.pop();
        for(i=0; i<8; i++)
        {
            x=p.x+dx[i];
            y=p.y+dy[i];
            if(x>=1 && x<=m && y>=1 && y<=n)
                if(A[x][y]==0)
                {
                    adresa.x=x;
                    adresa.y=y;
                    Coada.push(adresa);
                    A[x][y]=1+A[p.x][p.y];
                }
        }
    }
    p=cavaleri[1];
    r1=r2=A[p.x][p.y];
    for(i=2;i<=k;i++)
    {
        if(r1>A[cavaleri[i].x][cavaleri[i].y])
            r1=A[cavaleri[i].x][cavaleri[i].y];
        if(r2<A[cavaleri[i].x][cavaleri[i].y])
            r2=A[cavaleri[i].x][cavaleri[i].y];
    }
    r1--;
    r2--;
}

void afisare()
{
    ofstream fout("camelot.out");
    if(p==1)
        fout<<r1;
    else
        fout<<r2;
    fout.close();
}

int main()
{
    citire();
    rezolva();
    afisare();
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2041 camelot

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2041 camelot de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2041 camelot