【POJ 2488】A Knight‘s Journey 题解（深度优先搜索）

背景 骑士厌倦了一次又一次地看到同样的黑白方块，决定去旅行 全世界每当骑士移动时，它是一个方向上的两个正方形和一个垂直于这个方向的正方形。骑士的世界就是他生活的棋盘。我们的骑士生活在一个棋盘上，这个棋盘的面积比普通的8*8棋盘小，但它仍然是矩形的。你能帮助这位冒险的骑士制定旅行计划吗？ 问题 找到一条道路，让骑士访问每个广场一次。骑士可以在棋盘的任何一方开始和结束。

输入 输入以第一行中的正整数n开始。以下行包含n个测试用例。每个测试用例都由一条包含两个正整数p和q的单行线组成，因此1<=pq<=26。这表示一个pq棋盘，其中p表示有多少个不同的正方形数字1，p存在，q描述存在多少不同的方形字母。这是拉丁字母表的前q个字母：A。 输出 每个场景的输出都以包含“scenario#i:”的行开始，其中i是从1开始的场景编号。然后打印一条单行线，其中包含按字典顺序排列的第一条路径，该路径访问棋盘上的所有方格，骑士移动后接一条空行。路径应通过连接访问的方块的名称在单行上给出。每个方块名称由一个大写字母和一个数字组成。 如果不存在这样的路径，则应该在单行上输出“impossible”。

Sample Input 3 1 1 2 3 4 3

Output Scenario #1: A1

Scenario #2: impossible

Scenario #3: A1B3C1A2B4C2A3B1C3A4B2C4

思路

从（1,1）开始进行搜索，同时记录步数，若步数等于棋盘格数，则找到路径。需要注意的是，输入数据的顺序是行列，输出的是列行，且列序号要转为大写字母输出。

AC代码

#include <iostream>
#include <cstring>
using namespace std;
#define AUTHOR "HEX9CF"

const int go[8][2] = {
    -2, -1,
    -2, 1,
    -1, -2,
    -1, 2,
    1, -2,
    1, 2,
    2, -1,
    2, 1};

int n, m;
int vis[30][30];
int path[30][2];
int flg;

void dfs(int x, int y, int s){
    if(s == m * n){
        flg = 1;
        return;
    }
    for(int i = 0; i < 8; i++) {
        int xx = x + go[i][0];
        int yy = y + go[i][1];
        if(xx > 0 && xx <= n && yy > 0 && yy <= m && !vis[xx][yy] && !flg){
            vis[xx][yy] = 1;
            path[s][0] = xx;
            path[s][1] = yy;
            dfs(xx, yy, s + 1);
            vis[xx][yy] = 0;
        }
    }
    return;
}

int main() {
    int t;
    cin >> t;
    for(int cnt = 1; t--; cnt++){
        cin >> m >> n;// 行 列
        cout << "Scenario #" << cnt << ":" << endl;
        flg = 0;
        memset(vis, 0, sizeof(vis));
        path[0][0] = 1;
        path[0][1] = 1;
        vis[1][1] = 1;
        dfs(1, 1, 1);
        if(flg){
            for(int i = 0; i < n * m; i++){
                cout << char(path[i][0] + 'A' - 1) << path[i][1];
            }
            cout << endl;
        }
        else
        {
            cout << "impossible" << endl;
        }
        cout << endl;
    }
    return 0;
}