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

gigelajungeacasa.out

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.

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 GigelAjungeAcasa:

#include <fstream>
#include <queue>

using namespace std;

bool okay (unsigned short int i, unsigned short int j);

unsigned short int N, M, K;
unsigned short int X1, Y1, X2, Y2;
unsigned short int XY, YY, XB, YB;
unsigned short int X[14001], Y[14001];

queue < pair <unsigned short int, unsigned short int> > Q;
const short int dx[] = {-1, -1,  0,  1,  1,  1,  0, -1};
const short int dy[] = { 0,  1,  1,  1,  0, -1, -1, -1};
short int matrix[1001][1001];
unsigned short int i, j, k, nextI, nextJ;

unsigned short int D;

int main ()
{
    ifstream fin ("gigelajungeacasa.in");
    fin >> N >> M >> K;
    fin >> X1 >> Y1 >> X2 >> Y2;
    fin >> XY >> YY >> XB >> YB;
    for (i=1; i<=K; i++)
        fin >> X[i] >> Y[i];
    fin.close();
    matrix[XY][YY] = -1;
    matrix[XB][YB] = -1;
    for (i=1; i<=K; i++)
        matrix[X[i]][Y[i]] = -1;
    Q.push(make_pair(X2,Y2));
    while (!Q.empty())
    {
        i = Q.front().first;
        j = Q.front().second;
        Q.pop();
        for (k=0; k<8; k++)
        {
            nextI = i + dx[k];
            nextJ = j + dy[k];
            if (okay(nextI,nextJ) == 1 && matrix[nextI][nextJ] == 0)
            {
                matrix[nextI][nextJ] = matrix[i][j] + 1;
                Q.push(make_pair(nextI,nextJ));
            }
        }
    }
    D = matrix[X1][Y1];
    ofstream fout ("gigelajungeacasa.out");
    fout << D;
    fout.close();
    return 0;
}

bool okay (unsigned short int i, unsigned short int j)
{
    if (i<1 || j<1 || i>N || j>M)
        return 0;
    return 1;
}

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 #1795 GigelAjungeAcasa

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1795 GigelAjungeAcasa 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 #1795 GigelAjungeAcasa