Python and C++ Solution with Explanation - BFS
It is a commonly known concept that we can use either DFS or BFS to find if there is a path from one node to another in a graph. You check out Abdul Bari\u2019s
It is a commonly known concept that we can use either DFS or BFS to find if there is a path from one node to another in a graph. You check out Abdul Bari\u2019s video on YouTube if you want a clear about both of these traversals.\n\nThe basic idea here is to perform a breadth-first search on the given input matrix looking for the first exit point. We can use DFS as well, but the issue is that we would have to check for every path, unlike BFS. In BFS, as soon as we get an exit, we can be assured that it is the shortest path because BFS is a level order traversal. \n\nFor a detailed solution, check out my blog on hello ML at https://helloml.org/nearest-exit-from-entrance-in-maze-solution-to-leetcode-problem/. \n\n## Solution in Python\n```python\nclass Solution:\n    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:\n        # Creating a queue for BFS\n        queue = []\n        queue.append(entrance)\n        \n        moves = 1\n        rows = len(maze)\n        columns = len(maze[0])\n        # All Available movements\n        directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n        # Setting the entrace as visited\n        maze[entrance[0]][entrance[1]] = \'+\'\n        # As long as queue is not empty\n        while(queue):\n            l = len(queue)\n            # Now exploring every element in the queue\n            for k in range(0, l):\n                [i, j] = queue.pop(0)\n                # Trying all possible directions\n                for t in range(0, 4):\n                    x = i + directions[t][0]\n                    y = j + directions[t][1]\n                    # Invalid position\n                    if(x < 0 or y < 0 or x >= rows or y >= columns or maze[x][y] == \'+\'):\n                        continue\n                    # Exit Reached\n                    elif(x == 0 or y == 0 or x == rows -1 or y == columns -1 ):\n                        return moves\n                    # Mark as Visited\n                    maze[x][y] = \'+\'\n                    queue.append([x, y])\n            moves += 1\n        return -1\n```\n## Solution in C++\n```cpp\nclass Solution {\npublic:\n    int nearestExit(vector<vector<char>>& maze, vector<int>& e) {\n        queue<pair<int,int>> q;\n        q.push({e[0],e[1]});\n\n        int moves=1;\n        int rows=maze.size();\n        int cols=maze[0].size();\n\n        vector<vector<int>> offsets={{0,1},{1,0},{0,-1},{-1,0}};\n\n        maze[e[0]][e[1]]=\'+\';\n        while(!q.empty())\n        {\n            int l=q.size();\n            //for every node in the queue visit all of it\'s adjacent nodes which are not visited yet\n            for(int k=0;k<l;k++)\n            {\n                auto [i,j]=q.front();\n                q.pop();\n                \n                //try all 4 directions from the current cell\n                for(int l=0;l<4;l++)\n                {\n                    int x=i+offsets[l][0];\n                    int y=j+offsets[l][1];\n                    //a invalid move\n                    if(x<0 || y<0 || x>=rows || y>=cols || maze[x][y]==\'+\')\n                        continue;\n                    //if we have reached the exit then current moves are the min moves to reach the exit\n                    if(x==0 || y==0 || x==rows-1 || y==cols-1)\n                        return moves;\n                    //block the cell as we have visited\n                    maze[x][y]=\'+\';\n                    q.push({x,y});\n                }\n            }\n            //increment the moves\n            moves++;\n        }\n        return -1;\n    }\n};\n```
['Breadth-First Search', 'C', 'Python', 'C++']