题解 | #走迷宫#

广度优先遍历，是一种 层次遍历。它从 起点 开始，从上往下、从左到右 进行遍历。这种层次遍历，可以确保起点到终点的路径是 最短的。最坏情况下，也就是将所有的节点遍历一次，才能找到 终点。但是呢，广度优先遍历不太适用于找 路径的条数，归根结底，还是因为一般的 层次遍历，节点只知道自己 当前所在的层次，并不知道自己是由哪一个节点过来的

1. 判断是两个坐标是否相同，相同返回零
2. bfs广度优先搜索，用while循环将新创建的steps[][]进行层次遍历迭代
3. 判断目标坐标内容是否发生改变，如果没有，那么无法bsf到该目标坐标，返回-1

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Main obj = new Main();
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        int m = in.nextInt();
        int x_s = in.nextInt() - 1;
        int y_s = in.nextInt() - 1;
        int x_t = in.nextInt() - 1;
        int y_t = in.nextInt() - 1;
        char[][] str = new char[n][m];
        for (int i = 0; i < n; i++) {
            String s = in.next();
            for (int j = 0; j < m; j++) {

                str[i][j] = s.charAt(j);
            }
        }
        if (x_s == x_t && y_s == y_t) {
            System.out.println(0);
            return;
        }
        if(str[x_t][y_t]=='*'){
            System.out.println(-1);
            return;
        }
        int[][] steps = new int[n][m];
        steps[x_s][y_s] = 0;
       Queue<int[]> queue = new LinkedList<>();
        int i = x_s;
        int j = y_s;
        int[] tmp = new int[] {x_s, y_s};
        queue.add(tmp);
        while (!queue.isEmpty()) {
            tmp = queue.poll();
            if (tmp[0] - 1 >= 0 && str[tmp[0] - 1][tmp[1]] == '.') {
                steps[tmp[0] - 1][tmp[1]] = steps[tmp[0]][tmp[1]] + 1;
                int[] loc = new int[] {tmp[0] - 1, tmp[1]};
                queue.add(loc);
                str[tmp[0] - 1][tmp[1]] = '-';
            }
            if (tmp[0] + 1 < n && str[tmp[0] + 1][tmp[1]] == '.') {
                steps[tmp[0] + 1][tmp[1]] = steps[tmp[0]][tmp[1]] + 1;
                int[] loc = new int[] {tmp[0] + 1, tmp[1]};
                queue.add(loc);
                str[tmp[0] + 1][tmp[1]] = '-';
            }
            if (tmp[1] - 1 >= 0 && str[tmp[0] ][tmp[1] - 1] == '.') {
                steps[tmp[0]][tmp[1] - 1] = steps[tmp[0]][tmp[1]] + 1;
                int[] loc = new int[] {tmp[0], tmp[1] - 1};
                queue.add(loc);
                str[tmp[0] ][tmp[1]-1] = '-';
            }
            if (tmp[1] + 1 < m && str[tmp[0] ][tmp[1] + 1] == '.') {
                steps[tmp[0] ][tmp[1] + 1] = steps[tmp[0]][tmp[1]] + 1;
                int[] loc = new int[] {tmp[0], tmp[1] + 1};
                queue.add(loc);
                str[tmp[0]][tmp[1]+1] = '-';
            }
        }
        if(str[x_t][y_t]=='.'){
            System.out.println(-1);
            return;
        }

        System.out.println(steps[x_t][y_t]);
    }
}