Detailed C++ Standard Approaches BFS Approach
This question can easily solved using a standard BFS algorithm.\n\nWe must do BFS step by step starting from the entrance and iterating level by level, so one o
This question can easily solved using a standard **BFS** algorithm.\n\nWe must do **BFS** step by step starting from the entrance and iterating level by level, so one of the paths that we choose will be the minimum path (if it exists).\n\n**Idea :** using **BFS** to find shortest path. \n\n\n**Complexity**\nSpace Complexity: **```O(m*n)```**\nTime Complexity: **```O(m*n)```**\n(Queue will store at max **(m * n)** nodes for the same reason and push or pop requires **O(1)** time.)\n\n**C++ code (BFS) :**\n```\n\nclass Solution {\nprivate:\n    vector<int> dx = {0, -1, 1, 0}, dy = {1, 0, 0, -1}; // 4 direction to move\n    int m, n; // to store row and column\n\nprivate:\n    // check for valid index\n    bool isValid(int x, int y) {\n        return x >= 0 and y >= 0 and x < m and y < n;\n    }\n\n    int find(vector<vector<char>> &maze, int st1, int st2) {\n        // get the row and col\n        m = maze.size(), n = maze[0].size();\n        int mn = INT_MAX;\n\n        // init the vis array and queue\n        vector<vector<int>> vis(m, vector<int>(n, 0));\n        queue<pair<int, int>>q;\n\n        // mark the curent user cell to visited and push position in queue\n        vis[st1][st2] = 1;\n        q.push({st1, st2});\n\n        int move = 0;\n\n        // until queue is empty do move in 4 direction untill you reach exit\n        while (!q.empty()) {\n            // get the queue size\n            int s = q.size();\n            \n            while (s--) {\n                // take the first element from queue\n                auto cur = q.front();\n                q.pop(); // remove it\n\n                // check if person reach to any of the boundary and also check if person making move to reach boundary i.e person doesn\'t staying at boundary initially\n                if ((cur.first != st1 or cur.second != st2) and (cur.first == 0 or cur.first == m - 1 or cur.second == 0 or cur.second == n - 1)) {\n                    return move;\n                }\n                \n                // check in 4 dir\n                for (int i = 0; i < 4; ++i) {\n                    // get the new adj row and col\n                    int x = cur.first + dx[i];\n                    int y = cur.second + dy[i];\n                    // if the new position is not visited or it should be a valid position also it\'s not a wall then make moves\n                    if (isValid(x, y) and !vis[x][y] and maze[x][y] == \'.\') {\n                        vis[x][y] = 1;\n                        q.push({x, y});\n                    }\n                }\n            }\n            // increment the moves\n            move++;\n        }\n        \n        // if not able to reach boundary\n        return -1;\n    }\n    \npublic:\n    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {\n        // pass the maze and starting position\n        return find(maze, entrance[0], entrance[1]);\n    }\n};\n\n```\n\nPLease upvote if you find this helpful. **: )**\nFeel free to comment in case of any doubt.
['Breadth-First Search', 'Graph', 'C']