[Java/Python 3] 25 and 17 liner clean BFS codes w/ brief explanation and analysis.
Use the coordinate of the snake tail (up/left part), r, c, and the row difference between head and tail, dr, to describe the position of the snake. Obviously, d
1. Use the coordinate of the snake tail (up/left part), `r, c`, and the row difference between head and tail, `dr`, to describe the position of the snake. Obviously, `dr = 0` and `dr = 1` indicate that the snake is in `horizontal` and `vertical` positions, respectively;\n2. Use a Queue and a HashSet to perform BFS traversal and prune duplicates;\n3. In order to create hash for HashSet, use `r + "," + c + "," + dr` to encode snake position.\n\n\n```java\n    public int minimumMoves(int[][] g) {\n        int n = g.length;\n        int[] start = {0, 0, 0, 0}, target = {n - 1, n - 2, 0};\n        Queue<int[]> q = new LinkedList<>();\n        q.offer(start);\n        Set<String> seen = new HashSet<>();\n        while (!q.isEmpty()) {\n            int[] pos = q.poll();\n            int r = pos[0], c = pos[1], dr = pos[2], steps = pos[3];        // snake tail row, column, row difference, steps.\n            if (Arrays.equals(Arrays.copyOf(pos, 3), target))               // reach target.\n                return steps;\n            if (seen.add(r + "," + c + "," + dr)) {                         // prune duplicates.\n                if (dr == 0) {                                              // horizontal position.\n                    if (r + 1 < n && g[r + 1][c] + g[r + 1][c + 1] == 0)    // the two cells below are empty: down and colock-wise rotation.\n                        q.addAll(Arrays.asList(new int[]{r + 1, c, 0, steps + 1}, new int[]{r, c, 1, steps + 1}));\n                    if (c + 2 < n && g[r][c + 2] == 0)                      // the right cell is empty.\n                        q.offer(new int[]{r, c + 1, 0, steps + 1});         // right.\n                }else {                                                     // vertical position.\n                    if (c + 1 < n && g[r][c + 1] + g[r + 1][c + 1] == 0)    // the two cells right are empty: right and counterclock-wise rotation.\n                        q.addAll(Arrays.asList(new int[]{r, c + 1, 1, steps + 1}, new int[]{r, c, 0, steps + 1}));\n                    if (r + 2 < n && g[r + 2][c] == 0)                      // the below cell is empty.\n                        q.offer(new int[]{r + 1, c, 1, steps + 1});         // down.\n                }                    \n            }\n        }\n        return -1;\n    }\n```\n```python\n    def minimumMoves(self, grid: List[List[int]]) -> int:\n        n = len(grid)\n        q, seen, target = [(0, 0, 0, 0)], set(), (n - 1, n - 2, 0)              # row, column, row difference.\n        for r, c, dr, steps in q:\n            if (r, c, dr) == target: return steps                               # reach target.\n            if (r, c, dr) not in seen:                                          # prune duplicates.\n                seen.add((r, c, dr))\n                if dr:                                                          # vertical position. \n                    if c + 1 < n and grid[r][c + 1] + grid[r + 1][c + 1] == 0:  # the two cells right are emtpty.\n                        q += [(r, c + 1, 1, steps + 1), (r, c, 0, steps + 1)]   # right and counter-colock-wise rotate.\n                    if r + 2 < n and grid[r + 2][c] == 0:                       # the below cell is empty.\n                        q += [(r + 1, c, 1, steps + 1)]                         # down.\n                else:                                                           # horizontal position\n                    if r + 1 < n and grid[r + 1][c] + grid[r + 1][c + 1] == 0:  # the two cells below are empty.\n                        q += [(r + 1, c, 0, steps + 1), (r, c, 1, steps + 1)]   # down and colock-wise rotate.\n                    if c + 2 < n and grid[r][c + 2] == 0:                       # right cell is empty.\n                        q += [(r, c + 1, 0, steps + 1)]                         # right.\n        return -1\n```\n\n\n\n**Analysis:**\n\nFor each cell, the snake tail corresponds to at most 4 positions. Therefore,\n\nTime & space: `O(n ^ 2)`, where `n = grid.length`.\n\n----\nBelow is the **old post content**:\n\nQ: why the 23rd test case expects -1, NOT 29?\n\nPlease give me a hand to explain why the 23rd test case expects `-1`, NOT `29`? I use `a-za-c` to indicate the snake path.\n```\n[[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],\n [0,1,0,1,1,0,0,1,0,0,0,0,1,0,0],\n [0,1,0,0,0,0,1,0,0,1,0,0,0,0,0],\n [0,0,0,0,0,0,1,0,0,0,0,0,0,0,0],\n [0,0,0,0,0,0,1,1,0,0,0,0,0,0,0],\n [0,0,0,0,0,0,0,0,0,1,0,1,0,0,0],\n [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n [0,0,0,1,0,1,0,0,1,0,0,0,1,0,0],\n [0,0,0,0,1,0,0,0,0,0,0,0,0,1,0],\n [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n [0,0,0,1,0,0,0,0,0,0,0,0,0,0,0],\n [1,0,1,1,0,0,0,0,0,0,0,0,0,0,0],\n [0,0,0,0,0,0,0,0,0,0,0,0,0,1,0],\n [1,0,0,0,0,0,1,0,0,0,1,0,0,0,1],\n [0,0,1,0,1,0,0,0,0,0,0,0,0,0,0]]\n\n[[0,0,1,0,0,0,0,0,0,0,0,0,0,0,0],\n [a,1,0,1,1,0,0,1,0,0,0,0,1,0,0],\n [b,1,0,0,0,0,1,0,0,1,0,0,0,0,0],\n [c,0,0,0,0,0,1,0,0,0,0,0,0,0,0],\n [d,0,0,0,0,0,1,1,0,0,0,0,0,0,0],\n [e,0,0,0,0,0,0,0,0,1,0,1,0,0,0],\n [f,0,0,0,0,0,0,0,0,0,0,0,0,0,0],\n [g,0,0,1,0,1,0,0,1,0,0,0,1,0,0],\n [h,0,0,0,1,0,0,0,0,0,0,0,0,1,0],\n [i,k,0,0,0,0,0,0,0,0,0,0,0,0,0],\n [j,k,0,1,0,0,0,0,0,0,0,0,0,0,0],\n [1,l,1,1,0,0,0,0,0,0,0,0,0,0,0],\n [0,m,O,p,q,r,s,t,u,v,0,0,0,1,0],\n [1,n,O,p,0,0,1,0,w,w,1,0,0,0,1],\n [0,0,1,0,1,0,0,0,x,x,y,z,a,b,c]]\n```\ncredit to **@QuentinHe** and **@chuckdchen**\nA: \nIt will fail on the first step. the snake is cornered by the two `1s` on the right and bottom `[0,3]` and `[1,1]`, you can\'t rotate when `[1,1]` is a blocker.
[]