迷宫问题 （C++代码）-----Momoc

解题思路:

用广度优先搜索从起点开始按层次搜索，当到达终点时结束搜索并输出步数，同时当无法到达终点时输出-1。

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int Max=800;
char Map[Max][Max];
int vis[Max][Max];//是否访问过 
int Book[Max][Max];//按层次遍历储存答案 
int Next[][2]={1,0,-1,0,0,-1,0,1};//四个方向 
int m,n;
struct Node{//储存坐标 
	int x,y;
}; 
Node point;
queue <Node> q;//队列初始化
int ex,ey;
void bfs(){
	memset(vis, 0, sizeof(vis));
	Book[q.front().x][q.front().y]=0;//初始化开始点的答案 
	while(!q.empty()){
		int x,y;
		Node start=q.front();//先从入口搜索
		q.pop();
		x=start.x;
		y=start.y;
		int xx,yy;
		for(int i=0;i<4;i++){//往四个方向走
			xx=x+Next[i][0];
			yy=y+Next[i][1];
			//检查是否越界 是否有墙
			if(!vis[xx][yy] && x>=1 &&x<=m &&y>=1 &&y<=n && Map[xx][yy]!='#'){
			    
			    point.x=xx;
			    point.y=yy;
			    q.push(point);//可走方向入队
			    vis[xx][yy]=1;
			    Book[xx][yy]=Book[x][y]+1;
	        }
	  
			
		}  
		
		
		
	}
}

int main ()
{
	int t;
	cin>>t;
	while(t--){

		cin>> m>>n;
		memset(Map,0,sizeof Map);//每次都初始化 
		memset(Book,-1,sizeof Book);//初始化为-1，当答案不存在时直接输出结果
		for(int i=1;i<=m;i++)
			for(int j=1;j<=n;j++){	
				cin>>Map[i][j];
				if(Map[i][j]=='S'){//把入口加入队列中
					point.x=i;
					point.y=j;
					q.push(point);
					vis[i][j]=1;
				}
				if(Map[i][j]=='E'){
					ex=i;
					ey=j;	
				}
			}
		
	//	printf("起点%d %d\n",q.front().x,q.front().y);
	//	printf("终点%d %d\n",ex,ey);
	   bfs();
	
	   cout<<Book[ex][ey]<<endl;//输出结果
		
	}
	return 0;

	
		
}