Java BFS With Snake Class - Easy to Understand
The idea is to use BFS to find the shortest path to the destination. \n\nWe traverse all snake position (stored in the queue with recorded size) after each step
The idea is to use BFS to find the shortest path to the destination. \n\nWe traverse all snake position (stored in the queue with recorded size) after each step. For each possible snake position, we could try 4 moves, right, down, clockwise, counter clockwise in the next move. If the next move is valid, we add it to the queue.\n\nif the destination (note: must be horizontal position) is found during the traversal, return the step. If the destination is not found and the queue is empty (no more possible snake position), it means that the destination is not reachable therefore return false.\n\n`Snake` class is declared to store the position (horizontal/vertical) , the head position, and an id (avoid duplicate snake added to the queue).\n\nWe reocrd the snake id to dedupe the snake position we have visited in the previous steps (less steps, shorter path). \n\n\xB7\xB7\xB7\n\n\tclass Solution {\n\t\tpublic int minimumMoves(int[][] grid) {\n\t\t\tint rowCnt = grid.length, colCnt = grid[0].length;\n\t\t\tint[] des = {rowCnt - 1, colCnt - 1};\n\t\t\tQueue<Snake> level = new LinkedList<>();\n\t\t\tSnake origin = new Snake(true, new int[] {0, 1});\n\t\t\tSet<String> visited = new HashSet<>();\n\t\t\tlevel.offer(origin);\n\t\t\tvisited.add(origin.id);\n\t\t\tint step = -1;\n\n\t\t\twhile (!level.isEmpty()) {\n\t\t\t\t// record the current queue size, these are all possible snake positions after "step" steps. We reocrd the size here because we could add more snake positions into the queue during iterations.\n\t\t\t\tint size = level.size();\n\t\t\t\tfor (int i = 0; i < size; i++) {  \n\t\t\t\t\tSnake curr = level.poll();\n\t\t\t\t\tif (curr.isHor && curr.headPos[0] == des[0] && curr.headPos[1] == des[1]) {\n\t\t\t\t\t\treturn step + 1;\n\t\t\t\t\t}\n\t\t\t\t\tSnake r = moveRight(curr, grid);\n\t\t\t\t\tSnake d = moveDown(curr, grid);\n\t\t\t\t\tSnake c = moveClock(curr, grid);\n\t\t\t\t\tSnake cc = moveCounter(curr, grid);\n\t\t\t\t\tif (!visited.contains(r.id) && r.headPos[0] != -1) {\n\t\t\t\t\t\tlevel.offer(r);\n\t\t\t\t\t\tvisited.add(r.id);\n\t\t\t\t\t}\n\t\t\t\t\tif (!visited.contains(d.id) && d.headPos[0] != -1) {\n\t\t\t\t\t\tlevel.offer(d);\n\t\t\t\t\t\tvisited.add(d.id);\n\t\t\t\t\t}\n\t\t\t\t\tif (!visited.contains(c.id) && c.headPos[0] != -1) {\n\t\t\t\t\t\tlevel.offer(c);\n\t\t\t\t\t\tvisited.add(c.id);\n\t\t\t\t\t}\n\t\t\t\t\tif (!visited.contains(cc.id) && cc.headPos[0] != -1) {\n\t\t\t\t\t\tlevel.offer(cc);\n\t\t\t\t\t\tvisited.add(cc.id);\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tstep++;\n\t\t\t}\n\t\t\treturn -1;\n\t\t}\n\n\t\tprivate Snake moveRight(Snake s, int[][] grid) {\n\t\t\tSnake success = new Snake(s.isHor, new int[] {s.headPos[0], s.headPos[1] + 1});\n\t\t\tif (isValid(success, grid)) {\n\t\t\t\tif (s.isHor && grid[s.headPos[0]][s.headPos[1] + 1] == 0) {\n\t\t\t\t\treturn success;\n\t\t\t\t} else if (!s.isHor\n\t\t\t\t   && grid[s.headPos[0]][s.headPos[1] + 1] == 0\n\t\t\t\t   && grid[s.headPos[0] - 1][s.headPos[1] + 1] == 0) {\n\t\t\t\t\treturn success;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn new Snake(s.isHor, new int[] {-1, -1}); \n\t\t}\n\n\t\tprivate Snake moveDown(Snake s, int[][] grid) {\n\t\t\tSnake success = new Snake(s.isHor, new int[] {s.headPos[0] + 1, s.headPos[1]});\n\t\t\tif (isValid(success, grid)) {\n\t\t\t\tif (!s.isHor\n\t\t\t\t   && grid[s.headPos[0] + 1][s.headPos[1]] == 0) {\n\t\t\t\t\treturn success;\n\t\t\t\t} else if (s.isHor\n\t\t\t\t   && grid[s.headPos[0] + 1][s.headPos[1]] == 0\n\t\t\t\t   && grid[s.headPos[0] + 1][s.headPos[1] - 1] == 0) {\n\t\t\t\t\treturn success;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn new Snake(s.isHor, new int[] {-1, -1}); \n\t\t}\n\n\t\tprivate Snake moveClock(Snake s, int[][] grid) {\n\t\t\tSnake success = new Snake(!s.isHor, new int[] {s.headPos[0] + 1, s.headPos[1] - 1});\n\t\t\tif (isValid(success, grid)) {\n\t\t\t\tif (s.isHor && grid[s.headPos[0] + 1][s.headPos[1]] == 0\n\t\t\t\t   && grid[s.headPos[0] + 1][s.headPos[1] - 1] == 0) {\n\t\t\t\t\treturn success;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn new Snake(s.isHor, new int[] {-1, -1});  \n\t\t}\n\n\t\tprivate Snake moveCounter(Snake s, int[][] grid) {\n\t\t\tSnake success = new Snake(!s.isHor, new int[] {s.headPos[0] - 1, s.headPos[1] + 1});\n\t\t\tif (isValid(success, grid)) { \n\t\t\t\tif (!s.isHor\n\t\t\t\t   && grid[s.headPos[0] - 1][s.headPos[1] + 1] == 0\n\t\t\t\t   && grid[s.headPos[0]][s.headPos[1] + 1] == 0) {\n\t\t\t\t\treturn success;\n\t\t\t\t}\n\t\t\t}\n\t\t\treturn new Snake(s.isHor, new int[] {-1, -1}); \n\t\t}\n\n\t\tprivate boolean isValid(Snake s, int[][] grid) {\n\t\t\tif (s.headPos[0] >= 0 && s.headPos[0] < grid.length \n\t\t\t\t&& s.headPos[1] >= 0 && s.headPos[1] < grid[0].length) {\n\t\t\t\treturn true;\n\t\t\t}\n\t\t\treturn false;\n\t\t}\n\t}\n\n\tclass Snake {\n\t\tboolean isHor;\n\t\tint[] headPos;\n\t\tString id;\n\n\t\tpublic Snake(boolean isHor, int[] headPos) {\n\t\t\tthis.isHor = isHor;\n\t\t\tthis.headPos = headPos;\n\t\t\tthis.id = isHor + "_" + headPos[0] + "_" + headPos[1];\n\t\t}\n\t}\n\t\n\xB7\xB7\xB7
[]