Knight Moves

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1364 字

棋盘上 BFS 求骑士跳跃的最短路

一本通
例

正文

// 原题：https://oj.yecheng.tv/p/T1450
// 题意：L * L 棋盘上求骑士从起点到终点的最小步数，起点等于终点时输出 0。
// 思路：对每组询问做一次 BFS。
// 1. 骑士有 8 个方向的跳法，逐层扩展，第一次到达终点即为最少步数。
// 2. 棋盘最大 300 * 300，单组 BFS 完全够用，不用双向搜索。
// 复杂度：O(n * L^2) 时间 / O(L^2) 空间
// 易错点：读入格式是「棋盘大小 / 起点 / 终点」三行一组，不要把下一组的 L 当成起点读进来。
// 易错点：起点等于终点要直接输出 0，否则 BFS 也会得到 0，但提前判断能省一次搜索。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    if(!(cin >> n)) return 0;
    int dr[8] = {1, 1, 2, 2, -1, -1, -2, -2};
    int dc[8] = {2, -2, 1, -1, 2, -2, 1, -1};
    while(n--){
        int L, sx, sy, tx, ty;
        cin >> L >> sx >> sy >> tx >> ty;
        if(sx == tx && sy == ty){
            cout << 0 << "\n";
            continue;
        }
        vector<vector<int>> dis(L, vector<int>(L, -1));
        queue<pair<int, int>> q;
        dis[sx][sy] = 0;
        q.push({sx, sy});
        while(!q.empty()){
            int r = q.front().first;
            int c = q.front().second;
            q.pop();
            if(r == tx && c == ty) break;
            for(int k = 0; k < 8; k++){
                int nr = r + dr[k], nc = c + dc[k];
                if(nr < 0 || nr >= L || nc < 0 || nc >= L) continue;
                if(dis[nr][nc] >= 0) continue;
                dis[nr][nc] = dis[r][c] + 1;
                q.push({nr, nc});
            }
        }
        cout << dis[tx][ty] << "\n";
    }
    return 0;
}

Knight Moves

正文

一本通·提高篇的其它内容