| Author: | A. Klenin, I. Blinov | Time limit: | 3 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Young programmer Vasya created a two-dimensional game in Battle Royale genre. The game is played on a square field of N by N cells. Each cell is either empty (represented by '.') or occupied by wall (represented by '#').
The player is located in one of the empty cells. Every second the player can stay in place or move to an adjacent empty cell up, down, left or right. After player moves, all cells along the perimeter of the game field are removed (so field size is reduced by 2 along each axis). If the player was located on one of the removed cells, he dies.
Your program must, for each empty cell of the field, calculate maximum number of seconds the player can survive if he starts the game from that cell and plays optimally.
The first line of input contains a single integer N. The next N lines contain one string of N characters each — representation of the game field.
The output should contain N lines of N numbers, where the j-th number in the i-th line indicates the maximum survival time of a player when starting from a cell with coordinates (i, j). If the corresponding cell is not empty, output zero.
1 ≤ N ≤ 500
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|