C++ || BFS || IN-DEPTH Analysis
c++\nFirst I Thought We Have To Find The Nearest Exit Cell Coordinate Manhattan Distance From The Given Position.\nI Solved This Question Keeping The Above Thou
**c++**\nFirst I Thought We Have To Find The Nearest Exit Cell Coordinate Manhattan Distance From The Given Position.\nI Solved This Question Keeping The Above Thought In Mind.\n\nAnd Here\'s The Code \n**Suprisingly It has passed 188 test Cases Out of 194**\n```\nvector<int> dir={-1,0,1,0,-1};\n    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {\n        queue<pair<int, int>> pq;\n        int x = entrance[0], y = entrance[1];\n        int n = maze.size(), m = maze[0].size();\n        maze[x][y] = \'+\';\n        int ans = INT_MAX;\n        pq.push({x, y});\n        while(!pq.empty()){\n            int size = pq.size();\n            while(size--){\n                auto top  = pq.front();\n                pq.pop();\n                for(int i = 0; i < 4; i++){\n                    int r = top.first + dir[i];\n                    int c = top.second + dir[i + 1];\n                    if(r >= 0 && c >= 0 && r < n && c < m && maze[r][c] != \'+\'){\n                        pq.push({r, c});\n                        maze[r][c] = \'+\';\n                    }\n                    if(r < 0 || c < 0 || r >= n || c >= m){\n                        if(top.first != x || top.second != y){\n                            ans = min(ans , abs(x - top.first) + abs(top.second - y));\n                        }\n                    }\n                }\n            }\n        }\n        if(ans == INT_MAX) return -1;\n        return ans;\n    }\n```\n\nNow Comming Back To Original Question :\nWe Actually have to Find the Minimum Number Of Steps Reuired to reach The Nearest Exit:\nFor Which I have to do Small Modification of The Above Code,\nInstead of **queue<pair<int,int>>** I took **queue<pair<pair<int, int>, int>>** Which Will Keep The count OF the Number Of steps Taken So far:\n\nHere\'s The Code:\n```\nclass Solution {\npublic:\n    vector<int> dir={-1,0,1,0,-1};\n    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {\n        queue<pair<pair<int, int>,int>> pq;\n        int x = entrance[0], y = entrance[1];\n        int n = maze.size(), m = maze[0].size();\n        maze[x][y] = \'+\';\n        int ans = INT_MAX;\n        pq.push({{x, y}, 0});\n        while(!pq.empty()){\n            int size = pq.size();\n            while(size--){\n                auto top  = pq.front();\n                pq.pop();\n                for(int i = 0; i < 4; i++){\n                    int r = top.first.first + dir[i];\n                    int c = top.first.second + dir[i + 1];\n                    if(r >= 0 && c >= 0 && r < n && c < m && maze[r][c] != \'+\'){\n                        pq.push({{r, c}, top.second + 1});\n                        maze[r][c] = \'+\';\n                    }\n                    else if(r < 0 || c < 0 || r >= n || c >= m){\n                        if(top.first.first != x || top.first.second != y){\n                            ans = min(ans , top.second);\n                        }\n                    }\n                }\n            }\n        }\n        if(ans == INT_MAX) return -1;\n        return ans;\n    }\n};\n\n**Please Do UpVote , It Will BE Very HelpFull.....Thanks**\n```
['Breadth-First Search', 'C', 'Matrix']