LeetCode: 1926-Nearest Exit from Entrance in Maze 解題紀錄

Last Updated on 2022-11-21 by Clay

題目

You are given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'). You are also given the entrance of the maze, where entrance = [entrancerow, entrancecol] denotes the row and column of the cell you are initially standing at.

In one step, you can move one cell up, down, left, or right. You cannot step into a cell with a wall, and you cannot step outside the maze. Your goal is to find the nearest exit from the entrance. An exit is defined as an empty cell that is at the border of the maze. The entrance does not count as an exit.

Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.

Example 1:

Input: maze = [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2]
Output: 1
Explanation: There are 3 exits in this maze at [1,0], [0,2], and [2,3].
Initially, you are at the entrance cell [1,2].
- You can reach [1,0] by moving 2 steps left.
- You can reach [0,2] by moving 1 step up.
It is impossible to reach [2,3] from the entrance.
Thus, the nearest exit is [0,2], which is 1 step away.

Example 2:

Input: maze = [["+","+","+"],[".",".","."],["+","+","+"]], entrance = [1,0]
Output: 2
Explanation: There is 1 exit in this maze at [1,2].
[1,0] does not count as an exit since it is the entrance cell.
Initially, you are at the entrance cell [1,0].
- You can reach [1,2] by moving 2 steps right.
Thus, the nearest exit is [1,2], which is 2 steps away.

Example 3:

Input: maze = [[".","+"]], entrance = [0,0]
Output: -1
Explanation: There are no exits in this maze.

Constraints:

• maze.length == m
• maze[i].length == n
• 1 <= m, n <= 100
• maze[i][j] is either '.' or '+'.
• entrance.length == 2
• 0 <= entrancerow < m
• 0 <= entrancecol < n
• entrance will always be an empty cell.

題目會給定一張迷宮、起始座標，然後讓你判斷最短抵達迷宮出口的步數是多少？

迷宮出口的定義就是接觸到迷宮的邊界、該邊界並非牆壁，牆壁是不能走的。另外，出發點不能是出口。

---

解題思路

迷宮探路的題目會很直覺地想到使用 BFS 來找到最近的出口，因為 BFS 是一層層地往外去探索可能性，找到的第一個出口也就會是最短的路線。

C++ 範例程式碼

class Solution {
public:    
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        // Offset
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        
        // Init
        int steps = 0;
        int _x = entrance[0];
        int _y = entrance[1];
        
        int width = maze.size();
        int height = maze[0].size();
        
        queue<pair<int, int>> q;
        q.push({_x, _y});
        
        vector<vector<bool>> isVisited(width, vector<bool>(height, 0));
        isVisited[_x][_y] = 1;
        
        // BFS
        while (!q.empty()) {
            int size = q.size();
            ++steps;
            
            while (size) {
                --size;
                
                _x = q.front().first;
                _y = q.front().second;
                q.pop();
                
                for (int i=0; i<4; ++i) {
                    int new_x = _x + dx[i];
                    int new_y = _y + dy[i];
                    
                    // Out of the boundary
                    if (new_x < 0 || new_y < 0 || new_x >= width || new_y >= height) {
                        continue;
                    }
                    
                    // Wall or is visited
                    if (maze[new_x][new_y] == '+' || isVisited[new_x][new_y]) {
                        continue;
                    }
                    
                    // Reach the exit
                    if (new_x == 0 || new_y == 0 || new_x == width-1 || new_y == height-1) {
                        return steps;
                    }
                    
                    isVisited[new_x][new_y] = 1;
                    q.push({new_x, new_y});
                }
            }
        }
        
        return -1;
    }
};

Python 範例程式碼

class Solution {
public:    
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        // Offset
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        
        // Init
        int steps = 0;
        int _x = entrance[0];
        int _y = entrance[1];
        
        int width = maze.size();
        int height = maze[0].size();
        
        queue<pair<int, int>> q;
        q.push({_x, _y});
        
        vector<vector<bool>> isVisited(width, vector<bool>(height, 0));
        isVisited[_x][_y] = 1;
        
        // BFS
        while (!q.empty()) {
            int size = q.size();
            ++steps;
            
            while (size) {
                --size;
                
                _x = q.front().first;
                _y = q.front().second;
                q.pop();
                
                for (int i=0; i<4; ++i) {
                    int new_x = _x + dx[i];
                    int new_y = _y + dy[i];
                    
                    // Out of the boundary
                    if (new_x < 0 || new_y < 0 || new_x >= width || new_y >= height) {
                        continue;
                    }
                    
                    // Wall or is visited
                    if (maze[new_x][new_y] == '+' || isVisited[new_x][new_y]) {
                        continue;
                    }
                    
                    // Reach the exit
                    if (new_x == 0 || new_y == 0 || new_x == width-1 || new_y == height-1) {
                        return steps;
                    }
                    
                    isVisited[new_x][new_y] = 1;
                    q.push({new_x, new_y});
                }
            }
        }
        
        return -1;
    }
};

---

References

• 1926. Nearest Exit from Entrance in Maze

---

Read More

• LeetCode 解題紀錄目錄