НачалоПодразделы
Другие разделы
| 1411. Absent |
| 1412. Boy Scouts |
| 1413. Perfect Slice |
| 1414. Diceline |
| 1415. Elevator |
| 1416. Fibary |
| 1417. Overload |
| 1418. Restaurant tab |
Дата и время
20/12/2024 22:39:58
1419. Amazed
Amazed
Поиск в ширину (BFS)Олимпиадные задачи на английском языке
| 24/06/2010 | Лето 2010 дорешивание ( 4I) |
| 30/06/2010 | Лето 2010 - 4 (I) |
Ограничения: время – 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
