22 Line dfs
Code\n\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        grid = [[1] * (len(grid[0])+2)] + \\\n               [[1] + grid[i] 
# Code\n```\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        grid = [[1] * (len(grid[0])+2)] + \\\n               [[1] + grid[i] + [1] for i in range(len(grid))] + \\\n               [[1]*(len(grid[0])+2)]\n        R, C = len(grid), len(grid[0])\n        def canrotate(r, c):\n            if grid[r][c] == grid[r][c+1] == grid[r+1][c] == grid[r+1][c+1] == 0:\n                return True\n        #state 1: horizontal    state 2: vertical\n        def dfs(r, c, state):\n            if state&1 and r==R-2 and c==C-3: return 0\n            if (r, c, state) in memo: return memo[(r, c, state)]\n            memo[(r, c, state)] = res = 10**8\n            if state&1:\n                if grid[r][c+2] == 0: res = min(res, dfs(r, c+1, 1)+1)\n                if grid[r+1][c] == 0 and grid[r+1][c+1] == 0: res = min(res, dfs(r+1, c, 1)+1)\n            if state&2:\n                if grid[r][c+1] == 0 and grid[r+1][c+1] == 0: res = min(res, dfs(r, c+1, 2)+1) \n                if grid[r+2][c] == 0: res = min(res, dfs(r+1, c, 2)+1)\n            if grid[r][c] == grid[r][c+1] == grid[r+1][c] == grid[r+1][c+1] == 0:\n                res = min(res, dfs(r, c, 3-state)+1)\n            memo[(r, c, state)] = res\n            return res\n        memo = {}\n        return dfs(1, 1, 1) if dfs(1, 1, 1) != 10**8 else -1\n            \n                \n                \n```
['Python3']