## Дата и время

04/06/2023 12:39:36

## Авторизация

 Имя: Пароль:
Зарегистрироваться
Восстановить пароль

# 1419. Amazed

## Amazed

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)

In this problem, we consider traversing a rectangular maze with walls that prohibit passage, and seek to find the shortest distance from a given starting cell to all other cells. Technically, a maze is a rectangular grid of cells, each of which may or may not contain a blocking wall. When traversing a maze, one starts at a given cell (without a wall) and makes successive horizontal or vertical steps to adjacent cells without walls. One is not allowed to make a diagonal step, even if a diagonally adjacent cell contains no wall. The presence of walls might make it impossible to reach some cells from the starting cell, in which case they're considered to be infinitely distant.
Input Format
The input contains one or more mazes, each described by some successive lines of input. The first line of a maze contains two positive integers r and c describing the number of rows and columns in the cell grid (0\ ≤\ r,\ c\ ≤\ 50). The next r lines each contain c characters from the alphabet {' ', 'W', 'S'}. ' ' represents a cell without a wall, 'W' represents a cell containing a wall, and 'S' represents the starting cell (without a wall). There is exactly one starting cell in a maze.
Output Format
For each maze in the input, output the maze to show the cells with walls labeled by 'WWWWW' and the cells without walls labeled by the least number of steps to traverse there from the starting cell. Widen each input cell to five output columns wide, outputting 'WWWWW' for each 'W' input, and up to a 3-digit number (or inf representing ∞) with a blank on either side for each ' ' or 'S' input. Print new line before each maze.

Sample Input

6 7
WWWWW W
W  WW
WS WW
W  W WW
W
WWWWWWW
8 12
WWWWWWWWWWWW
W   W S  W
W W  WWW W W
W W      W W
W WWWWWWWW W
W          W
W  W    WW W
WWWWWWWWWWWW


Sample Output


WWWWWWWWWWWWWWWWWWWWWWWWW inf WWWWW
WWWWW   9   10 WWWWWWWWWW inf  inf
9    8 WWWWW   0    1 WWWWWWWWWW
WWWWW   7    6 WWWWW   2 WWWWWWWWWW
7    6    5    4    3    4 WWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW
WWWWW  13   12   11 WWWWW   1    0    1    2 WWWWW  30   31
WWWWW  14 WWWWW  10    9 WWWWWWWWWWWWWWW   3 WWWWW  29 WWWWW
WWWWW  15 WWWWW   9    8    7    6    5    4 WWWWW  28 WWWWW
WWWWW  16 WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW  27 WWWWW
WWWWW  17   18   19   20   21   22   23   24   25   26 WWWWW
WWWWW  18   19 WWWWW  21   22   23   24 WWWWWWWWWW  27 WWWWW
WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Source: California State Polytechnic University Programming Contest, Spring 2009