✅3d dp solution || python
Intuition\n    please use bfs approach,my solution works but not optimize.\n\n# Code\n\nclass Solution:\n\n    def check(self,dp,grid,i,j,k,n):\n        if(i==n
# Intuition\n    please use bfs approach,my solution works but not optimize.\n\n# Code\n```\nclass Solution:\n\n    def check(self,dp,grid,i,j,k,n):\n        if(i==n-1 and j==n-1 and k==0):return 0\n        if(min(i,j)<0 or max(i,j)>=n or grid[i][j]==1 or grid[i][j]==-1):return n*n\n        # print(i,j,k,dp[i][j][k],"------")\n        if(dp[i][j][k]!=-1):return dp[i][j][k]\n        ans=n*n\n        pre=grid[i][j]\n        grid[i][j]=-1\n        if(k==0):\n            if(i+1<n and grid[i+1][j-1]!=1 and grid[i+1][j]!=1):\n                ans=min(ans,self.check(dp,grid,i+1,j,k,n)+1)\n                ans=min(ans,self.check(dp,grid,i+1,j-1,k^1,n)+1)\n            ans=min(ans,self.check(dp,grid,i,j+1,k,n)+1)\n        else:\n            ans=min(ans,self.check(dp,grid,i+1,j,k,n)+1)\n            if(j+1<n and grid[i-1][j+1]!=1 and  grid[i][j+1]!=1):\n                ans=min(ans,self.check(dp,grid,i,j+1,k,n)+1)\n                ans=min(ans,self.check(dp,grid,i-1,j+1,k^1,n)+1)\n        dp[i][j][k]=ans\n        grid[i][j]=pre\n        # print(i,j,k,dp[i][j][k])\n        return dp[i][j][k]\n\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        n=len(grid)\n        dp=[[[-1 for k in range(2)] for i in range(n)] for j in range(n)]\n        ans=self.check(dp,grid,0,1,0,n)\n        if(ans>=n*n):return -1\n        return ans\n```
['Array', 'Dynamic Programming', 'Matrix', 'Python3']