描述

棋盘是一个如同国际象棋棋盘那样的矩形方格阵列，其中可能有一些方格被封锁。棋盘上的“车巡游”是一条路径，它恰好访问棋盘上的每个空白方格一次，每一步移动到相邻的空白方格（向北、向南、向东或向西移动，但不允许斜向移动）。如果“车巡游”的起点和终点在同一个方格上，那么它就被称为“车回路”。在下面的图示中，用“+”符号表示车，用“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 年竞赛

解题思路

该代码用于解决棋盘上车回路的寻找问题，解题时先持续读取输入，直至遇到$5$个$0$ ，对于每组输入读取棋盘行数$H$、列数$W$、封锁方格数量$N$及起始点坐标$Si$和$Sj$，将所有方格初始化为空白并按输入标记封锁方格；接着进行无解判断，利用奇偶性原则统计黑白空白方格数量，若不相等或棋盘行数少于$2$或列数少于$2$则判定无解；对于棋盘无封锁方格的特殊情况，根据列数奇偶性采用特殊解法生成车回路；若无法特殊处理，则从起始点开始使用深度优先搜索算法，每次尝试向四个方向移动，计算每个可能下一步方格的可能性得分并排序，优先尝试选择少的方格，同时在搜索中进行剪枝，若方格可能性得分为$0$或为$1$且后续搜索失败则回溯；最后，若找到车回路则按每行$40$个字符格式输出移动方向，未找到则输出 &“NO SOLUTION”&，代码通过$judge()$用奇偶性原则判断解的存在性、$isIn()$检查坐标范围、$calPossibility()$计算方格可能性得分、$dfs()$进行深度优先搜索、$specialSolve()$处理特殊情况以及$output()$输出最终结果。

C++实现

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <functional>
#include <map>
#include <string.h>
#include <math.h>
#include <list>
#include <set>
using namespace std;
 
const int MAX_W = 100;
 
int W, H, N, Si, Sj;
char G[MAX_W][MAX_W];
int StepSum;
char step[MAX_W * MAX_W];
bool finish;
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
 
struct Next {
    int i, j, p;
    Next(int ii = 0, int jj = 0, int pp = 0) {
        i = ii;
        j = jj;
        p = pp;
    }
};
 
bool judge() {
    int w, b;
    w = b = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (G[i][j] == ' ') {
                if ((i + j) & 1) b++;
                else w++;
            }
        }
    }
    return b == w;
}
 
bool isIn(int i, int j) {
    return 0 <= i && i < H && 0 <= j && j < W;
}
 
int calPossibility(int i, int j) {
    int p = 0;
    for (int k = 0; k < 4; k++) {
        if (isIn(i + dir[k][0], j + dir[k][1]) && (G[i + dir[k][0]][j + dir[k][1]] == ' ' || (i + dir[k][0] == Si && j + dir[k][1] == Sj))) p++;
    }
    return p;
}
 
bool cmp(const Next & n1, const Next & n2) {
    return n1.p < n2.p;
}
 
void dfs(int nowStep, int lastI, int lastJ) {
    if (nowStep == StepSum) {
        bool canArrive = false;
        for (int i = 0;  i < 4; i++) {
            if (isIn(lastI + dir[i][0], lastJ + dir[i][1]) && lastI + dir[i][0] == Si && lastJ + dir[i][1] == Sj) {
                if (dir[i][0] == -1) step[nowStep] = 'N';
                if (dir[i][0] == 1) step[nowStep] = 'S';
                if (dir[i][1] == 1) step[nowStep] = 'E';
                if (dir[i][1] == -1) step[nowStep] = 'W';
                finish = true;
                break;
            }
        }
        return;
    }
    Next next[4];
    int num = 0;
    for (int i = 0; i < 4; i++) {
        int nexti = lastI + dir[i][0];
        int nextj = lastJ + dir[i][1];
        if (isIn(nexti, nextj) && G[nexti][nextj] == ' ') {
            next[num++] = Next(nexti, nextj, calPossibility(nexti, nextj));
        }
    }
    sort(next, next + num, cmp);
    bool mustGo = false;
    for (int i = 0; i < num; i++) {
        if (next[i].p == 0) return;
        if (next[i].p == 1) mustGo = true;
        G[next[i].i][next[i].j] = '.';
        if (next[i].i < lastI) step[nowStep] = 'N';
        if (next[i].i > lastI) step[nowStep] = 'S';
        if (next[i].j > lastJ) step[nowStep] = 'E';
        if (next[i].j < lastJ) step[nowStep] = 'W';
        dfs(nowStep + 1, next[i].i, next[i].j);
        if (!finish) {
            G[next[i].i][next[i].j] = ' ';
            if (mustGo) return;
        } else return;
    }
}
 
void specialSolve() {
    int all = H * W, now = 0;
    int nowi = Si, nowj = Sj;
    finish = true;
    if (W % 2 == 0) {  // 如果列数是偶数
        while (now < all) {
            if (nowi == 0) {  // 如果在第一行
                if (nowj == W - 1) {  // 如果在第一行最右向南
                    step[now] = 'S';
                    nowi++;
                } else {  // 否则都向东
                    step[now] = 'E';
                    nowj++;
                }
            } else {  // 如果不在第一行
                if (nowj % 2 == 0) {  // 如果在偶数列
                    if (nowi == 1 && nowj != 0) {  // 如果在第二行并且不是第一列的第二行向西
                        step[now] = 'W';
                        nowj--;
                    } else {  // 如果不在第二行，或者在第一列的第二行向北
                        step[now] = 'N';
                        nowi--;
                    }
                } else {  // 如果在奇数列
                    if (nowi == H - 1) {  // 如果在最后一行向西
                        step[now] = 'W';
                        nowj--;
                    } else {  // 否则都向南
                        step[now] = 'S';
                        nowi++;
                    }
                }
            }
            now++;
        }
    } else {
        while (now < all) {
            if (nowj == 0) {
                if (nowi == 0) {
                    step[now] = 'E';
                    nowj++;
                } else {
                    step[now] = 'N';
                    nowi--;
                }
            } else {
                if (nowi % 2 == 1) {
                    if (nowj == 1 && nowi != H - 1) {
                        step[now] = 'S';
                        nowi++;
                    } else {
                        step[now] = 'W';
                        nowj--;
                    }
                } else {
                    if (nowj == W - 1) {
                        step[now] = 'S';
                        nowi++;
                    } else {
                        step[now] = 'E';
                        nowj++;
                    }
                }
            }
            now++;
        }
    }
}
 
void output() {
    if (!finish) {
        cout << "NO SOLUTION" << endl << endl;
        return;
    }
    for (int i = 0, counter = 0; i <= StepSum; i++, counter++) {
        if (counter == 40) {
            counter = 0;
            cout << endl;
        }
        cout << step[i];
    }
    cout << endl << endl;
}
 
int main() {
 
    std::ios::sync_with_stdio(false);
 
    while (1) {
        cin >> H >> W >> N >> Sj >> Si;
        if (!H) break;
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                G[i][j] = ' ';
            }
        }
        for (int i = 0; i < N; i++) {
            int ti, tj;
            cin >> tj >> ti;
            G[ti][tj] = 'X';
        }
        finish = false;
        StepSum = W * H - N - 1;
        if (H < 2 || W < 2 || !judge()) {
            output();
            continue;
        }
        if (N == 0) {
            specialSolve();
            output();
            continue;
        }
        G[Si][Sj] = '.';
        dfs(0, Si, Sj);
        output();
    }
 
    return 0;
}