✅ Easy Peasy Approach || C++ || Beats 100% 😮😮
Intuition\nThe problem requires finding the shortest path to an exit in a maze from a given starting position (entrance). This resembles a shortest path search,
# Intuition\nThe problem requires finding the shortest path to an exit in a maze from a given starting position (entrance). This resembles a **shortest path** search, which is efficiently handled by **Breadth-First Search (BFS)** since BFS explores nodes level by level, ensuring that the first exit found is the closest.\n\n# Approach\n1. **Setup BFS**: We use a queue to hold each cell (or room) to explore, with the row, column, and current distance from the entrance.\n2. **Mark Entrance**: We start from the entrance cell, marking it as visited to prevent revisiting it and avoiding infinite loops.\n3. **Process Each Level in BFS**: For each cell, we:\n   - Check if it is an exit. If it is on the boundary of the maze (except the entrance), we return the current distance.\n   - Add each unvisited, traversable neighbor (adjacent cells marked \'.\') to the queue and mark it as visited.\n4. **Return Result**: If we exhaust all options without finding an exit, return `-1`.\n\n# Complexity\n- **Time complexity**: \\(O(m \\times n)\\)\n  - In the worst case, we visit each cell in the maze once, giving a time complexity of \\(O(m \\times n)\\), where \\(m\\) and \\(n\\) are the maze dimensions.\n\n- **Space complexity**: \\(O(m \\times n)\\)\n  - The space complexity also depends on the size of the maze since we use a `visited` matrix of the same size, and the queue could potentially store up to \\(m \\times n\\) cells in the worst case.\n\n# Code\n```cpp\nclass Solution {\npublic:\n    struct room {\n        int row;\n        int col;\n        int distance;\n    };\n\n    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {\n        int m = maze.size();\n        int n = maze[0].size();\n        vector<vector<bool>> visited(m,vector<bool>(n,false));\n        queue<room> q;\n        q.push({entrance[0], entrance[1], 0});\n        visited[entrance[0]][entrance[1]] = true;\n\n        while (!q.empty()) {\n            auto e = q.front();\n            int row = e.row;\n            int col = e.col;\n            int dis = e.distance;\n            q.pop();\n\n            if ((row == 0 || col == 0 || row == m-1 || col == n-1) && !(row == entrance[0] && col == entrance[1])) {\n                return dis;\n            }\n\n            if ((row - 1 >= 0) && (maze[row - 1][col] == \'.\') && (!visited[row - 1][col])) {\n                visited[row - 1][col] = true;\n                q.push({row - 1, col, dis + 1});\n            }\n            if ((col - 1 >= 0) && (maze[row][col - 1] == \'.\') && (!visited[row][col - 1])) {\n                visited[row][col - 1] = true;\n                q.push({row, col - 1, dis + 1});\n            }\n            if ((row + 1 < m) && (maze[row + 1][col] == \'.\') && (!visited[row + 1][col])) {\n                visited[row + 1][col] = true;\n                q.push({row + 1, col, dis + 1});\n            }\n            if ((col + 1 < n) && (maze[row][col + 1] == \'.\') && (!visited[row][col + 1])) {\n                visited[row][col + 1] = true;\n                q.push({row, col + 1, dis + 1});\n            }\n        }\n        return -1;\n    }\n};\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n
['Breadth-First Search', 'Graph', 'C++']