某广搜迷宫求助
  • 板块学术版
  • 楼主SunLegend
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/9/5 14:13
  • 上次更新2023/11/4 07:40:02
查看原帖
某广搜迷宫求助
461452
SunLegend楼主2021/9/5 14:13

蒟蒻求助

题目

一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

【输入】 一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解

【输出】 左上角到右下角的最短路径,格式如样例所示。
【输入样例】
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
【输出样例】
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)


蒟蒻能走通一些迷宫(如样例),但对于某个蒟蒻自创迷宫:
0 0 0 0 0
1 1 1 1 0
0 0 0 0 0
0 0 1 1 1
0 0 0 0 0
蒟蒻表示不会走(QAQ)

求大佬指点,代码如下:

#include <bits/stdc++.h>
using namespace std;
int Map[10][10];
bool bj[10][10];
int be_x=0,be_y=0,en_x=4,en_y=4;
int wz[100][2];
int pre[100];
int fx[4]={1,-1,0,0},fy[4]={0,0,-1,1};
int head,tail;
bool pd;

int print(int t)
{
	if(t>1)
	{
		print(pre[t]);
	}
	cout<<'('<<wz[t][0]<<", "<<wz[t][1]<<')'<<endl;
}
void bfs()
{
	tail=1;
	head=0;
	wz[tail][0]=be_x;
	wz[tail][1]=be_y;
	pre[tail]=head;
	bj[be_x][be_y]=1;
	while(head!=tail)
	{
		head++;
		for(int i=0;i<4;i++)
		{
			int x=fx[i]+wz[head][0];
			int y=fy[i]+wz[head][1];
			if(bj[x][y]==0 && Map[x][y]==0)
			{
				tail++;
				bj[x][y]=1;
				pre[tail]=head;
				wz[tail][0]=x;
				wz[tail][1]=y;
				if(x==en_x && y==en_y)
				{
					print(tail);
					pd=1;
					break;
				}
			}
		}
		if(pd) break;
	}
}

int main()
{
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			cin>>Map[i][j]; 
		}
	}
	bfs();
	return 0;
}
2021/9/5 14:13
加载中...