Muzeu
Un muzeu are forma patratica si contine N*N camere ce pot fi vizitate. Unele camere sunt deschise si contin opere de arta, altele sunt inchise (sunt folosite pentru alte scopuri). In unele din camerele libere, se afla paznici. Directorul muzeului se teme de eventualitatea unei spargeri si de aceea doreste sa evalueze cat de bine au fost asezati paznicii in camerele libere. Mai precis, el doreste sa afle, pentru fiecare camera libera, care este distanta minima pana la cel mai apropiat paznic (numarul minim de camere prin care trebuie sa intre un paznic pentru a ajunge la camera respectiva). Paznicii se pot deplasa numai in camerele libere din Nord, Est, Sud sau Vest (cu conditia sa nu paraseasca muzeul).
Date de intrare
Pe prima linie a fisierului muzeu.in se afla numarul intreg N, reprezentand numarul de linii (si de coloane) ale muzeului (muzeul avand N*N camere). Urmatoarele N linii contin cate N caractere fiecare:
-
`.' pentru camera libera in care nu se afla paznic
-
`P' pentru camera libera in care se afla paznic
-
`#' pentru camera inchisa (prin care nu pot trece nici paznicii, dar in care nu pot intra nici hotii)
Date de ieșire
In fisierul muzeu.out veti afisa N linii, fiecare din ele continand N numere intregi (separate prin spatii). Fiecare numar afisat corespunde camerei de pe linia si coloana corespunzatoare din fisierul de intrare. Pentru fiecare camera libera veti afisa distanta minima pana la cel mai apropiat paznic (sau -1 daca nici un paznic nu poate ajunge in aceasta camera). Pentru camerele inchise, veti afisa -2.
Restricții si precizări
-
1 ≤ N ≤ 250
Exemplu
Heading 1
Implementare
#include <fstream>
#include <iostream>
using namespace std;
ifstream f ("muzeu.in");
ofstream g ("muzeu.out");
int Max=999999999;
int in=1,sf=0,i,nl,nc,n,j,a[252][252],l,c;
char sir[252];
const int dl[]={-1,0,1,0};
const int dc[]={0,1,0,-1};
struct muzeu{
int l,c;
}coada[1000000],u;
void bordare()
{
for(i=0;i<=n+1;i++)
a[i][n+1] = a[n+1][i]=a[0][i]=a[i][0]=-1;
}
void lee()
{
while(in <= sf)
{
u = coada[in];
for(i = 0; i <= 3; i++)
{
nl = u.l + dl[i];
nc = u.c + dc[i];
if(a[u.l][u.c] + 1 < a[nl][nc])
{
a[nl][nc] = a[u.l][u.c] + 1;
coada[++sf].l = nl;
coada[sf].c = nc;
}
}
in++;
}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>sir;
for(j=1;j<=n;j++)
{
if(sir[j-1]=='#')
a[i][j]=-2;
else
if(sir[j-1]=='P'){
coada[++sf].l=i;
coada[sf].c=j;
}
else
a[i][j]=Max;
}
}
bordare();
lee();
for(i = 1;i <= n; i++){
for(j = 1 ;j<= n; j++)
if(a[i][j] != Max)
g<<a[i][j]<<" ";
else
g<<-1<<" ";
g<<"\n";
}
return 0;
}