Python DP solution
dp[i][j][k]: minimum moves make snake tail to grid[i][j], where k = 0 means horizontal and k = 1 means vertical\n\n\ndef minimumMoves(self, grid):\n        """\
dp[i][j][k]: minimum moves make snake tail to grid[i][j], where k = 0 means horizontal and k = 1 means vertical\n\n```\ndef minimumMoves(self, grid):\n        """\n        :type grid: List[List[int]]\n        :rtype: int\n        """\n        n = len(grid)\n        if grid[-1][-1] == 1:\n            return -1\n        dp = [[[float(\'inf\'), float(\'inf\')] for i in xrange(n)] for j in xrange(n)]\n        dp[0][0][0] = 0\n        for j in xrange(1, n - 1):\n            if grid[0][j + 1] == 0:\n                dp[0][j][0] = dp[0][j - 1][0] + 1\n            else:\n                break\n        for i in xrange(n):\n            for j in xrange(n):\n                if j < n - 1 and grid[i][j + 1] == 0:\n                    dp[i][j][0] = min(dp[i][j][0], dp[i][j - 1][0] + 1)\n                    if grid[i][j] == 0:\n                        dp[i][j][0] = min(dp[i][j][0],dp[i - 1][j][0] + 1)\n                if i < n - 1 and grid[i + 1][j] == 0:\n                    dp[i][j][1] = min(dp[i][j][1], dp[i - 1][j][1] + 1)\n                    if grid[i][j] == 0:\n                        dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + 1)\n                if i < n - 1 and j < n - 1 and grid[i][j + 1] == grid[i + 1][j] == grid[i + 1][j + 1] == 0:\n                    dp[i][j][0], dp[i][j][1] = min(dp[i][j][0], dp[i][j][1] + 1), min(dp[i][j][1], dp[i][j][0] + 1)\n        return dp[n - 1][n - 2][0] if dp[n - 1][n - 2][0] < float(\'inf\') else -1\n```
['Dynamic Programming']