Fully Step by step explanation. BFS Solution
Intuition\nThe problem involves finding the nearest exit from a given entrance in a maze. We can use Breadth-First Search (BFS) to explore possible paths from t
# Intuition\nThe problem involves finding the nearest exit from a given entrance in a maze. We can use Breadth-First Search (BFS) to explore possible paths from the entrance and stop when we reach an exit.\n\n# Approach\n1. **Initialize**: Start by initializing the maze, the entrance coordinates, and the directions to move (up, down, left, right).\n2. **BFS**: Use BFS to explore the maze, marking the distance from the entrance to each cell. Stop the BFS when an exit is found.\n3. **Check for Exit on the Border**: While exploring, check if the current cell is on the border. If it is, return the distance as soon as an exit is found. This optimization reduces unnecessary exploration.\n4. **Return Result**: If no exit is found, return -1.\n\n# Step-by-Step Explanation\n1. **Initialization:** The code starts by including necessary headers, defining the Solution class, and initializing variables including the maze, entrance coordinates, and movement directions.\n2. **BFS:** The Breadth-First Search (BFS) algorithm is employed to explore the maze. A distance array is used to store the shortest distance from the entrance to each cell.\n3. **Check for Exit on the Border:** While exploring, the code checks if the current cell is on the border. If so, it returns the distance as soon as an exit is found. This is an optimization to reduce unnecessary exploration.\n4. **Return Result:** If no exit is found during the BFS, the function returns -1.\n\n\n# Complexity\n- **Time complexity:** The time complexity is O(m * n) where m is the number of rows and n is the number of columns in the maze. In the worst case, we may need to visit every cell in the maze.\n- **Space complexity:** The space complexity is also O(m * n) for the distance array used to store the shortest distance from the entrance to each cell.\n\n\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {\n        int m = maze.size();\n        int n = maze[0].size();\n\n        vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};\n        \n        // Initialize distance array with maximum values\n        vector<vector<int>> distance(m, vector<int>(n, INT_MAX));\n        distance[entrance[0]][entrance[1]] = 0;\n\n        // Queue for BFS\n        queue<pair<int, int>> q;\n        q.push({entrance[0], entrance[1]});\n\n        // BFS\n        while (!q.empty()) {\n            int x = q.front().first;\n            int y = q.front().second;\n            q.pop();\n\n            for (auto& dir : directions) {\n                int newX = x + dir[0];\n                int newY = y + dir[1];\n\n                // Check if the new position is valid\n                if (newX >= 0 && newX < m && newY >= 0 && newY < n && maze[newX][newY] == \'.\' && distance[newX][newY] == INT_MAX) {\n                    // Update the distance and add the new position to the queue\n                    distance[newX][newY] = distance[x][y] + 1;\n                    q.push({newX, newY});\n\n                    // Check if we reached an exit on the border\n                    if (newX == 0 || newX == m - 1 || newY == 0 || newY == n - 1) {\n                        return distance[newX][newY];\n                    }\n                }\n            }\n        }\n\n        // If no exit is found\n        return -1;\n    }\n};\n\n
['C++']