==Include(page="template/taskheader" task_id="muzeu")==
 
==Include(page="template/raw")==
 
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).
 
h2. 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)
 
h2. Date de Iesire
 
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.
 
h2. Restrictii si precizari
 
. 1 <= N <= 250
 
h2. Exemplu
 
muzeu.in muzeu.out
8 -1 -1 -1 -2 2 3 4 5
 
...#.... -2 -1 -1 -2 1 2 -2 6
 
#..#..#. 8 -2 -2 1 0 1 2 -2
 
.##.P..# 7 6 -2 2 -2 2 -2 6
 
..#.#.#. 6 5 4 3 4 3 4 5
 
........ 6 5 4 3 4 4 5 6
 
........ -2 -2 -2 2 3 4 -2 -2
 
###...## 2 1 0 1 2 3 4 5

==Include(page="template/taskheader" task_id="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).
 
h2. 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)
 
h2. Date de Iesire
 
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$.
 
h2. Restrictii si precizari
 
* 1 ≤ N ≤ 250
 
h2. Exemplu
 
table(example). |_. muzeu.in |_. muzeu.out |
| 8
  ...#....
  #..#..#.
  .##.P..#
  ..#.#.#.
  ........
  ........
  ###...##
  ..P.....
| -1 -1 -1 -2  2  3  4   5
  -2 -1 -1 -2  1  2 -2   6
    8 -2 -2  1  0  1  2 -2
    7  6 -2  2 -2  2 -2   6
    6  5  4  3  4  3  4  5
    6  5  4  3  4  4  5  6
  -2 -2 -2  2  3  4 -2 -2
    2  1  0  1  2  3  4  5 |
 
==Include(page="template/taskfooter" task_id="muzeu")==

..P.....
==Include(page="template/taskfooter" task_id="muzeu")==

504