Dare2Solve
The problem involves navigating through a maze to find the nearest exit. Given a maze represented as a grid of cells, with some cells containing walls ('+'
) and others being empty ('.'
), the task is to find the shortest path from a given entrance to the nearest exit. An exit is defined as an empty cell on the boundary of the maze that is not the entrance.
The most efficient way to find the shortest path in an unweighted grid is by using a Breadth-First Search (BFS). BFS explores all possible moves level by level, ensuring that the first time it reaches an exit, that path is the shortest one. By pushing all possible exits into a queue initially and then performing BFS, we can efficiently determine the shortest path from the entrance to the nearest exit.
(O(n \times m)), where (n) is the number of rows and (m) is the number of columns in the maze. This is because in the worst case, we might need to check every cell in the maze.
(O(n \times m)), due to the storage required for the queue and the visited map used during the BFS traversal.
class Solution {
public:
int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
vector<tuple<int, int, int>> st;
int rows = maze.size();
int cols = maze[0].size();
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (maze[i][j] == '.' && (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && !isEquals(vector<int>{i, j}, entrance)) {
st.push_back({i, j, 0});
}
}
}
return bfs(st, maze, entrance);
}
private:
bool isEquals(const vector<int>& a, const vector<int>& b) {
return a[0] == b[0] && a[1] == b[1];
}
int bfs(vector<tuple<int, int, int>>& st, vector<vector<char>>& maze, vector<int>& start) {
vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
unordered_map<int, unordered_map<int, bool>> visited;
while (!st.empty()) {
auto [row, col, len] = st.front();
st.erase(st.begin());
visited[row][col] = true;
for (auto& dir : directions) {
int r = row + dir[0];
int c = col + dir[1];
if (isEquals(vector<int>{r, c}, start)) return len + 1;
if (r < 0 || c < 0 || r >= maze.size() || c >= maze[0].size() || maze[r][c] == '+' || visited[r][c]) continue;
st.push_back({r, c, len + 1});
visited[r][c] = true;
}
}
return -1;
}
};
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
st = []
rows, cols = len(maze), len(maze[0])
for i in range(rows):
for j in range(cols):
if maze[i][j] == "." and (i == 0 or i == rows - 1 or j == 0 or j == cols - 1) and [i, j] != entrance:
st.append((i, j, 0))
return self.bfs(st, maze, entrance)
def isEquals(self, a: List[int], b: List[int]) -> bool:
return a[0] == b[0] and a[1] == b[1]
def bfs(self, st: List[tuple], maze: List[List[str]], start: List[int]) -> int:
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
visited = set()
while st:
row, col, length = st.pop(0)
visited.add((row, col))
for r_offset, c_offset in directions:
r, c = row + r_offset, col + c_offset
if [r, c] == start:
return length + 1
if r < 0 or c < 0 or r >= len(maze) or c >= len(maze[0]) or maze[r][c] == "+" or (r, c) in visited:
continue
st.append((r, c, length + 1))
visited.add((r, c))
return -1
class Solution {
public int nearestExit(char[][] maze, int[] entrance) {
List<int[]> st = new ArrayList<>();
int rows = maze.length;
int cols = maze[0].length;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (maze[i][j] == '.' && (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) && !isEquals(new int[]{i, j}, entrance)) {
st.add(new int[]{i, j, 0});
}
}
}
return bfs(st, maze, entrance);
}
private boolean isEquals(int[] a, int[] b) {
return a[0] == b[0] && a[1] == b[1];
}
private int bfs(List<int[]> st, char[][] maze, int[] start) {
int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
Set<String> visited = new HashSet<>();
while (!st.isEmpty()) {
int[] cur = st.remove(0);
int row = cur[0], col = cur[1], len = cur[2];
visited.add(row + "," + col);
for (int[] dir : directions) {
int r = row + dir[0];
int c = col + dir[1];
if (isEquals(new int[]{r, c}, start)) return len + 1;
if (r < 0 || c < 0 || r >= maze.length || c >= maze[0].length || maze[r][c] == '+' || visited.contains(r + "," + c)) continue;
st.add(new int[]{r, c, len + 1});
visited.add(r + "," + c);
}
}
return -1;
}
}
var nearestExit = function (maze, entrance) {
let st = []
for (let i = 0; i < maze.length; i++) {
for (let j = 0; j < maze[0].length; j++) {
if (maze[i][j] == "." && (i == 0 || i == maze.length - 1 || j == 0 || j == maze[0].length - 1) && !isEquals([i, j], entrance)) {
st.push([i, j, 0])
}
}
}
return bfs(st, maze, entrance)
};
function isEquals(a, b) {
return a[0] == b[0] && a[1] == b[1]
}
function bfs(st, maze, start) {
let directions = [[0, 1], [0, -1], [1, 0], [-1, 0]], visited = {}
while (st.length) {
const [row, col, len] = st.shift()
visited[[row, col]] = 1
for (let i of directions) {
let r = row + i[0], c = col + i[1]
if (isEquals([r, c], start)) return len + 1
if (r < 0 || c < 0 || r > maze.length - 1 || c > maze[0].length - 1 || maze[r][c] == "+" || visited[[r, c]]) continue
st.push([r, c, len + 1])
visited[[r, c]] = 1
}
}
return -1
}