移动骑士

BFS

• 每次遍历8个方向
• st存放当前位置是否访问过
• 有多组数据，每次bfs要将st清空

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 310;
bool st[N][N];

int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int bfs(pair<int,int> start, pair<int,int> end, int n) {
    memset(st, 0, sizeof st);
    queue<pair<int,int>> q;
    int ans = 0;
    q.push(start);
    st[start.first][start.second] = true;
    while (q.size()) {
        int l = q.size();
        for (int i = 0 ; i < l ; i ++ ) {
            auto t = q.front();
            q.pop();
            if (t == end) return ans;
            for (int j = 0 ; j < 8 ; j ++ ) {
                int x = t.first + dx[j];
                int y = t.second + dy[j];
                if (x >= 0 && x < n && y >= 0 && y < n && !st[x][y]) {
                    st[x][y] = true;
                    q.push({x ,y});
                }
            }
        }
        ans ++ ;
    }
    return -1;
}

int main()
{
    int t;
    cin >> t;
    while (t -- ) {
        int n;
        cin >> n;
        pair<int,int> start, end;
        cin >> start.first >> start.second;
        cin >> end.first >> end.second;
        cout << bfs(start, end, n) << endl;
    }
    return 0;
}