Cerința

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 anumite camere se află echipe de pompieri. Pentru o intervenție cât mai rapidă în cazul unui eventual incendiu apărut în una dintre camerele clădirii, este necesar să se știe, pentru fiecare cameră care este timpul minim în care o echipă de pompieri ajunge în acea cameră.

Date de intrare

Fișierul de intrare acces1.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ă o cameră în care se găsește o echipă de pompieri

Date de ieșire

Fișierul de ieșire acces1.out va conține o matrice cu n linii și m coloane, fiecare element al matricei reprezentând timpul minim necesar ca o echipă de pompieri să ajungă în camera corespunzătoare. Pentru camerele ocupate se va fișa simbolul #, iar pentru cele libere în care nu va ajunge nici o echipă se va afișa -.

Exemplu

acces1.in

4 6
P-#-#P
--##--
--P---
-----#

acces1.out

0 1 # - # 0 
1 2 # # 2 1 
2 1 0 1 2 2 
3 2 1 2 3 # 

#include <bits/stdc++.h>
using namespace std;
ifstream cin("acces1.in");
ofstream cout("acces1.out");
const int di[]={-1 , 0 , 1 , 0};
const int dj[]={0 , 1 , 0 , -1};
int n , m ;
int a[1002][1002], numar;
bool prt[1001][1001];

struct poz{int i , j;};
poz q[1000000];

bool inside(int i , int j){return i>=1 && i<=n && j>=1 && j<=m;}
void lee(int dr)
{
    int st=1;
    while(st<=dr)
    {
        int i = q[st].i;
        int j = q[st].j;
        //if (i == n)break;
        for(int d = 0 ; d < 4 ; d++)
        {
            int inou=i+di[d];
            int jnou=j+dj[d];
            if(inside(inou,jnou) && a[inou][jnou]==0 )
            {
                q[++dr].i=inou;
                q[dr].j=jnou;
                a[inou][jnou]=a[i][j]+1;
            }
        }
        st++;
    }
    //return a[q[st].i][q[st].j];
}
int main()
{
    char ch;
    int dr = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
        {
            cin >> ch;
            if (ch == 'P')
            {
                poz start;
                start.i = i;
                start.j = j;
                a[i][j] = 1;
                q[++ dr] = start;
                prt[i][j] = 1;
            }
            else if (ch == '#')a[i][j] = -1;
            //else if (ch == '-')a[i][j] = 1;
        }

    lee(dr);
    for (int i = 1; i <= n; ++ i)
    {

        for (int j = 1; j <= m; ++ j)
            if (a[i][j] == -1)cout << "# ";
            else if (a[i][j] == 0 && prt[i][j] == 0)cout << "- ";

            else cout << a[i][j] - 1 << ' ';
        cout << '\n';
            }
    return 0;
}