不同于深度优先遍历，先找一个子节点，再找子节点的子节点...
广度优先遍历会挨着子节点遍历，第一层的子节点遍历完了，才会遍历第二层；如图：
bfs(起点){ 起点加入队列； while (队列!=空) { 得到队首x； 删除队首; for(遍历X的子节点){ 子节点加入队列尾； } } }所以说，用广度优先 先访问到的目标一定是 层数最少的--路径最短的；
所以走迷宫求最短路径可以这么写：
#代表障碍物，S代表起点；T代表中点；
其中最短路径可以用结点的路径来记录；
public class 走迷宫最小步数 { static String map[]; static boolean[][] visit; static int dir[][] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; //对应的上下左右4各方向 static int n; static int m; public static void main(String[] args) { // TODO Auto-generated method stub Scanner input = new Scanner(System.in); n = input.nextInt(); m = input.nextInt(); map = new String[n]; visit = new boolean[n][m]; for (int i = 0; i < n; i++) { map[i] = input.next(); } int x = 0, y = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (map[i].charAt(j) == 'S') { x = i; y = j; } } } Points point = new Points(x, y);//静态方法 调用非静态的内部类报错； bfs(point); } private static void bfs(Points point) { // TODO Auto-generated method stub Queue<Points> queue = new LinkedList<Points>(); queue.add(point); visit[point.getX()][point.getY()]=true; while (!queue.isEmpty()) { Points father = queue.poll(); int headx = father.getX(); int heady = father.getY(); for (int i = 0; i < dir.length; i++) { int x = headx+dir[i][0]; int y = heady+dir[i][1]; Points son = new Points(x, y); if ((-1 < x && x < n) && (-1 < y && y < m)) { if (visit[x][y]==false) { if (map[x].charAt(y) == '#') { visit[x][y]=true; continue; }else if (map[x].charAt(y) == 'T') { int count =1; while (!(father.getX()==point.getX()&&father.getY()==point.getY())) { father = father.getFathrpoint(); count++; } System.out.println(count); return; }else { visit[x][y]=true; son.setFathrpoint(father); queue.add(son); } } } } } System.out.println("-1"); } static class Points{ int x; int y; Points fathrpoint; public Points getFathrpoint() { return fathrpoint; } public void setFathrpoint(Points fathrpoint) { this.fathrpoint = fathrpoint; } public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } protected Points(int x,int y){ this.x=x; this.y=y; } } }
