Welcome to Subscribe On Youtube
1926. Nearest Exit from Entrance in Maze
Description
You are given an m x n
matrix maze
(0indexed) with empty cells (represented as '.'
) and walls (represented as '+'
). You are also given the entrance
of the maze, where entrance = [entrance_{row}, entrance_{col}]
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 <= entrance_{row} < m
0 <= entrance_{col} < n
entrance
will always be an empty cell.
Solutions
BFS.

class Solution { public int nearestExit(char[][] maze, int[] entrance) { int m = maze.length; int n = maze[0].length; Deque<int[]> q = new ArrayDeque<>(); q.offer(entrance); maze[entrance[0]][entrance[1]] = '+'; int ans = 0; int[] dirs = {1, 0, 1, 0, 1}; while (!q.isEmpty()) { ++ans; for (int k = q.size(); k > 0; k) { int[] p = q.poll(); int i = p[0], j = p[1]; for (int l = 0; l < 4; ++l) { int x = i + dirs[l], y = j + dirs[l + 1]; if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') { if (x == 0  x == m  1  y == 0  y == n  1) { return ans; } q.offer(new int[] {x, y}); maze[x][y] = '+'; } } } } return 1; } }

class Solution { public: int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) { int m = maze.size(), n = maze[0].size(); queue<vector<int>> q{ {entrance} }; maze[entrance[0]][entrance[1]] = '+'; int ans = 0; vector<int> dirs = {1, 0, 1, 0, 1}; while (!q.empty()) { ++ans; for (int k = q.size(); k > 0; k) { auto p = q.front(); q.pop(); for (int l = 0; l < 4; ++l) { int x = p[0] + dirs[l], y = p[1] + dirs[l + 1]; if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.') { if (x == 0  x == m  1  y == 0  y == n  1) return ans; q.push({x, y}); maze[x][y] = '+'; } } } } return 1; } };

class Solution: def nearestExit(self, maze: List[List[str]], entrance: List[int]) > int: m, n = len(maze), len(maze[0]) i, j = entrance q = deque([(i, j)]) maze[i][j] = '+' ans = 0 while q: ans += 1 for _ in range(len(q)): i, j = q.popleft() for a, b in [[0, 1], [0, 1], [1, 0], [1, 0]]: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and maze[x][y] == '.': if x == 0 or x == m  1 or y == 0 or y == n  1: return ans q.append((x, y)) maze[x][y] = '+' return 1

func nearestExit(maze [][]byte, entrance []int) int { m, n := len(maze), len(maze[0]) q := [][]int{entrance} maze[entrance[0]][entrance[1]] = '+' ans := 0 dirs := []int{1, 0, 1, 0, 1} for len(q) > 0 { ans++ for k := len(q); k > 0; k { p := q[0] q = q[1:] for l := 0; l < 4; l++ { x, y := p[0]+dirs[l], p[1]+dirs[l+1] if x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' { if x == 0  x == m1  y == 0  y == n1 { return ans } q = append(q, []int{x, y}) maze[x][y] = '+' } } } } return 1 }