hnust 1497: 中国象棋中的跳马问题

hnust 1497: 中国象棋中的跳马问题

题目描述
现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）
输入
第一行输入n表示有n组测试数据。
每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。

输出
马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”
样例输入 Copy
2
9 10
1 1 2 3
0
9 10
1 1 2 3
8
1 2
2 2
3 3
3 4
1 4
3 2
2 4
1 3
样例输出 Copy
1
can not reach!
提示
此题是一个搜索题，建议选择BFS(广搜)。一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。

解题过程

这段C++代码实现了一个基于广度优先搜索（BFS）的算法，用于解决在一个棋盘上模拟“马走日”的路径搜索问题。以下是对代码的更详细解析：

1. 头文件和命名空间

• 包含必要的头文件，提供输入输出、内存操作和队列功能。
• 使用using namespace std;简化代码。

2. 全局变量定义

• dir结构体数组D定义了马的8个可能跳跃方向。
• zhang数组定义了与8个方向相对应的4个拐马角点，用于确定马的走法。
• X和Y变量存储棋盘的行数和列数。
• a数组存储起点和终点的坐标。
• Q队列用于BFS过程中的层级遍历。
• visit二维数组标记已访问的点，避免重复搜索。
• can二维数组标记障碍点，马不能跳到这些点上。
• cnt变量记录从起点到当前点的步数。

3. 检查函数check

• 检查函数check确定给定点是否在棋盘的边界内。

4. BFS算法实现BFS

• BFS函数是核心算法实现：
  • 初始化队列Q，将起点坐标和步数压入队列。
  • 使用while循环，只要队列不为空，就继续搜索。
  • 在循环中，弹出队列前端的点作为当前点，并检查是否到达终点。
  • 如果到达终点，输出步数cnt并结束搜索。
  • 对于当前点的每个可能跳跃方向，检查是否在棋盘内、是否为重复点、是否为障碍点。
  • 如果跳跃后的点有效，将其压入队列，并标记为已访问。

5. 主函数main

• 读取测试用例数量n，并对每个测试用例执行以下操作：
  • 清空队列Q和两个二维数组visit、can。
  • 读取棋盘大小X和Y。
  • 读取起点和终点坐标。
  • 读取障碍点数量m，并使用循环读取每个障碍点的坐标，将其标记在can数组中。
  • 调用BFS函数执行搜索，并输出结果。

6. 程序结束

• 当所有测试用例处理完毕后，程序正常结束并返回0。

代码逻辑分析

• 代码使用BFS算法来找到从起点到终点的最短路径，同时考虑了障碍物和马的走法规则。
• BFS是一种适合解决最短路径问题的算法，因为它能够一层一层地遍历所有可能的路径。

潜在问题

• 如果棋盘很大或障碍点很多，visit和can数组可能会消耗大量内存。
• 代码没有处理棋盘上没有有效路径到达终点的情况。

改进建议

• 对于大规模棋盘，考虑使用更节省内存的数据结构，如位图或哈希表。
• 在BFS函数中添加对搜索失败的检查，如果队列为空且未找到终点，输出适当的消息。
• 考虑使用std::vector代替固定大小的数组，以提高代码的灵活性和安全性。
• 对输入数据进行有效性检查，确保它们在预期的范围内，并且是有效的棋盘坐标。
• 代码中没有提供障碍点的输入示例，实际使用时需要确保输入格式正确。

部分代码

代码如下（检查点是否在棋盘内 ）：

int check(int a, int b)  
{
    if (a > 0 && a <= X && b > 0 && b <= Y)
        return 1;
    else
        return 0;
}

代码如下（ 广度优先搜索算法）：

void BFS()
{
    int H, L;
    cnt = 0;
    Q.push(a[0]);
    Q.push(a[1]);
    Q.push(cnt);
    visit[a[0]][a[1]] = 1;
    while (!Q.empty())
    {
        H = Q.front(); Q.pop();
        L = Q.front(); Q.pop();
        cnt = Q.front(); Q.pop();
        if (H == a[2] && L == a[3])
        {
            cout << cnt << endl;
            return;
        }
        for (int i = 0; i < 8; i++)
        {
            if (can[H + zhang[i / 2][0]][L + zhang[i / 2][1]] == 0)  //判断该点是否为拐马角点
                if (check(H + D[i].x, L + D[i].y) && !visit[H + D[i].x][L + D[i].y]&&!can[H + D[i].x][L + D[i].y])  
                /*判断跳的那个点是否在棋盘内，跳的点不能是重复点，跳的点不能是障碍点*/
                {
                    Q.push(H + D[i].x);
                    Q.push(L + D[i].y);
                    Q.push(cnt + 1);
                    visit[H + D[i].x][L + D[i].y] = 1;
                }
        }
    }
    cout<<"can not reach!"<<endl;
}

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct dir
{
    int x;
    int y;
};
dir D[8] = { {-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2} };  //马跳的8个方向
int zhang[4][2] = { -1,0,0,1,1,0,0,-1 };  //8个方向对应的4个拐马角点。
int X,Y;  //棋盘大小
int a[6];
queue<int> Q;
int visit[101][101];  //判断是否为重复点
int can[101][101];  //判断是否为障碍点
int cnt;
int check(int a, int b)  //检查点是否在棋盘内
{
    if (a > 0 && a <= X && b > 0 && b <= Y)
        return 1;
    else
        return 0;
}
void BFS()
{
    int H, L;
    cnt = 0;
    Q.push(a[0]);
    Q.push(a[1]);
    Q.push(cnt);
    visit[a[0]][a[1]] = 1;
    while (!Q.empty())
    {
        H = Q.front(); Q.pop();
        L = Q.front(); Q.pop();
        cnt = Q.front(); Q.pop();
        if (H == a[2] && L == a[3])
        {
            cout << cnt << endl;
            return;
        }
        for (int i = 0; i < 8; i++)
        {
            if (can[H + zhang[i / 2][0]][L + zhang[i / 2][1]] == 0)  //判断该点是否为拐马角点
                if (check(H + D[i].x, L + D[i].y) && !visit[H + D[i].x][L + D[i].y]&&!can[H + D[i].x][L + D[i].y])  
                /*判断跳的那个点是否在棋盘内，跳的点不能是重复点，跳的点不能是障碍点*/
                {
                    Q.push(H + D[i].x);
                    Q.push(L + D[i].y);
                    Q.push(cnt + 1);
                    visit[H + D[i].x][L + D[i].y] = 1;
                }
        }
    }
    cout<<"can not reach!"<<endl;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        cin >> X >> Y;
        while (!Q.empty())
            Q.pop();
        memset(visit, 0, sizeof(visit));
        memset(can, 0, sizeof(can));
        cin >> a[0] >> a[1] >> a[2] >> a[3];
        int m;
        cin >> m;
        while (m--)
        {
            int a, b;
            cin >> a >> b;
            can[a][b] = 1;
        }
        BFS();
    }
    return 0;
}