骑士移动步数计算 - 解题思路

这段代码使用广度优先搜索(BFS)算法来计算骑士在国际象棋棋盘上从起点到终点的最少移动步数。

算法思路

1. 初始化：读取棋盘大小和起点、终点坐标。如果起点和终点相同，直接返回0步。

2. BFS准备：

   • 创建一个队列来存储待访问的点
   • 创建一个二维数组记录已访问的点
   • 将起点加入队列，标记为已访问

3. BFS过程：

   • 从队列中取出当前点
   • 检查8个可能的"日"字形移动方向
   • 对于每个方向：
     • 计算新位置坐标
     • 如果到达终点，返回当前步数+1
     • 如果新位置在棋盘内且未被访问过，将其加入队列并标记为已访问

4. 输出结果：对于每个测试用例，输出计算得到的最少步数。

关键点

• 使用BFS保证找到的是最短路径
• 使用队列实现BFS的层序遍历
• 使用标记数组避免重复访问和无限循环
• 处理了8种可能的骑士移动方式

该算法能高效地找到骑士在棋盘上两点之间的最短路径步数。

#include <iostream>
#include <queue>
#include <cstring>
#define AUTHOR "HEX9CF"
using namespace std;

struct SPoint
{
    int x;
    int y;
    int step;
};

int go[8][2] = {
    {1, 2},
    {2, 1},
    {-1, 2},
    {-2, 1},
    {1, -2},
    {2, -1},
    {-1, -2},
    {-2, -1}
    };

int bfs(int l, int x1, int y1, int x2, int y2)
{
    if (x1 == x2 && y1 == y2)
    {
        return 0;
    }
    bool gnd[l][l];
    queue<SPoint> Q;
    memset(gnd, 0, sizeof(gnd));
    SPoint start, node;
    start.x = x1;
    start.y = y1;
    start.step = 0;
    Q.push(start);
    while (!Q.empty())
    {
        int x0, y0, step;
        start = Q.front();
        Q.pop();
        x0 = start.x;
        y0 = start.y;
        step = start.step;
        for (int j = 0; j < 8; j++)
        {
            int x3, y3;
            x3 = x0 + go[j][0];
            y3 = y0 + go[j][1];
            if (x3 == x2 && y3 == y2)
            {
                return step + 1;
            }
            if (x3 >= 0 && x3 < l && y3 >= 0 && y3 < l && !gnd[x3][y3])
            {
                node.x = x3;
                node.y = y3;
                node.step = step + 1;
                Q.push(node);
                gnd[x3][y3] = 1;
            }
        }
    }
    return 0;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x1, y1, x2, y2, l;
        cin >> l >> x1 >> y1 >> x2 >> y2;
        cout << bfs(l, x1, y1, x2, y2) << endl;
    }
    return 0;
}