Description
A board is a rectangular array of squares such as on a chessboard, with possibly some squares blocked off. A rook tour of a board is a path that visits each empty square of the board exactly once, moving at each step to an empty adjacent square (North, South, East or West but not diagonally). A rook tour is a rook circuit if it starts and ends on the same square. In the figures below, let the + symbol be the rook, and the X symbol be an obstruction. The following are descriptions of each figure: (a) is a board with no rook circuit, (b) and (c) give distinct rook circuits of the same board and (d) gives the unique (up to direction) rook circuit of another board.
Write a program, which takes as input the description of a board and either finds a rook circuit or determines that there is no rook circuit.
Input
Input consists of a sequence of board descriptions and starting points. The first line of the input is
Nrows Ncols Nblocks StartX StartY
where Nrows is the number of rows in the rectangular array, Ncols is the number of columns in the rectangular array, Nblocks is the number of blocked off squares on the board and (StartX, StartY) is the position on the board where the path is to start (and end). StartX and StartY are 0 based (StartX ranges from 0 to Ncols - 1). Following the first line there are Nblocks lines giving the coordinates of the blocked off squares, one per line. The coordinates of these points are 0 based and are of the form X Y. The final line of each board description is a blank line.
The last line of the input is line of 5 zeroes.
Output
If there is no rook circuit for the corresponding board, the output is a line "NO SOLUTION" followed by a blank line. Otherwise, the output is a sequence of the letters N, S, E, W giving the moves from the starting point to traverse a rook circuit and return to the starting point. (N indicates moving to the previous row, S moving to the next row, E moving to the next column and W moving to the previous column.) If more than 40 moves are required, the moves will be output 40 to a line (except possibly for the last line). The move output is to be followed by a blank line.
Note that the same board may
have several rook circuits. Your program need only find any one (correct) rook circuit.
Sample Input
4 4 2 0 0
1 2
3 0
4 4 0 2 2
4 4 0 0 0
4 4 2 1 2
0 3
2 2
8 8 0 0 0
0 0 0 0 0
Sample Output
NO SOLUTION
NENWWWSESWSEEENW
EEESWWSEESWWWNNN
WNNESENESSSWWN
EEEEEEESWWWWWWSEEEEEESWWWWWWSEEEEEESWWWW
WWSEEEEEESWWWWWWWNNNNNNN
