Acces

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;
}