迷宫中离入口最近的出口

题目链接

迷宫中离入口最近的出口

题目描述

注意点

• maze[i][j] 要么是 ‘.’ ，要么是 ‘+’
• entrance.length == 2
• entrance 一定是空格子
• 出口的含义是 maze 边界上的空格子
• entrance格子不算出口

解答思路

• 广度优先遍历找到走i步时所能到达的所有节点位置（相同位置多次遍历需要排除，所以需要使用二维数组visited存储已经到达过的节点）。使用队列存储第i步所能到达的所有位置，先将入口入队，可以向上下左右四个方向进行移动（前提是未出界，移动的位置不是墙，移动的位置没有被遍历过），重复上述过程，直到找到出口或队列中没有元素为止
• 需要注意的是在移动到新的位置（x, y）将该位置添加到队列时也要同步将visted[x][y]标记为true，而不是出队时才标记，因为相同步数可能由上一步多个点到达该位置，可能会做多次入队出队操作（与一次入队出队操作相同），效率很低

代码

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        int res = 0;
        int row = maze.length;
        int col = maze[0].length;
        int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean[][] visited = new boolean[row][col];
        Deque<int[]> deque = new ArrayDeque<>();
        deque.offerLast(new int[]{entrance[0], entrance[1]});
        visited[entrance[0]][entrance[1]] = true;
        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] loc = deque.pollFirst();
                int x = loc[0], y = loc[1];
                if (isExport(x, y, row, col, entrance)) {
                    return res;
                }
                // 朝着四个方向前进
                for (int j = 0; j < direction.length; j++) {
                    int newX = x + direction[j][0], newY = y + direction[j][1];
                    // 移动的格子未出界、不是墙、未遍历过
                    if (newX >= 0 && newX < row && newY >= 0 && newY < col 
                        && maze[newX][newY] == '.' && !visited[newX][newY]) {
                        deque.offerLast(new int[]{newX, newY});
                        // 入队立马标记为已遍历，防止同一层遍历多次相同位置
                        visited[newX][newY] = true;
                    }
                }
            }
            res++;
        }
        return -1;
    }

    public boolean isExport(int x, int y, int row, int col, int[] entrance) {
        if (x == entrance[0] && y == entrance[1]) {
            return false;
        }
        return x == 0 || y == 0 || x == row - 1 || y == col - 1;
    }
}

关键点

• 入口不能作为出口
• 广度优先遍历的思想
• 在朝着四个方向前进时，哪些位置不能到达
• 在到达新位置时，入队的同时还要将visited标记为true