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 cele K perechi de coordonate (X, Y) ale zonelor î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.
Răspunsuri la întrebare
#include <fstream>
#include <queue>
#include <iostream>
using namespace std;
ifstream fin("gigelajungeacasa.in");
ofstream fout("gigelajungeacasa.out");
queue < pair < int, int > > q;
int a[1002][1002];
int di[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dj[] = {0, 1, 1, 1, 0, -1, -1, -1};
int n, m, k;
int x1, y1, x2, y2;
int iy, jy, ib, jb;
void citire()
{
int i, j;
fin >> n >> m >> k;
fin >> x1 >> y1 >> x2 >> y2;
fin >> iy >> jy >> ib >> jb;
//cout << iy << " " << jy << " " << ib << " " << jb;
a[iy][jy] = -1;
a[ib][jb] = -1;
int x, y;
for(i = 1; i <= k; i++)
{
fin >> x >> y;
a[x][y] = -1;
}
}
void filll(int i, int j)
{
int k;
q.push(make_pair(i, j));
while(!q.empty())
{
i = q.front().first;
j = q.front().second;
q.pop();
for(k = 0; k < 8; k++)
{
int nexti = i + di[k], nextj = j + dj[k];
if(a[nexti][nextj] == 0)
{
a[nexti][nextj] = a[i][j] + 1;
if(nexti == x2 && nextj == y2)
{
fout << a[nexti][nextj];
}
q.push(make_pair(nexti, nextj));
}
}
}
}
void gard()
{
int i, j;
for(i = 0; i <= n + 1; i++)
{
a[i][0] = -1;
a[i][m + 1] = -1;
}
for(j = 0; j <= m + 1; j++)
{
a[0][j] = -1;
a[n + 1][j] = -1;
}
}
int main()
{
citire();
gard();
filll(x1, y1);
fin.close();
fout.close();
return 0;
}