Problem of The Day: Nearest Exit from Entrance in Maze

Problem Statement

leetcode problem link

My Solution [Accepted]

public class Solution {
    public static (int dx, int dy)[] Directions { get;} = {
        (0,1), (0,-1), (1,0), (-1,0)
    };

    public int NearestExit(char[][] maze, int[] entrance) {
        int ROWS = maze.Length;
        int COLS = maze[0].Length;
        int row = entrance[0];
        int col = entrance[1];
        Queue<(int, int, int)> queue = new Queue<(int, int ,int)>();
        queue.Enqueue((row, col, 0));
        maze[row][col] = '+'; // Ensure we don't go back to the start
        while (queue.Count > 0) {
            var (r, c, steps) = queue.Dequeue();

            foreach (var (dx, dy) in Directions) {
                var newRow = r + dx;
                var newCol = c + dy;

                if ((newRow >= 0 && newRow < ROWS) && (newCol >= 0 && newCol <COLS)
                    && maze[newRow][newCol] == '.') {

                    if (newRow == 0 || newRow == ROWS - 1 || newCol == 0 || newCol == COLS - 1) {
                        return steps + 1;
                    }
                    queue.Enqueue((newRow, newCol, steps + 1));
                    maze[newRow][newCol] = '+'; // mark as visited immediately to prevent out of memory
                }
            }
        }

        return -1;
    }
}

Editorial

Approach: Breadth First Search (BFS)

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        rows, cols = len(maze), len(maze[0])
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

        # Mark the entrance as visited since its not a exit.
        start_row, start_col = entrance
        maze[start_row][start_col] = "+"

        # Start BFS from the entrance, and use a queue `queue` to store all
        # the cells to be visited.
        queue = collections.deque()
        queue.append([start_row, start_col, 0])

        while queue:
            curr_row, curr_col, curr_distance = queue.popleft()

            # For the current cell, check its four neighbor cells.
            for d in dirs:
                next_row = curr_row + d[0]
                next_col = curr_col + d[1]

                # If there exists an unvisited empty neighbor:
                if 0 <= next_row < rows and 0 <= next_col < cols \
                    and maze[next_row][next_col] == ".":

                    # If this empty cell is an exit, return distance + 1.
                    if 0 == next_row or next_row == rows - 1 or 0 == next_col or next_col == cols - 1:
                        return curr_distance + 1

                    # Otherwise, add this cell to 'queue' and mark it as visited.
                    maze[next_row][next_col] = "+"
                    queue.append([next_row, next_col, curr_distance + 1])

        # If we finish iterating without finding an exit, return -1.
        return -1