[数据结构与算法]DFS-A Knight‘s Journey

题目链接

关键点：
注意输出时的字母要按字典序，具体就是深搜时的方向排序问题

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

struct node {
    int x, y;
    node(int a, int b) : x(a), y(b){};
};
bool vis[30][30];
vector<node> tmp;
vector<vector<node>> ans;
int flag = 0;
int dirx[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int diry[8] = {-2, -2, -1, -1,1, 1, 2, 2};
int p, q;

void dfs(int x, int y, int cnt, int all) {
    if (cnt == all) {
        flag = 1;
        ans.push_back(tmp);
        return;
    }
    for (int i = 0; i < 8; i++) {
        int tx = x + dirx[i];
        int ty = y + diry[i];
        if (tx >= 1 && tx <= p && ty >= 1 && ty <= q && !vis[tx][ty]) {
            vis[tx][ty] = true;
            tmp.push_back(node(tx, ty));
            dfs(tx, ty, cnt + 1, all);
            tmp.pop_back();
            vis[tx][ty] = false;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int n, count = 1;
    cin >> n;
    while (count <= n) {
        cin >> p >> q;
        memset(vis, false, sizeof vis);
        ans.clear();
        tmp.clear();
        flag = 0;
        vis[1][1] = true;
        tmp.push_back(node(1, 1));
        dfs(1, 1, 1, p * q);
        cout << "Scenario #" << count << ":" << endl;
        if (flag == 0) cout << "impossible" << endl;
        else {
            vector<node> t = ans[0];
            for (int i = 0; i < t.size(); i++) {
                int x = t[i].x;
                char y = t[i].y - 1 + 'A';
                cout << y << x;
            }
            cout << endl;
        }
        cout << endl;
        count++;
    }

    return 0;
}