Nearest Exit from Entrance in Maze

class Solution {
public:
    int findNearestExit(vector<vector<char>>& grid, vector<int>& entry) {
        int height = grid.size(), width = grid[0].size();
        vector<pair<int, int>> moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        int startX = entry[0], startY = entry[1];
        grid[startX][startY] = '+';
        
        queue<array<int, 3>> bfsQueue;
        bfsQueue.push({startX, startY, 0});
        
        while (!bfsQueue.empty()) {
            auto [currentRow, currentCol, steps] = bfsQueue.front();
            bfsQueue.pop();
            
            for (auto &move : moves) {
                int new_row = currentRow + move.first;
                int new_col = currentCol + move.second;

                if (new_row >= 0 && new_row < height && new_col >= 0 && new_col < width 
                    && grid[new_row][new_col] == '.') {

                    if (new_row == 0 || new_row == height - 1 || new_col == 0 || new_col == width - 1)
                        return steps + 1;

                    grid[new_row][new_col] = '+';
                    bfsQueue.push({new_row, new_col, steps + 1});
                }
            }
        }

        return -1;
    }
};

The provided C++ code defines a solution for finding the shortest path to the nearest exit from a given entrance in a maze, using the Breadth-First Search (BFS) technique. Here is a breakdown of the solution:

• The maze is represented as a vector<vector<char>> where spaces ('.') indicate open paths and '+' signs are blocking elements after being visited, preventing revisits.
• The function findNearestExit receives the maze grid and the starting position entry as parameters.
• Essential BFS components implemented:
  • A queue to store the BFS frontier with each element including the current position and the step count.
  • Direction vectors (moves) to navigate up, down, left, or right in the maze.
• The BFS starts from the entry point, marking it initially to prevent revisiting.
• For each cell:
  • Iterate over possible moves.
  • Check bounds and whether the new cell is walkable ('.').
  • If a boundary of the maze is reached, that is considered an exit, and the current step count + 1 is returned, providing the shortest exit distance.
  • If not an exit, mark the new cell to prevent future revisits and add it to the BFS queue for further exploration.
• If all possible paths are explored without finding an exit, return -1.

In cases where the exit is adjacent to the entrance or multiple paths are available, the BFS ensures that the shortest path to the exit is found efficiently. The use of directional vectors and a queue for BFS processing simplifies traversal of the maze and handling of visited nodes.

class Solution {
    public int findExit(char[][] labyrinth, int[] entry) {
        int totalRows = labyrinth.length, totalCols = labyrinth[0].length;
        int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        
        int startingRow = entry[0], startingCol = entry[1];
        labyrinth[startingRow][startingCol] = '+';
        
        Queue<int[]> explorationQueue = new LinkedList<>();
        explorationQueue.offer(new int[]{startingRow, startingCol, 0});
        
        while (!explorationQueue.isEmpty()) {
            int[] current = explorationQueue.poll();
            int currRow = current[0], currCol = current[1], currStep = current[2];

            for (int[] move : directions) {
                int newRow = currRow + move[0], newCol = currCol + move[1];

                if (0 <= newRow && newRow < totalRows && 0 <= newCol && newCol < totalCols
                   && labyrinth[newRow][newCol] == '.') {
                    if (newRow == 0 || newRow == totalRows - 1 || newCol == 0 || newCol == totalCols - 1)
                        return currStep + 1;
                    
                    labyrinth[newRow][newCol] = '+';
                    explorationQueue.offer(new int[]{newRow, newCol, currStep + 1});
                }  
            }
        }
        return -1;
    }
}

The provided Java solution tackles the problem of finding the nearest exit from a given entrance in a maze. The maze is represented by a 2D character grid where passable paths are marked with '.', walls with '#', and places already visited are subsequently marked with '+' from their initial state of the entrance marked in the same way.

The solution employs the Breadth-First Search (BFS) strategy using a queue to explore the maze systematically. To implement this:

1. Initialize the maze dimensions (totalRows, totalCols) based on the size of the labyrinth.
2. Define four possible movement directions (up, down, left, right).
3. Start from the provided entry point in the maze, marking it visited by setting it to '+'.
4. Use a queue to manage the exploration. The queue stores each position as a three-element array containing the current row, current column, and steps taken to reach that position.
5. Begin exploration:
   • Dequeue the front position from the queue.
   • For each possible movement:
     • Compute the new position.
     • Check boundaries to ensure the new position is inside the maze and the cell is passable ('.').
     • If the new position is on the maze border (and not the initial entrance), it's an exit; hence return the number of steps taken incremented by one.
     • Mark the new position visited and enqueue it with incremented steps.
6. If no exit is found after exploring all possible paths, return -1 indicating failure to find an exit.

Use of BFS ensures that you find the minimum number of steps to the closest exit from the entrance, as it explores all possible paths level by level from the starting point.

class Solution:
    def shortestPathToExit(self, grid: List[List[str]], entry: List[int]) -> int:
        max_rows, max_cols = len(grid), len(grid[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        # Begin by marking the entry point as '+', indicating visited
        entry_row, entry_col = entry
        grid[entry_row][entry_col] = "+"
        
        # Use a deque to implement BFS and start from the entry point
        explore = collections.deque()
        explore.append([entry_row, entry_col, 0])
        
        while explore:
            r, c, dist = explore.popleft()
            
            # Checking all possible directions from the current position
            for dir_x, dir_y in directions:
                new_r = r + dir_x
                new_c = c + dir_y
                
                # Check for valid, unvisited path
                if 0 <= new_r < max_rows and 0 <= new_c < max_cols and grid[new_r][new_c] == ".":
                    
                    # If the position is at the boundary, it's an exit
                    if new_r in {0, max_rows - 1} or new_c in {0, max_cols - 1}:
                        return dist + 1
                    
                    # Mark this cell as visited and enqueue it
                    grid[new_r][new_c] = "+"
                    explore.append([new_r, new_c, dist + 1])
        
        # If there is no exit found
        return -1

This summary provides a brief overview for a function designed to find the shortest path from an entrance to the nearest exit in a maze, using Python 3. The solution utilizes the Breadth-First Search (BFS) algorithm to ensure optimal path discovery through the maze.

• Initialize max_rows and max_cols to the dimensions of the input grid and define potential movement directions (up, down, left, right).
• Mark the entry point in the grid as visited by setting it to "+" and initiate a deque to facilitate the BFS process.
• Start the BFS loop:
  • For each position (r,c) dequeued, check all four possible movement directions.
  • For each direction, calculate the new position (new_r, new_c).
  • If this position is on the grid, not visited, and not a wall (indicated by "."), proceed:
    • If this position is on the boundary of the grid (thus an exit), return the current distance incremented by one, signifying the exit has been reached.
    • If not an exit, mark it as visited and enqueue the new position along with the incremented distance.
• If no exit is found after exploring all possibilities, return -1 indicating failure to find an exit.

This method efficiently calculates the minimum number of steps required to exit the maze, ensuring that all potential paths are explored systematically and terminate once the nearest exit is reached.