题目名：移动骑士
题目链接：https://www.acwing.com/problem/content/1104/
基础BFS，每次走一步路径长度+1，所以queue依旧可以做
每次向8个方向扩展
dist[i][j] 代表起点到达{i, j}的距离
st[i][j] 代表是否到达过{i, j}, 0代表没到过，1代表到过

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int tt, n, dist[310][310];
int dx[8] = {-2,-2,-1,-1,1,1,2,2}, dy[8] = {-1,1,-2,2,-2,2,-1,1};

bool st[310][310];
queue<pii> q;

bool value(int x, int y){//判断是否越界
    return x >= 0 && y >= 0 && x < n && y < n; 
}

//得到距离函数
int solve(){
    //因为有多组数据，所以记得初始化数组哦
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    while(q.size()) q.pop();

    //输入
    int stx, sty, endx, endy;
    cin >> n >> stx >> sty >> endx >> endy;
    //处理起点，把起点加入队列中，起点到起点的路径为0
    q.push({stx, sty}); dist[stx][sty] = 0; st[stx][sty] = 1;
    if(stx == endx && sty == endy) return 0;

    //BFS
    while(q.size()){
        int nowx = q.front().first, nowy = q.front().second;//取出当前坐标
        q.pop();

        for(int i = 0; i < 8; i++){
            int nx = nowx + dx[i], ny = nowy + dy[i];//得到下一个坐标
            if(value(nx, ny) && !st[nx][ny]){//如果坐标没越界 && 没被访问过
                //如果是重点直接返回答案
                if(nx == endx && ny == endy) return dist[nowx][nowy] + 1;
                //更新下一个坐标的距离，并且放入队列中
                dist[nx][ny] = dist[nowx][nowy] + 1;
                q.push({nx,ny});
                st[nx][ny] = 1;
            }
        }
    }
    return 0;
}

int main(){
    cin >> tt;
    while(tt--){
        cout << solve() << endl;;
    }

    return 0;
}

上面的是遇到终点直接返回答案 288ms
其实也可以把所有位置走完，然后返回答案，但是会慢一点 537ms

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int tt, n, dist[310][310];
int dx[8] = {-2,-2,-1,-1,1,1,2,2}, dy[8] = {-1,1,-2,2,-2,2,-1,1};

bool st[310][310];
queue<pii> q;

bool value(int x, int y){
    return x >= 0 && y >= 0 && x < n && y < n; 
}

void solve(){
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    int stx, sty, endx, endy;
    cin >> n >> stx >> sty >> endx >> endy;
    q.push({stx, sty}); dist[stx][sty] = 0; st[stx][sty] = 1;

    while(q.size()){
        int nowx = q.front().first, nowy = q.front().second;
        q.pop();
        for(int i = 0; i < 8; i++){
            int nx = nowx + dx[i], ny = nowy + dy[i];
            if(value(nx, ny) && !st[nx][ny]){
                dist[nx][ny] = dist[nowx][nowy] + 1;
                q.push({nx,ny});
                st[nx][ny] = 1;
            }
        }
    }
    cout << dist[endx][endy] << endl;//最后返回答案
}

int main(){
    cin >> tt;
    while(tt--){
        solve();
    }

    return 0;
}

最后贴一个不用pii的方案

#include<bits/stdc++.h>
using namespace std;
int tt, n, dist[200000];

bool st[200000];
queue<int> q;

bool value(int x, int y){
    return x >= 0 && y >= 0 && x < n && y < n; 
}

int solve(){
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    while(q.size()) q.pop();

    int stx, sty, endx, endy;
    cin >> n >> stx >> sty >> endx >> endy;
    int k =  2 * n + 1, k2 = 2 * k;
    int dxy[8] = {-k2-1,-k2+1,-k+2,-k-2,k+2,k-2,k2+1,k2-1};

    q.push(stx * k + sty); dist[stx * k + sty] = 0; st[stx * k + sty] = 1;
    if(stx == endx && sty == endy) return 0;

    while(q.size()){
        int now = q.front(); q.pop();
        for(int i = 0; i < 8; i++){
            int nxt = now + dxy[i];
            if(value(nxt / k, nxt % k) && !st[nxt]){
                if(nxt == endx * k + endy) return dist[now] + 1;
                dist[nxt] = dist[now] + 1;
                q.push(nxt);
                st[nxt] = 1;
            }
        }
    }
    return 0;
}

int main(){
    cin >> tt;
    while(tt--){
        cout << solve() << endl;;
    }

    return 0;
}