同学在google foobar上的一道题， 提交时候一直是400 bad request，估计是超时了，分享给我题目和他的解法，求优化
Prepare the Bunnies’’ Escape
You’‘re awfully close to destroying the LAMBCHOPdoomsday device and freeing Commander Lambda’‘s bunny prisoners, but oncethey’‘re free of the prison blocks, the bunnies are going to need to escapeLambda’‘s space station via the escape pods as quickly as possible.Unfortunately, the halls of the space station are a maze of corridors and deadends that will be a deathtrap for the escaping bunnies. Fortunately, CommanderLambda has put you in charge of a remodeling project that will give you theopportunity to make things a little easier for the bunnies. Unfortunately(again), you can’‘t just remove all obstacles between the bunnies and the escapepods - at most you can remove one wall per escape pod path, both to maintainstructural integrity of the station and to avoid arousing Commander Lambda’'ssuspicions.
You have maps of parts of the space station, each starting at a prison exit andending at the door to an escape pod. The map is represented as a matrix of 0sand 1s, where 0s are passable space and 1s are impassable walls. The door outof the prison is at the top left (0,0) and the door into an escape pod is atthe bottom right (w-1,h-1).
Write a function answer(map) that generates the length of the shortest pathfrom the prison door to the escape pod, where you are allowed to remove onewall as part of your remodeling plans. The path length is the total number ofnodes you pass through, counting both the entrance and exit nodes. The startingand ending positions are always passable (0). The map will always be solvable,though you may or may not need to remove a wall. The height and width of themap can be from 2 to 20. Moves can only be made in cardinal directions; nodiagonal moves are allowed.
Test cases
Inputs:
(int) maze = [[0, 1, 1, 0], [0, 0, 0,1], [1, 1, 0, 0], [1, 1, 1, 0]]
Output:
(int) 7
Inputs:
(int) maze = [[0, 0, 0, 0, 0, 0], [1,1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0,0, 0, 0, 0, 0]]
Output:
(int) 11未通过答案：（其实我两都在自己机子上通过的，跑的很快，方法就是dfs变形）：public static int answer(int[][] maze) {
// Your code goes here. boolean[][] visited = new boolean[maze.length][maze[0].length]; return dfs(0, 0, true, visited, maze, 1); } private static int dfs(int x, int y, boolean allowRemove, boolean[][] visited, int[][] maze, int len){ if(x == maze.length - 1 && y == maze[0].length - 1){ return len; } int[] dx = {0, 0, -1, 1}; int[] dy = {-1, 1, 0, 0}; visited[x][y] = true; int min = Integer.MAX_VALUE; for(int i = 0; i < 4; i++){ int nx = dx + x; int ny = dy + y; if(nx < 0 || ny < 0 || nx >= maze.length || ny >= maze[0].length || visited[nx][ny]){ continue; } if(maze[nx][ny] == 0){ min = Math.min(dfs(nx, ny, allowRemove, visited, maze, len + 1), min); }else if(allowRemove){ min = Math.min(dfs(nx, ny, false, visited, maze, len + 1), min); } if(min == maze.length + maze[0].length - 1){ break; } } visited[x][y] = false; return min; }