迷宫问题-题解（Java代码）

解题思路:
本题使用深度优先搜索会超时，所以使用广度优先搜索，也叫作宽度优先搜索。

深搜与广搜相似，都是“穷竭搜索”。但他们也有不同之处，不同之处在于搜索的顺序。

广搜总是先搜索距离初始状态最近的状态。也就是说，

它时按照开始状态 ->只需1次就可以到达的所有状态
->只需2次就可以到达的所有状态……这样的顺序进行搜索。

对于同一个状态，广度优先搜索只经过一次，

因此复杂度为O(状态数 X 转移的方式)。

深搜（隐式地）利用了栈（后进先出）进行计算，而广搜则利用了队列(先进后出)。

搜索时首先将初始状态添加到队列里，此后从队列的最前端不断取出状态，把从该状态可以转移到的状态中尚未访问过的部分加入队列，

如此往复，直到队里被取空了找到了问题的解。

宽度优先搜索按照距离初始状态由近及远的顺序进行搜索，因此比较适合求最短路径、最少操作之类的问题。

在这个问题中，我们构造一个Q类 用来存储x，y，dept，分别是坐标(x,y) 第dept步。

因为要向四个方向移动，用 int next[][]={{0,1},{1,0},{0,-1},{-1,0}};来表示四个方向，这样可以通过循环来实现四个方向的移动遍历。

在向四个方向遍历移动前，去除队列最前端的元素，判断是否是终点。如果是，则程序结束，得到结果。

在向四个方向移动中，还是和dfs一样的判断，判断是否越界，是否可以通过，是否未走过，这里需要注意的是广搜不需要取消走过的标记，

因为广搜是一层层的搜索，而不用回溯。

在向四个方向移动中，如果可以移动，那么将下一个点加入到队列的结尾，并且步数加一。

参考代码:

import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
	public static class Q{
		int x;
		int y;
		int dept;//当前步数
	}
    public static void main(String[] args) {
        //队列，queue，先进先出
    		//在java中，LinkedList实现 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
    		//所以本题用LinkedList代替Queue。
    	//bfs.广度优先搜索，层层递进
    	//使用队列存储起点，        
    	//遍历四个方向，如果新方向可以走
    		//则将新方向存储到队列
    	//当四个方向遍历完成后，将首个出列 poll()，并得到首列的元素。重复上一步，即向四个方向遍历。
    	//假如遍历到某个点时，刚好是终点，那么结束循环，这就是结果。
        Scanner sc=new Scanner(System.in);
        int next[][]={{0,1},{1,0},{0,-1},{-1,0}};//下一步
        int t=sc.nextInt();
        while (t-->0) {//组数
			int n=sc.nextInt();
			int m=sc.nextInt();
			int sx=0,sy=0;//起点坐标
			int gx=0,gy=0;//终点坐标
			LinkedList<Q> que=new LinkedList<Main.Q>();
			char arr[][]=new char[n][m];
			int flag[][]=new int[n][m];//标记是否走过
			
			//输入
			for (int i = 0; i < n; i++) {
				String str=sc.next();
				for (int j = 0; j <str.length(); j++) {
					arr[i][j]=str.charAt(j);
					if (arr[i][j]=='S') {//起点
						sx=i;sy=j;
					}
					if (arr[i][j]=='E') {//终点
						gx=i;gy=j;
					}
				}
			}
			//开始广搜
			flag[sx][sy]=1;//标记开始坐标
			Q q=new Q();//初始化开始坐标
			q.x=sx;
			q.y=sy;
			q.dept=0;
			que.add(q);//添加
			int finish=0,result=0;
			while (que.size()!=0) {
				Q first=que.poll();//取出头列，并删除
				if (first.x==gx && first.y==gy) {
					finish=1;
					result=first.dept;
					break;
				}
				for (int i = 0; i <4; i++) {//右下左上 4 个步骤
					//如果已经到达终点，那么退出循环，并且得到结果
					int tx=first.x+next[i][0];
					int ty=first.y+next[i][1];
					if (tx>=0 && tx<n && ty>=0 && ty<m 
						&& arr[tx][ty]!='#' && flag[tx][ty]==0) {//符合条件
						flag[tx][ty]=1;//标记走过
						Q temp=new Q();
						temp.x=tx;
						temp.y=ty;
						temp.dept=first.dept+1;
						que.add(temp);//添加一个坐标到队列
					}
				}
				if (finish==1) {//如果已经得到结果，那么直接退出
					break;
				}
			}
			//输出结果
			if (result==0) {
				System.out.println("-1");
			}else {
				System.out.println(result);
			}
		}
       
        
}
  
}