谷歌foobar挑戰與dfs解決方案的錯誤

我收到了邀請，以加強谷歌代碼的挑戰。我遇到了一個問題，就像在迷宮中找到最小路徑，而允許最多移除一面牆。我提交我的代碼，只有400 bad request。我對此有點困惑，因爲我不知道這是我的代碼問題。下面是我的代碼，它可能會冒很大的時間複雜性：谷歌foobar挑戰與dfs解決方案的錯誤

public class Answer { 
    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[i] + x; 
      int ny = dy[i] + 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; 
    } 
}

來源

2016-09-26 Anderson

你有沒有發現什麼辦法來解決這個問題。我一直讓時間過期。任何建議優化將不勝感激。 – rizzz86

對不起請問，但你是如何得到邀請？

當每個人都注意到它時（當不可能的遊戲出現時）有一個，但沒有及時解決所有挑戰，並且我只是邀請過期。

而且有人在堆棧溢出居然進了同一個問題，本書雖然不知道是不是想通了：Google foobar responds with Error(400)

來源

2016-09-28 23:27:12 Nowahe

谷歌foobar挑戰與dfs解決方案的錯誤

回答

相關問題