为什么广度优先搜索算法的迷宫问题输出有问题

学术版

CodingTim @ 2024-10-05 20:45:09

代码如下:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>

using namespace std;

int a[100][100], v[100][100];

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

queue<Point> r; // 申请队列

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

int main()
{
    int n = 0, m = 0, startx = 0, starty = 0, p = 0, q = 0;
    int flag = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &a[m][n]);
        }
    }
    scanf("%d%d%d%d", &startx, &starty, &p, &q);
    // BFS
    Point start;
    start.x = startx;
    start.y = starty;
    start.step = 0;
    r.push(start); // 将起点推入队列
    v[startx][starty] = 1;
    while (!r.empty())
    {
        int x = r.front().x;
        int y = r.front().y;

        if (x == p && y == q)
        {
            flag = 1;
            printf("%d", r.front().step);
            break;
        }
        for (int k = 0; k < 3; k++)
        {
            int tempX, tempY;
            tempX = x + dx[k];
            tempY = y + dy[k];
            if (a[tempX][tempY] == 1 && v[tempX][tempY] == 0) // 如果这个点是空地并且未访问
            {
                // 推入队列
                Point temp;
                temp.x = tempX;
                temp.y = tempY;
                temp.step = r.front().step + 1;
                r.push(temp);
                v[tempX][tempY] = 1; // 设置成已访问状态
            }
        }
        r.pop(); // 扩展完成之后需要将队首弹出队列
    }
    if (flag == 0)
    {
        printf("no answer\n");
    }
    return 0;
}
输入:
5 4
1 1 2 1
1 1 1 1
1 1 2 1
1 2 1 1
1 1 4 3
输入解析
第一行:5行4列
第二行到第四行:输入迷宫结构 1代表空地 2代表障碍物
第五行:前两个是起点坐标,后两个是终点坐标

为什么正确结果是7我输出的是no answer???
跪求大神指点


by __Beyond__ @ 2024-10-05 21:38:57

@CodingTim 你的样例应该有问题的,依照你的解释,迷宫是 5 行 4 列 的,而你给出的地图是 4 行 4 列


by __Beyond__ @ 2024-10-05 21:41:28

@CodingTim 还有这个 for 循环:

for (int k = 0; k < 3; k++)

应该为 k < 4k <= 3 对嘛?


|