题目一：骑士游历（****） 分支限界法 c++

以下是使用分支限界法求解骑士游历问题的C++代码：

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

const int N = 10;
int n, m;
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy8] = {1 2, 2, 1, -1, -2, -2 -1};

struct Node {
    int x, y, step;
};

bool st[N][N];

int bfs(int sx, int sy, int ex, int ey) {
    queue<Node> q;
    q.push({sx, sy, 0});
    st[sx][sy] = true;

    while (q.size()) {
        auto t = q.front();
        q.pop();

        if (t.x == ex && t.y == ey) return t.step;

        for (int i = 0; i < 8; i++) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b]) continue;
            q.push({a, b, t.step + 1});
            st[a][b] = true;
        }
    }

    return -1;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        memset(st, 0, sizeof st);
        cout << bfs(sx, sy, ex, ey) << endl;
    }

    return 0;
}