啊?
查看原帖
啊?
1213524
C_plus_plus_12345楼主2024/2/27 22:56

用广度优先搜索做了一个迷宫,照着样例输入数据输入了一个迷宫,但是输出却是无解,为啥?

输入数据:

#####
S...#
###.#
#...#
#..##
#...#
###.#
#E..#

井号是障碍,点是空位
入口是S,出口是E

代码:

#include<bits/stdc++.h>
using namespace std;
#define False false
#define True true
#define None 0
int u[5]={0, 0, 1, 0, -1};
int w[5]={0, 1, 0, -1, 0};
int n, m, desx, desy, soux, souy, head, tail, x, y, a[101], b[101], pre[101], _map[101][101];
bool f;
void out(int d)
{
	if(pre[d]!=0)
	{
		out(pre[d]);
	}
	printf("%d, $d\n", a[d], b[d]);
}
int main()
{
	cin>>n>>m;                // The maze with n rows and m columns.
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>_map[i][j];
		}
	}
	cout<<"Input the enter: ";
	scanf("%d%d", &soux, &souy);
	cout<<"Input the exit: ";
	scanf("%d%d", &desx, &desy);
	head=0;tail=1;f=False;
	_map[soux][souy]=-1;
	while(head!=tail)         // Judge that queue isn't empty.
	{
		head++;
		for(int i=1;i<=4;i++)
		{
			x=a[head]+u[i];y=b[head]+w[i];
			if((x>0)&&(x<n)&&(y>0)&&(y<m)&&_map[x][y]==0)
			{   // If this direction is avaliable then?
				tail++;
				a[tail]=x;b[tail]=y;pre[tail]=head;
				_map[x][y]=-1; // """Break the bridge after you crossed the river""" //
				if((x==desx)&&(y==desy))
				{
					f=True;
					out(tail);
					break;
				}
			}
		}
		if(f==1)
		{
			break;
		}
	}
	if(f==0)
	{
		cout<<"NEVER"<<endl;
	}
	return 0;
}

我真的服了广度优先搜索,嘈

2024/2/27 22:56
加载中...