Sponsored
Sponsored
In this approach, we use the Breadth-First Search (BFS) algorithm to explore the maze. BFS is suitable because it explores nodes layer by layer, ensuring that the shortest path is found. We initialize a queue with the entrance cell and explore its neighbors (up, down, left, right). If a neighbor is an unvisited empty cell and is on the boundary (except the entrance), it can be considered as an exit.
Each time we explore a cell, we mark it as visited by changing its state to '+'. This prevents revisiting nodes, which ensures that we won't traverse the same path multiple times. We keep track of steps taken from the entrance to the current cell, and if we reach an exit, we return the number of steps. If the queue is exhausted without finding an exit, we return -1.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the maze. In the worst case, all cells are traversed.
Space Complexity: O(m * n) for the queue used in BFS.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int NearestExit(char[][] maze, int[] entrance) {
6 int m = maze.Length, n = maze[0].Length;
7 Queue<int[]> queue = new Queue<int[]>();
8 queue.Enqueue(new int[] { entrance[0], entrance[1] });
9 maze[entrance[0]][entrance[1]] = '+';
10 int[][] directions = new int[4][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };
11 int steps = 0;
12
13 while (queue.Count > 0) {
steps++;
int size = queue.Count;
for (int i = 0; i < size; i++) {
int[] cell = queue.Dequeue();
foreach (var d in directions) {
int nx = cell[0] + d[0], ny = cell[1] + d[1];
if (nx >= 0 && ny >= 0 && nx < m && ny < n && maze[nx][ny] == '.') {
if (nx == 0 || ny == 0 || nx == m - 1 || ny == n - 1) {
return steps;
}
maze[nx][ny] = '+';
queue.Enqueue(new int[] { nx, ny });
}
}
}
}
return -1;
}
}The C# implementation also uses a queue to perform BFS, with similar logic to other implementations. It processes each cell's possible moves and checks if any lead to the nearest exit by counting steps. If none are found after traversing the grid, it returns -1.
In this approach, we use the Depth-First Search (DFS) algorithm to explore the maze. DFS might not be as efficient as BFS for finding the shortest path, but for educational purposes, it demonstrates another way to traverse the maze. We recursively explore each path, marking cells as visited and backtracking when dead-ends or exits are encountered.
This approach keeps a global minimum step count, updating it whenever an exit (that isn't the entrance) is found. Through recursive calls, each possible path is explored until all directions are exhausted. The main objective is to identify the closest exit with respect to steps taken from the entrance cell.
Time Complexity: O((m * n)^2) in the worst case, where m and n are dimensions of the maze.
Space Complexity: O(m * n) due to recursion stack usage in deep recursive path exploration.
1#include <vector>
2#include <climits>
3using namespace std;
4
5void dfs(vector<vector<char>>& maze, int x, int y, int steps, int &minSteps) {
6 static vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
7 int m = maze.size(), n = maze[0].size();
8 if (x < 0 || y < 0 || x >= m || y >= n || maze[x][y] != '.') return;
9 if ((x == 0 || y == 0 || x == m - 1 || y == n - 1) && steps != 0) {
10 minSteps = min(minSteps, steps);
11 }
12 maze[x][y] = '+'; // mark as visited
13 for (auto& d : directions) {
14 int nx = x + d[0], ny = y + d[1];
15 dfs(maze, nx, ny, steps + 1, minSteps);
16 }
17 maze[x][y] = '.'; // backtrack
18}
19
20int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
21 int minSteps = INT_MAX;
22 dfs(maze, entrance[0], entrance[1], 0, minSteps);
23 return (minSteps == INT_MAX) ? -1 : minSteps;
24}A recursive DFS in C++ checks each grid point. Each direction from a current node is pursued recursively, with path steps counted. Whenever an exit is found on the boundary (that is not the entrance point), the global minimum is updated. Dead-ends and invalid paths lead to backtracking.