正经题解｜骑士移动

【算法分析】

求最少需要多少步，考虑使用广搜。从起点开始进行搜索，当搜索到终点时就结束。注意地图下标以及 $vis$ 数组的清空。

【参考代码】

#include <bits/stdc++.h>
using namespace std;

int dir[8][2] = { -2,-1,-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2 };
struct node {
    int x, y, step;
}l,r;
bool vis[309][309];
int main() {
    int _;
    cin >> _;
    while (_--) {
        memset(vis, 0, sizeof(vis));
        int L;
        cin >> L;
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        queue<node> q;
        q.push({ sx,sy,0 });
        vis[sx][sy] = 1;
        while (q.size()) {
            r = q.front();
            q.pop();
            if (r.x == ex && r.y == ey) {
                cout << r.step << '\n';
                break;
            }
            for (int i = 0; i < 8; i++) {
                l.x = r.x + dir[i][0];
                l.y = r.y + dir[i][1];
                l.step = r.step + 1;
                if (l.x >= 0 && l.x < L && l.y >= 0 && l.y < L && !vis[l.x][l.y]) {
                    vis[l.x][l.y] = 1;
                    q.push(l);
                }
            }
        }
    }
    return 0;
}

【时间复杂度】

$O(L*n*n)$

【预计得分】

$100pts$