为什么广度优先搜索算法的迷宫问题输出有问题
  • 板块学术版
  • 楼主CodingTim
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/5 20:45
  • 上次更新2024/10/5 21:54:10
查看原帖
为什么广度优先搜索算法的迷宫问题输出有问题
1473968
CodingTim楼主2024/10/5 20:45

代码如下:

#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???
跪求大神指点

2024/10/5 20:45
加载中...