Maze Problem

Given a maze, find a shortest path from start to goal.

Input consists serveral test cases.

First line of the input contains number of test case T.

For each test case the first line contains two integers N , M ( 1 <= N, M <= 100 ).

Each of the following N lines contain M characters. Each character means a cell of the map.

Here is the definition for chracter.

Constraint:

For a character in the map:

‘S’ : start cell

‘E’ : goal cell

‘-’ : empty cell

‘#’ : obstacle cell

no two start cell exists.

no two goal cell exists.

For each test case print one line containing shortest path. If there exists no path from start to goal, print -1.

INPUT
1
5 5
S-###
-----
##---
E#---
---##

OUTPUT
9

这是一道典型的用bfs求最短路的题（也挺简单的），这道题千万不要用dfs，因为dfs是求不了最短路的，只能单纯地搜索，但是bfs就不一样了，bfs搜索完以后，就自动求出了最短路。

#include<bits/stdc++.h>
using namespace std;
char e[101][101];   //存图
int t,n,m,vis[101][101],sx,sy,ex,ey,tx,ty;   //vis记录到vis[i][j]用的步数
int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};   //移动的四个方向
struct node   //结构体存入队的每个点的坐标
{
	int x,y;
};
queue<node> q;    //建立一个队列
void bfs()
{
	while(!q.empty())   //如果队列不为空，一直循环
	{
		for(int i=0;i<4;i++)
		{
			tx=q.front().x+move[i][0];
			ty=q.front().y+move[i][1];
			if(!vis[tx][ty]&&e[tx][ty]!='#'&&tx>=0&&tx<n&&ty>=0&&ty<m)   //如果满足条件
			{
				vis[tx][ty]=vis[q.front().x][q.front().y]+1;   //这个点由上一个点一步到达，所以加一
				q.push({tx,ty});   //再把相邻的点入队
			}
		}
		q.pop();   //操作完，把队首出队
	}
}
int main()
{
	cin>>t;
	while(t--)
	{
		memset(vis,0,sizeof(vis));
		cin>>n>>m;
		for(int i=0;i<n;i++)	scanf("%s",e[i]);
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(e[i][j]=='S')	sx=i,sy=j;  //找到起点
				if(e[i][j]=='E')	ex=i,ey=j;  //找到终点
			}
		}
		q.push({sx,sy});   //首先把起点入队
		vis[sx][sy]=1;     //让起点为1，防止0重复访问
		bfs(); 
		cout<<vis[ex][ey]-1<<endl;   //因为最开始起点加一，所以最后答案减一
	}
	return 0;
}