迷宫问题 （C++代码）可AC

解题思路:利用BFS解决最短路径

参考代码:
#include <iostream>
using namespace std;
struct note{
	int x;    //横坐标
	int y;    //纵坐标
	int step;    //保存当前步数
}Que[10001];
int main(){
	int count;
	cin>>count;
	while(count){
		int m,n,tail,head,flag=0,book[101][101]={0};
		char Start_x,Start_y,End_x,End_y,map[101][101]={0};
		cin>>n>>m;
		int tx,ty,k;
		int next[4][2]={{1,0},	//向下走 
				    {0,1},	//向右走 
				    {-1,0},	//向上走 
				    {0,-1}};//向左走  
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				cin>>map[i][j];
				if(map[i][j]=='S')
					Start_x=i,Start_y=j;
				else if(map[i][j]=='E')
					End_x=i,End_y=j;
			}
		head=1;
		tail=1;
		Que[tail].x=Start_x;
		Que[tail].y=Start_y;
		Que[tail].step=0;
		tail++;
		book[Start_x][Start_y]=1;
		while(head<tail){
			for(k=0;k<=3;k++){
				tx=Que[head].x+next[k][0];
				ty=Que[head].y+next[k][1];
				if(tx<1||ty<1||tx>n||ty>m)
					continue;
				if(map[tx][ty]!='#'&&book[tx][ty]==0){
						book[tx][ty]=1;
						Que[tail].x=tx;
						Que[tail].y=ty;
						Que[tail].step=Que[head].step+1;
						tail++;
				}
				if(tx==End_x&&ty==End_y){
					flag=1;
					break;
				}
			}
			if(flag)
				break;
			head++;        
		}
		if(flag==1)
			cout<<Que[tail-1].step<<endl;
		else
			cout<<"-1"<<endl;	
		count--;
	}
	return 0;
}

深搜超时版：

#include <iostream>
using namespace std;
int Min=99999;
char Map[101][101];
int book[101][101],m,n;
int Start_x,Start_y,End_x,End_y;
void Dfs(int x,int y,int step){
	if(x==End_x&&y==End_y){
		if(step<Min)
			Min=step;    //更换最小步数
		return;
	}
	int tx,ty,k;
	int next[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
	/* 枚举4个方向 */
	for(k=0;k<=3;k++){
		tx=x+next[k][0];
		ty=y+next[k][1]; 
		if(tx<1||tx>n||ty<1||ty>m)
			continue;
		if(Map[tx][ty]!='#'&&book[tx][ty]==0){
			book[tx][ty]=1;
			Dfs(tx,ty,step+1);
			book[tx][ty]=0;
		}
	}
	return;
}
int main(){
	int count;	cin>>count;
	while(count--){
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++){
				cin>>Map[i][j];
				if(Map[i][j]=='S')
					Start_x=i,Start_y=j;    //保存初始位置
				else if(Map[i][j]=='E')
					End_x=i,End_y=j;        //保存最终位置
			}	
		book[Start_x][Start_y]=1;
		Dfs(Start_x,Start_y,0);    
		if(Min)
			cout<<Min<<endl;
		else
			cout<<"-1"<<endl;
	}
	return 0;
}