[Python] DP solution. Intuitive with comments.
python\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        dp = [[[114514, 11
```python\nclass Solution:\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        m, n = len(grid), len(grid[0])\n        \n        dp = [[[114514, 114514] for i in range(n)] for j in range(m)]\n        # dp[i][j][0]: the number of minimum moves that the snake\'s tail can reach (i, j) and positioned horizontally\n        # dp[i][j][1]: the number of minimum moves that the snake\'s tail can reach (i, j) and positioned vertically\n        \n        dp[0][0][0] = 0\n        for i in range(m):\n            for j in range(n):\n                # dp[i][j][0] = min(dp[i][j - 1][0], dp[i - 1][j][0], dp[i][j][1]) + 1\n                # dp[i][j][1] = min(dp[i][j - 1][1], dp[i - 1][j][1], dp[i][j][0]) + 1\n                \n                hori = [] # tail horizontally placed in (i, j)\n                if j < n - 1 and j > 0 and grid[i][j] != 1 and grid[i][j + 1] != 1: # moved right to (i, j)\n                    hori.append(dp[i][j - 1][0])\n                if j < n - 1 and i > 0 and grid[i][j] != 1 and grid[i][j + 1] != 1: # moved down to (i, j)\n                    hori.append(dp[i - 1][j][0])\n                if j < n - 1 and i < m - 1 and grid[i][j] != 1 and grid[i][j + 1] != 1 and grid[i + 1][j + 1] != 1: # rotate counterclockwise\n                    hori.append(dp[i][j][1])\n                if hori:\n                    dp[i][j][0] = min(hori + [dp[i][j][0]]) + 1\n                    \n                vert = [] # tail vertically placed in (i, j)\n                if i < m - 1 and j > 0 and grid[i][j] != 1 and grid[i + 1][j] != 1: # moved right to (i, j)\n                    vert.append(dp[i][j - 1][1])\n                if i < m - 1 and i > 0 and grid[i][j] != 1 and grid[i + 1][j] != 1: # moved down to (i, j)\n                    hori.append(dp[i - 1][j][0])\n                    vert.append(dp[i - 1][j][1])\n                if i < m - 1 and j < n - 1 and grid[i][j] != 1 and grid[i + 1][j] != 1 and grid[i + 1][j + 1] != 1: # rotate clockwise\n                    vert.append(dp[i][j][0])\n                if vert:\n                    dp[i][j][1] = min(vert + [dp[i][j][1]]) + 1\n                    \n                if j < n - 1 and i < m - 1 and grid[i][j] != 1 and grid[i][j + 1] != 1 and grid[i + 1][j + 1] != 1: # update dp[i][j][0] again after dp[i][j][1] has changed\n                    dp[i][j][0] = min(dp[i][j][0], dp[i][j][1] + 1)\n                    \n        return -1 if dp[-1][-2][0] >= 114514 else dp[-1][-2][0] - dp[0][0][0]\n```
['Dynamic Programming', 'Python']