描述

棋盘是一个如同国际象棋棋盘那样的矩形方格阵列，其中可能有一些方格被封锁。棋盘上的“车巡游”是一条路径，它恰好访问棋盘上的每个空白方格一次，每一步移动到相邻的空白方格（向北、向南、向东或向西移动，但不允许斜向移动）。如果“车巡游”的起点和终点在同一个方格上，那么它就被称为“车回路”。在下面的图示中，用“+”符号表示车，用“X”符号表示障碍物。以下是对每个图示的描述：(a) 是一个不存在车回路的棋盘，(b) 和 (c) 给出了同一个棋盘的不同车回路，(d) 给出了另一个棋盘唯一的（不考虑方向）车回路。

编写一个程序，该程序以棋盘的描述和起始点作为输入，要么找到一个车回路，要么确定不存在车回路。

输入

输入由一系列棋盘描述和起始点组成。输入的第一行是：

Nrows Ncols Nblocks StartX StartY

其中 Nrows 是矩形阵列的行数，Ncols 是矩形阵列的列数，Nblocks 是棋盘上被封锁的方格数量，(StartX, StartY) 是棋盘上路径开始（和结束）的位置。StartX 和 StartY 是从 0 开始计数的（StartX 的范围是从 0 到 Ncols - 1）。在第一行之后，有 Nblocks 行给出被封锁方格的坐标，每行一个。这些点的坐标也是从 0 开始计数的，格式为 X Y。每个棋盘描述的最后一行是一个空行。

输入的最后一行是由 5 个 0 组成的行。

输出

如果对于相应的棋盘不存在车回路，输出一行“NO SOLUTION”，后面跟一个空行。否则，输出一系列字母 N、S、E、W，这些字母表示从起始点出发遍历车回路并回到起始点的移动方向（N 表示移动到上一行，S 表示移动到下一行，E 表示移动到下一列，W 表示移动到上一列）。如果需要的移动步数超过 40 步，那么每 40 步输出一行（最后一行可能除外）。移动方向的输出后面跟一个空行。

请注意，同一个棋盘可能有多个车回路。你的程序只需要找到任何一个（正确的）车回路即可。

输入数据 1

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

输出数据 1

NO SOLUTION

NENWWWSESWSEEENW

EEESWWSEESWWWNNN

WNNESENESSSWWN

EEEEEEESWWWWWWSEEEEEESWWWWWWSEEEEEESWWWW
WWSEEEEEESWWWWWWWNNNNNNN

提示

一些事实：

1. 奇偶性原则：如果我们将阵列中的方格涂成黑白相间的颜色（当 (x + y) 为偶数时方格为白色，当 (x + y) 为奇数时方格为黑色），车回路中的每一步移动都必须从一个白色方格移动到一个黑色方格，反之亦然。因此，任何车回路中白色方格和黑色方格的数量必须相同。上面的棋盘 (a) 有 8 个白色和 6 个黑色的未封锁方格，所以不可能有车回路。
2. 两邻接原则：如果一个方格只有两个邻接方格，那么它必须通过这两个邻接方格被访问。当回路到达其中一个邻接方格时，它必须接着经过这个有两个邻接方格的方格，然后再到另一个邻接方格。在棋盘 (d) 中，(0,0)、(3, 0)、(0, 2)、(1,3)、(2,3)、(3,3) 和 (3,2) 这些方格每个都有两个邻接方格。因此，路径必然会以某种顺序包含 (1,0)-(0,0)-(0,1)-(0,2)-(1,2)-(1,3)-(2,3)-(3,3)-(3,2)-(3,1)-(3,0)-(2,0) 这些移动。
3. 死胡同原则：永远不要绘制会使一个方格只剩下一个出口的线段。
4. 过早闭合原则：在所有方格都被访问之前，永远不要闭合回路。

来源

大纽约地区 2003 年竞赛