1926. 迷宫中离入口最近的出口【广度优先搜索】

1926. 迷宫中离入口最近的出口

class Solution {  //java  广度优先搜索
    public int nearestExit(char[][] maze, int[] entrance) {
        int rows = maze.length - 1;
        int cols = maze[0].length - 1;
        int[][] directions = new int[][] { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
        Queue que = new ArrayDeque<>();
        que.offer(new int[] { entrance[0], entrance[1], 0 });  //加入队列,不是 xy坐标系的xy，是行列
        maze[entrance[0]][entrance[1]] = '+';  //修改为墙
        while (!que.isEmpty()) {
            int[] cur = que.poll();  // 取出数组，并删除！
            int row = cur[0]; 
            int col = cur[1];
            int step = cur[2];
            for (int i = 0; i < 4; ++i) {
                int nextRow = row + directions[i][0];  //走四个方向
                int nextCol = col + directions[i][1];                  //判断四个方向哪个能进入
                if (nextRow >= 0 && nextRow <= rows && nextCol >= 0 && nextCol <= cols && maze[nextRow][nextCol] == '.') { 
                    if (nextRow == 0 || nextRow == rows || nextCol ==0 || nextCol == cols) {  //到出口了
                        return step + 1;
                    } 
                    maze[nextRow][nextCol] = '+';
                    que.add(new int[] {nextRow, nextCol, step + 1});  // 最短路径的步数
                }
            }
        }
        return -1;
    }
}