Robots
A robot needs to travel from the NW corner of a room to the SE corner. It can't walk there
directly, though, because of obstacles in its path. You are to write a program to find the
SHORTEST path the robot can take from corner to corner while avoiding all obstacles in its
path.
The robot can move N, S, E, or W, but not diagonally, and must remain at all times within the
boundary of the room. You are to print out the shortest path that the robot can take to get
from corner to corner.
Input Specification
There will be a series of test cases, followed by a line containing
“0 0”. Each test case will begin with a line consisting of two
decimal integers between 2 and 10 inclusive, separated by a space. These numbers, M
and N respectively, define the size of the room: M rows and N
columns. What will then follow are M lines of N characters each. Each line
contains only the characters 0 and 1. 0 corresponds to
an open space, and 1 corresponds to an obstacle. The first character in the
first line (the NW corner) and the last character in the last line (the SE corner) will
always both be 0. There will always be at least one path from the NW corner to
the SE corner, and while there may be many paths between them, the shortest path will always
be unique. There may or may not be one or more additional newline characters separating the
test cases and separating the final test case from the terminating
“0 0”, but there will be no extra spaces or newline characters
appearing within a test case beyond those described above.
Output Specification
The test cases in the output should appear in the order in which they appear in the input.
Each test case in the output will be a string of characters from {N,
S, E, W} corresponding to the path the robot has to
take to get from the NW corner to the SE corner. The first letter in the string corresponds
to the direction in which the robot takes its first step, and so on. This string should
contain no spaces and should be terminated by a newline character. No extra newline
characters should appear in the output.
Sample Input
4 401110011101100007 60000001100011000111010111010111011101000000 0
download as text file
Output for Sample Input
SESSEEEESSWSSSSEEEE
download as text file
Original Problem
NMU Invitational Programming Contest, 2000