Java | BFS based on snake position
The only part to pay attention to is to make sure there are no errors when generating the next snake position based on the current position. \n The approach bel
* The only part to pay attention to is to make sure there are no errors when generating the next snake position based on the current position. \n* The approach below encode the snake\'s tail and head positions as 4 co-ordinates\n* (r1, c1) represents snake tail, (r2, c2) represents snake head cells\n* Using the rules defined in the question, generate next positions in order to move to destination using BFS\n\n```\nclass Solution {\n    public int minimumMoves(int[][] grid) {\n        Set<Position> seen = new HashSet<>();\n        Queue<int[]> queue = new LinkedList<>();\n        \n        int[] start = {0, 0, 0, 1, 0};\n        queue.add(start);\n        \n        seen.add(new Position(0, 0, 0, 1));\n        \n        while (!queue.isEmpty()) {\n            int[] top = queue.poll();\n            int r1 = top[0];\n            int c1 = top[1];\n            int r2 = top[2];\n            int c2 = top[3];\n            int moves = top[4];\n            \n            if (r1 == grid.length - 1 && r2 == grid.length - 1 && c1 == grid[0].length - 2 && c2 == grid[0].length - 1) {\n                return moves;\n            }\n            \n            List<int[]> next = nextPositions(r1, c1, r2, c2, grid);\n            for (int[] n : next) {\n                Position nPos = new Position(n[0], n[1], n[2], n[3]);\n                if (seen.contains(nPos)) {\n                    continue;\n                }\n                \n                seen.add(nPos);\n                queue.add(new int[]{n[0], n[1], n[2], n[3], moves + 1});\n            }\n        }\n        \n        return -1;\n    }\n    \n    private boolean isHorizontal(int r1, int r2) {\n        return r1 == r2;\n    }\n    \n    private List<int[]> nextPositions(int r1, int c1, int r2, int c2, int[][] grid) {\n        List<int[]> res = new ArrayList<>();\n        \n        boolean isHorizontal = isHorizontal(r1, r2);\n        \n        if (isHorizontal) {\n            // Horizontal & Right\n            if (c2 + 1 < grid[0].length && grid[r2][c2 + 1] == 0) {\n                res.add(new int[]{r2, c2, r2, c2 + 1});\n            }\n            \n            if (r2 + 1 < grid.length && grid[r2 + 1][c1] == 0 && grid[r2 + 1][c2] == 0) {\n                // Horizontal & Down\n                res.add(new int[]{r2 + 1, c1, r2 + 1, c2});\n                // Horizonal && clockwise\n                res.add(new int[]{r1, c1, r1 + 1, c1});\n            }\n        } else {\n            if (c2 + 1 < grid[0].length && grid[r1][c2 + 1] == 0 && grid[r2][c2 + 1] == 0) {\n                // Vertical & Right\n                res.add(new int[]{r1, c2 + 1, r2, c2 + 1});\n                // Vertical & counterclockwise\n                res.add(new int[]{r1, c1, r1, c1 + 1});\n            }\n            // Vertical & Down\n            if (r2 + 1 < grid.length && grid[r2 + 1][c1] == 0) {\n                res.add(new int[]{r2, c1, r2 + 1, c1});\n            }\n        }\n        \n        return res;\n    }\n}\n\nclass Position {\n    int r1;\n    int c1;\n    int r2;\n    int c2;\n    \n    public Position(int r1, int c1, int r2, int c2) {\n        this.r1 = r1;\n        this.c1 = c1;\n        this.r2 = r2;\n        this.c2 = c2;\n    }\n    \n    public int hashCode() {\n        return Objects.hash(r1, c1, r2, c2);\n    }\n    \n    public boolean equals(Object o) {\n        if (o == null || !(o instanceof Position)) {\n            return false;\n        }\n        \n        Position that = (Position)o;\n        \n        return r1 == that.r1 && r2 == that.r2 && c1 == that.c1 && c2 == that.c2;\n    }\n}\n```
['Breadth-First Search', 'Java']