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 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.

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 

#include <bits/stdc++.h>
using namespace std;
ifstream cin("acces.in");
ofstream cout("acces.out");
const int di[]={-1 , 0 , 1 , 0};
const int dj[]={0 , 1, 0 , -1};
int n , m , a[1002][1002] , x[1000001] , y[1000001];
int ip , jp , is=1 , js=1;
char v[1002][1002];

bool inside(int i , int j)
{
    return i>=1 && i<=n && j>=1 && j<=m;
}

int main()
{
    cin >> n >> m;
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            cin >> v[i][j];
            if(v[i][j]=='-') a[i][j]=0;
            else if(v[i][j]=='P') {ip=i; jp=j; a[i][j]=0;}
            else a[i][j]=1;
        }
    }
    int st=1 , dr=1;
    a[ip][jp]=1;
    x[1]=ip;
    y[1]=jp;
    while(st <= dr )
    {
        int i = x[st] , j = y[st];
        for(int k = 0 ; k < 4 ; k++)
        {
            int ii=i+di[k];
            int jj=j+dj[k];
            if(inside(ii , jj) && a[ii][jj]==0)
            {
                dr++;
                x[dr]=ii , y[dr]=jj , a[ii][jj]=a[i][j]+1;
            }
        }
        st++;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        for(int j = 1 ; j <= m ; ++j)
        {
            if(a[i][j]==1 && (i!=ip || j!=jp)) cout << -1 << ' ';
            else cout << a[i][j]-1 << ' ';
        }
        cout << endl;
    }
    return 0;
}