bfs ✅ || c++ ✅ || superfast 100%
\nclass Solution {\npublic:\n    int minimumMoves(vector<vector<int>>&grid){\n        int n=grid.size(),ans=0;\n        map<pair<int,pair<int,int>>,int>mp;\n   
```\nclass Solution {\npublic:\n    int minimumMoves(vector<vector<int>>&grid){\n        int n=grid.size(),ans=0;\n        map<pair<int,pair<int,int>>,int>mp;\n        queue<pair<int,pair<int,int>>>q;\n        \n        q.push({0,{0,1}});\n        mp[{0,{0,1}}]++;\n        int i=0;\n        while(q.size()>0){\n            int m=q.size();\n            while(m--)\n            {\n                int x=q.front().second.first,y=q.front().second.second,pos=q.front().first;\n                q.pop();\n                if(x==n-1 && y==n-1 && pos==0)return ans;\n                if(pos==0)\n                {\n                    if(y+1<n && grid[x][y+1]==0 && mp.find({0,{x,y+1}})==mp.end()){\n                        q.push({0,{x,y+1}});\n                        mp[{0,{x,y+1}}]++;\n                    }\n                    if(x+1<n && grid[x+1][y]==0 && grid[x+1][y-1]==0 && mp.find({0,{x+1,y}})==mp.end()){\n                        q.push({0,{x+1,y}});\n                        mp[{0,{x+1,y}}]++;\n                    }\n                    if(x+1<n && grid[x+1][y]==0 && grid[x+1][y-1]==0 && mp.find({1,{x+1,y-1}})==mp.end()){\n                        q.push({1,{x+1,y-1}});\n                        mp[{1,{x+1,y-1}}]++;\n                    }\n                }else{\n                    if(x+1<n && grid[x+1][y]==0 && mp.find({1,{x+1,y}})==mp.end()){\n                        q.push({1,{x+1,y}});\n                        mp[{1,{x+1,y}}]++;\n                    }\n                    if(y+1<n && grid[x][y+1]==0 && grid[x-1][y+1]==0 && mp.find({1,{x,y+1}})==mp.end()){\n                         q.push({1,{x,y+1}});\n                         mp[{1,{x,y+1}}]++;\n                    }\n                    if(y+1<n && grid[x][y+1]==0 && grid[x-1][y+1]==0 && mp.find({0,{x-1,y+1}})==mp.end()){\n                         q.push({0,{x-1,y+1}});\n                         mp[{0,{x-1,y+1}}]++;\n                    }\n                }\n            }\n            ans++;\n        }\n        return -1;\n    }\n};\n```
['Dynamic Programming', 'Breadth-First Search', 'C']