dfs✅ || c++✅ || superfast solution✅
\nclass Solution {\npublic:\n    map<pair<int,pair<int,int>>,int>mp;\n    int dp[101][101][3];\n    int solve(vector<vector<int>>&grid,int n,int m,int i,int j,i
```\nclass Solution {\npublic:\n    map<pair<int,pair<int,int>>,int>mp;\n    int dp[101][101][3];\n    int solve(vector<vector<int>>&grid,int n,int m,int i,int j,int pos){\n        if(i>=n || j>=m)return INT_MAX;\n\t\t//f i ans j are at right bottom end and rotaion is 0 then we return \n        if(i==n-1 && j==n-1 && pos==0)return 0;\n        int ans=INT_MAX,first=i,second=j;\n        \n        if(dp[i][j][pos]!=-1)return dp[i][j][pos];\n        if(pos==0){\n            if(j+1<m && grid[i][j+1]==0 && mp.find({0,{i,j+1}})==mp.end()){\n\t\t\t//to avoid runtime erroe vis the same node again\n                mp[{0,{i,j+1}}]++;\n                int c=solve(grid,n,m,i,j+1,pos);\n\t\t\t\t//backtrack\n                mp.erase({0,{i,j+1}});\n                if(c!=INT_MAX)ans=min(ans,1+c);\n            }\n            if(i+1<n && grid[i+1][j]==0 && grid[i+1][j-1]==0 && mp.find({0,{i+1,j}})==mp.end()){\n                mp[{0,{i+1,j}}]++;\n                int e=solve(grid,n,m,i+1,j,pos);\n                mp.erase({0,{i+1,j}});\n                if(e!=INT_MAX)ans=min(ans,1+e);\n            }\n            if(i+1<n && grid[i+1][j]==0 && grid[i+1][j-1]==0 && mp.find({1,{i+1,j-1}})==mp.end()){\n                mp[{1,{i+1,j-1}}]++;\n                int e=solve(grid,n,m,i+1,j-1,1);\n                mp.erase({1,{i+1,j-1}});\n                if(e!=INT_MAX)ans=min(ans,1+e);\n            }\n        }else{\n            if(i+1<n && grid[i+1][j]==0 && mp.find({1,{i+1,j}})==mp.end()){\n                mp[{1,{i+1,j}}]++;\n                int e=solve(grid,n,m,i+1,j,1);\n                mp.erase({1,{i+1,j}});\n                if(e!=INT_MAX)ans=min(ans,1+e);\n            }\n            if(j+1<n && grid[i][j+1]==0 && grid[i-1][j+1]==0 && mp.find({1,{i,j+1}})==mp.end()){\n                mp[{1,{i,j+1}}]++;\n                int e=solve(grid,n,m,i,j+1,1);\n                mp.erase({1,{i,j+1}});\n                if(e!=INT_MAX)ans=min(ans,1+e);\n            }\n            if(j+1<n && grid[i][j+1]==0 && grid[i-1][j+1]==0 && mp.find({0,{i-1,j+1}})==mp.end()){\n                mp[{0,{i-1,j+1}}]++;\n                int e=solve(grid,n,m,i-1,j+1,0);\n                mp.erase({0,{i-1,j+1}});\n                if(e!=INT_MAX)ans=min(ans,1+e);\n            }\n        }\n        return dp[i][j][pos]=ans;\n    }\n    int minimumMoves(vector<vector<int>>&grid){\n        memset(dp,-1,sizeof(dp));\n        int ans=solve(grid,grid.size(),grid[0].size(),0,1,0);\n        return ans==INT_MAX?-1:ans;\n    }\n};\n```
['Dynamic Programming', 'Depth-First Search', 'C']