#C++1672——迷宫问题（广搜）

注意:

多组输入，记得重置相关变量，处理无终点情况

ps:

同类题------2177（终点和起点固定，输入单组）
https://www.dotcpp.com/oj/problem2177.html

AC代码:

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
typedef struct Node
{
	int x,y,step;
	Node(int a,int b,int c):x(a),y(b),step(c){}
}No;
int R,C,endx,endy,startx,starty;
char mp[105][105];
int vis[105][105];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};//L,R,D,U
int bfs()
{
	memset(vis,0,sizeof(vis));//重置vis； 
	queue<No> q;
	vis[startx][starty]=1;
	q.push(No(startx,starty,0));
		while(!q.empty())//只要还有点
		{
			No u=q.front();
			q.pop();
			if(u.x==endx && u.y==endy)//或者找到终点 
				return u.step;
			for(int i=0;i<4;i++)
			{
				//newx,newy遍历所有位置 
				int newx=u.x+dir[i][0],newy=u.y+dir[i][1],newstep=u.step+1;
				//范围内空地、未访问  
				if(newx>=1 && newx<=R && newy>=1 && newy<=C && !vis[newx][newy] && mp[newx][newy] == '-' || mp[newx][newy] == 'E')
				{
					vis[newx][newy]=1;
					q.push(No(newx,newy,newstep)); 
				}
			}
		}
	return 0;	
}
int main()
{
	int T;cin>>T;
	while(T--) 
	{
		cin>>R>>C;
		for(int i=1;i<=R;i++)
			for(int j=1;j<=C;j++)
			{
				cin>>mp[i][j];
				if(mp[i][j]=='E')//记录终点坐标
				{
					endx=i;
					endy=j;
				 } 
				if(mp[i][j]=='S')//记录起始点坐标
				{
					startx=i;
					starty=j;
				}
			} 
		if(bfs())//到达一定有步数（！0）
			cout<<bfs()<<endl;
		else
			cout<<-1<<endl;
	}
	return 0;
}//dongdong