✅[C++] Just do BFS !!......still getting TLE? See, Why
Thought Process:\nSince it is asked to get the shortest path (nearest exit), first thought that should come to us is BFS.\nTHATS IT !!\n\n\nclass Solution {\npu
# Thought Process:\nSince it is asked to get the shortest path (nearest exit), first thought that should come to us is **BFS**.\nTHATS IT !!\n\n```\nclass Solution {\npublic:\n    bool check_constraint (int i, int j, int m, int n){\n        return (i >= 0 && i < m && j >= 0 && j < n);\n    }\n    \n    bool check_boundary (int i, int j, int m, int n){        \n        return (i == 0 || i == m-1 || j == 0 || j == n-1);\n    }\n\t\n    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {\n        int level = 0, m = maze.size(), n = maze[0].size();\n        queue<vector<int>> q;\n        vector<vector<bool>> vis (m, vector<bool>(n,0));\n        q.push (entrance);\n        \n        vis[entrance[0]][entrance[1]] = 1;\n        \n        while (!q.empty ()){\n            int len = q.size();\n            \n            for (int i = 0; i < len; i++){\n                auto x = q.front ()[0];\n                auto y = q.front ()[1];\n                q.pop ();\n                \n\t\t\t\t//go down\n                if (check_constraint (x+1,y,m,n) && !vis[x+1][y] && maze[x+1][y] == \'.\'){\n                    if (check_boundary(x+1,y,m,n)) return level+1;\n                    \n                    vis[x+1][y] = 1;\n                    q.push ({x+1,y});\n                }\n                \n\t\t\t\t// go up\n                if (check_constraint (x-1,y,m,n) && !vis[x-1][y]&& maze[x-1][y] == \'.\'){\n                    if (check_boundary(x-1,y, m,n)) return level+1;\n                    \n                    vis[x-1][y] = 1;\n                    q.push ({x-1,y});\n                }\n                \n\t\t\t\t//go right\n                if (check_constraint (x,y+1,m,n)  && !vis[x][y+1] && maze[x][y+1] == \'.\'){\n                    if (check_boundary(x,y+1,m,n)) return level+1;\n                    \n                    vis[x][y+1] = 1;\n                    q.push ({x,y+1});\n                }\n                \n\t\t\t\t//go left\n                if (check_constraint (x,y-1,m,n)  && !vis[x][y-1] && maze[x][y-1] == \'.\'){\n                    if (check_boundary(x,y-1,m,n))  return level+1;\n                    \n                    vis[x][y-1] = 1;\n                    q.push ({x,y-1});\n                }\n            }\n            \n            level++;\n        }\n        \n        return -1;\n    }\n};\n```\n\n# Complexities:\n**TC:** O(number of empty cells)\n**SC:** O(n * m)
['C']