Java concise BFS solution - Take snake positions as a node
When it comes to minimum moves, it is not hard to think about using BFS. If we take this as a search problem in a graph, the key is the defintion of nodes and e
When it comes to minimum moves, it is not hard to think about using BFS. If we take this as a search problem in a graph, the key is the defintion of nodes and edges in the graph . In this case, we can take snake\'s position(as the snake is taking two positions in the grid, we should use two locations) as a node, and a move(RIGHT, DOWN, ROTATE CLOCKWISE, ROTATE ANTI-CLOCKWISE) as an edge, then we can proceed with BFS.\n\n\n```\nclass Solution {\n    public int minimumMoves(int[][] grid) {\n        // r1-c1-r2-c2 as a node\n        Set<String> visited = new HashSet<>();\n        Queue<int[]> queue = new LinkedList<>();\n        int[][] moves = {{0, 1, 0, 1}, {1, 0, 1, 0}, {0, 0, 1, -1}, {0, 0, -1, 1}};\n        \n        int n = grid.length;\n        int steps = 0;\n        \n        queue.add(new int[] {0, 0, 0, 1});\n        visited.add("0-0-0-1");\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            \n            steps++;\n            for (int k = 0; k < size; k++) {\n                int[] node = queue.poll();\n                \n                // moves;\n                for (int i = 0; i < moves.length; i++) {\n                    int r1 = node[0] + moves[i][0], c1 = node[1] + moves[i][1];\n                    int r2 = node[2] + moves[i][2], c2 = node[3] + moves[i][3];\n                    String id = r1 + "-" + c1 + "-" + r2 + "-" + c2;\n                    \n                    if (!isValid(r1, c1, grid) || !isValid(r2, c2, grid)) {\n                        continue;\n                    } else if (r1 == n - 1 && c1 == n - 2 && r2 == n - 1 && c2 == n - 1) {\n                        return steps;\n                    } else if (!visited.contains(id)) {\n                        if (i < 2 || (isH(node) && i == 2 || !isH(node) && i == 3) && isValid(r1 + 1, c1 + 1, grid)) {\n                            visited.add(id);\n                            queue.add(new int[] {r1, c1, r2, c2});    \n                        }\n                    }\n                }\n            }\n        }\n        \n        return -1;\n    }\n    \n    boolean isH(int[] node) {\n        return node[0] == node[2];\n    }\n    \n    boolean isValid(int r, int c, int[][] grid) {\n        int n = grid.length;\n        \n        return r >= 0 && c >= 0 && r < n && c < n && grid[r][c] == 0;\n    }\n}\n```
[]