Se consideră o clădire de formă dreptunghiulară, împărțită în n*m camere, dispuse sub forma unei matrice cu n linii și m coloane. Dintr-o cameră se poate trece în oricare dintre cele 4 camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.
În una dintre camere se află proprietarul clădirii, care dorește să afle, pentru fiecare dintre camere care este timpul minim necesar pentru a ajunge în acea cameră.
Date de intrare
Fișierul de intrare acces.in conține pe prima linie numerele n m; următoarele n linii conțin câte m caractere, care pot fi:
-– reprezintă o cameră liberă#– reprezintă o cameră închisăP– reprezintă camera proprietarului, care se consideră liberă
Date de ieșire
Fișierul de ieșire acces.out va conține o matrice cu n linii și m coloane, elementele matricei reprezentând timpul minim necesar ca proprietarul să ajungă în camere clădirii. Pentru camerele ocupate și pentru camerele libere în care nu se poate ajunge timpul necesar va fi -1.
Matricea va fi afișată linie cu linie, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin câte un spațiu.
Restricții și precizări
1 ≤ n,m ≤ 1000
Exemplu
acces.in
4 6 --#-#- --##-- --P--- -----#
acces.out
4 3 -1 -1 -1 5 3 2 -1 -1 3 4 2 1 0 1 2 3 3 2 1 2 3 -1
SOLUTIE 1
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
ifstream fin("acces.in");
ofstream fout("acces.out");
int n , m;
short a[1001][1001];
int x[1000001], y[1000001];
char P[1001][1001];
int xp , yp;
const int dx[] = {0 , 0 , 1 , -1},
dy[] = {1 , -1 , 0 , 0};
int main(){
fin >> n >> m;
for(int i = 1 ; i <= n ; i ++)
for(int j = 1 ; j <= m ; j ++)
{
fin >> P[i][j];
if(P[i][j] == 'P')
xp = i, yp = j;
}
fin.close();
int st , dr;
st = dr = 1;
x[dr] = xp, y[dr] = yp;
a[x[1]][y[1]] = 1;
while(st <= dr)
{
int i = x[st], j = y[st];
for(int k = 0 ; k < 4 ; k ++)
{
int ii = i + dx[k], jj = j + dy[k];
if( ii > 0 && ii <= n && jj > 0 && jj <= m && P[ii][jj] !='#' && a[ii][jj] == 0)
{
a[ii][jj] = a[i][j] + 1;
dr ++;
x[dr] = ii, y[dr] = jj;
}
}
st ++;
}
for(int i = 1 ; i <= n ; i ++)
{
for(int j = 1 ; j <= m ; j ++)
fout << a[i][j] - 1 << " ";
fout << "\n";
}
fout.close();
return 0;
}
SOLUTIE 2
#include <fstream>
#include <queue>
using namespace std;
ifstream f("acces.in");
ofstream g("acces.out");
struct pereche
{
int x, y;
};
int n, m, i, j;
char camere[1010][1010];
int t[1010][1010];
bool viz[1010][1010], ok;
queue<pereche> q;
pereche first, second;
int main()
{
f >> n >> m;
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
f >> camere[i][j];
if (camere[i][j] == 'P') {
q.push({i, j});
viz[i][j] = true;
}
}
}
while (!q.empty()) {
first = q.front();
second = {first.x - 1, first.y};
ok = (second.x >= 1 && second.x <= n && second.y >= 1 && second.y <= m && camere[second.x][second.y] != '#');
if (ok && !viz[second.x][second.y]) {
viz[second.x][second.y] = true;
t[second.x][second.y] = t[first.x][first.y] + 1;
q.push(second);
}
second = {first.x, first.y + 1};
ok = (second.x >= 1 && second.x <= n && second.y >= 1 && second.y <= m && camere[second.x][second.y] != '#');
if (ok && !viz[second.x][second.y]) {
viz[second.x][second.y] = true;
t[second.x][second.y] = t[first.x][first.y] + 1;
q.push(second);
}
second = {first.x + 1, first.y};
ok = (second.x >= 1 && second.x <= n && second.y >= 1 && second.y <= m && camere[second.x][second.y] != '#');
if (ok && !viz[second.x][second.y]) {
viz[second.x][second.y] = true;
t[second.x][second.y] = t[first.x][first.y] + 1;
q.push(second);
}
second = {first.x, first.y - 1};
ok = (second.x >= 1 && second.x <= n && second.y >= 1 && second.y <= m && camere[second.x][second.y] != '#');
if (ok && !viz[second.x][second.y]) {
viz[second.x][second.y] = true;
t[second.x][second.y] = t[first.x][first.y] + 1;
q.push(second);
}
q.pop();
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (!viz[i][j])
g << "-1 ";
else
g << t[i][j] << ' ';
}
g << '\n';
}
f.close();
g.close();
return 0;
}