迷宫问题 （Java代码）

解题思路:

广度优先搜索

注意事项:

参考代码:

import java.util.ArrayList;
import java.util.Scanner;

public class T1672 {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		while(T-->0){
			int N = in.nextInt(),M = in.nextInt();
			char map[][] = new char[N+1][M+1];//迷宫
			boolean visit[][] = new boolean[N+1][M+1];//是否被访问
			int length[][] = new int[N+1][M+1];//长度记录
			Point start = new Point(0,0);
			Point end = new Point(0,0);
			int ans = -1;
			int [][]dir = {{-1,0},{1,0},{0,-1},{0,1}};
			for(int i = 1;i<=N;i++){
				String s = in.next();
				for(int j = 1;j<=M;j++){
					map[i][j] = s.charAt(j-1);
					if(map[i][j] == 'S') 
						start.set_xy(i, j);
					else if(map[i][j] == 'E')
						end.set_xy(i, j);
				}
			}
			ArrayList<Point> queue = new ArrayList<Point>();
			queue.add(start);
			length[start.x][start.y] = 0;
			visit[start.x][start.y] = true;
s:			while(!queue.isEmpty()){
				for(int i = 0;i<4;i++){
					Point tmp = new Point(queue.get(0).x + dir[i][0],
										  queue.get(0).y + dir[i][1]);
					if(tmp.x>0&&tmp.x<=N&&tmp.y>0&&tmp.y<=M&&map[tmp.x][tmp.y] != '#'&&visit[tmp.x][tmp.y]==false){
						if(map[tmp.x][tmp.y] == 'E'){
							ans = length[queue.get(0).x][queue.get(0).y]+1;
							break s;
						}
						visit[tmp.x][tmp.y] = true;
						queue.add(tmp);
						length[tmp.x][tmp.y] = length[queue.get(0).x][queue.get(0).y]+1;
					}
				}
				queue.remove(0);
			}
			System.out.println(ans);
		}
		in.close();
	}
}
class Point{
	int x;
	int y;
	public Point(int x,int y){
		this.x = x;
		this.y = y;
	}
	public void set_xy(int x,int y){
		this.x = x;
		this.y = y;
	}
}