题目描述

给定一个$n∗n$的棋盘，以及一个开始位置和终点位置。

棋盘的横纵坐标范围都是 0∼n。

将一个国际象棋中的骑士放置在开始位置上，请问将它移动至终点位置至少需要走多少步。

样例

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

5
28
0

算法

(BFS)

我们在这里总结一下$BFS$算法的常用情景

1. BFS算法是一种搜索算法，分成2类

   • 外部搜索，搜索的每一个状态是整个矩阵，比如黑白棋这道题
   • 内部搜索，搜索的每一个状态是该矩阵内部的每一个格子，比如骑士这道题，一定会用到偏移量这个技巧。

2. BFS求解的问题往往是最少步数，最小，最近什么的。
3. 算法步骤：

   • 找到起点start
   • 将起点放入队列queue中，然后可以将判重数组和dist[][]数组放在一起
   • 取出队头，方向数组的应用

4. 除了偏移量，还有pair<>这个二元组也要用，对于memset()函数中是否会溢出这个问题，sizeof的使用可以避免溢出。使用完memset后一定要置dist[st.x][st.y] = 0，不然会WA，原因是这样更新dist[][]数组的时候是从0x3f开始的，而不是从0开始的。
5. 这道题和仙剑奇侠的区别是，输入没有整张图的信息，只有起点和终点，所以我们只输入st和ed，然后作为bfs()的参数，其他是一样的，多用了一个$make_pair$函数。

时间复杂度

$O(n^2 * 4)$
因为队列中，最多push进n^2个元素，然后方向遍历4个，所以是n^2 * 4

C++ 代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 310;

typedef pair<int, int> PII;

#define x first
#define y second

PII st, ed;

int n, T;
int dist[N][N];

int bfs(PII st, PII ed)
{
    if(st == ed) return 0;
    memset(dist, 0x3f, sizeof dist);
    dist[st.x][st.y] = 0;

    queue<PII> q;
    q.push(st);

    int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

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

        for(int i = 0; i < 8; i ++)
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if(dist[x][y] != 0x3f3f3f3f) continue;
            if(x < 0 || x >= n || y < 0 || y >= n) continue;

            dist[x][y] = dist[t.x][t.y] + 1;
            if(make_pair(x, y) == ed) return dist[x][y];
            q.push({x, y});
        }
    }

    return 0;
}

int main()
{
    cin >> T;
    while(T --)
    {
        cin >> n;
        cin >> st.x >> st.y;
        cin >> ed.x >> ed.y;

        cout << bfs(st, ed) << endl;
    }

    return 0;
}