Pro.ID22310 TitleMaze Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22310 AC0 Submit0 Ratio- 时间&空间限制描述You have been blindfolded and deposited someplace in a maze. You have no idea where you are. You do know, however, that the maze is laid out on a grid, and that each grid location is either blocked or free. In fact, you have memorized a map of the maze. Also, your magnetic personality allows you to always sense which direction is north. In this maze, you have four possible moves: north, south, east, and west. Your task is to find the shortest sequence of moves that will guarantee your escape, regardless of your initial placement in the maze. You have "escaped" whenever you reach a square on an outside edge of the grid (and if you start there, then you've already escaped). Further moves are irrelevant once you have escaped. If you try to walk into a wall, you will simply stay in the same spot. You may assume that it is possible to escape from every unblocked position in the maze. 输入Input consists of a positive integer n <= 8, followed by n lines giving the rows of an n by n grid. This grid describes the maze you are trapped in. Written on the screen, north is up. Blocked locations are denoted by the character "O" (that's an uppercase "o"), while unblocked locations are indicated by the character ".". 输出Description You have been blindfolded and deposited someplace in a maze. You have no idea where you are. You do know, however, that the maze is laid out on a grid, and that each grid location is either blocked or free. In fact, you have memorized a map of the maze. Also, your magnetic personality allows you to always sense which direction is north. In this maze, you have four possible moves: north, south, east, and west. Your task is to find the shortest sequence of moves that will guarantee your escape, regardless of your initial placement in the maze. You have "escaped" whenever you reach a square on an outside edge of the grid (and if you start there, then you've already escaped). Further moves are irrelevant once you have escaped. If you try to walk into a wall, you will simply stay in the same spot. You may assume that it is possible to escape from every unblocked position in the maze. Input Input consists of a positive integer n <= 8, followed by n lines giving the rows of an n by n grid. This grid describes the maze you are trapped in. Written on the screen, north is up. Blocked locations are denoted by the character "O" (that's an uppercase "o"), while unblocked locations are indicated by the character ".". Output Output consists of a number of lines, each consisting of one of "north", "south", "east", or "west", indicating the shortest sequence of moves that guarantees escape for any possible unblocked starting position. If there are multiple possible shortest sequences, any of them will do. Sample Input 4 OO.O ...O OO.. O..O Sample Output east
northSource 样例输入4 OO.O ...O OO.. O..O 样例输出east
north作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-4 21:50 , Processed in 0.038471 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
