谷歌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; 
    } 
}

你有没有发现什么办法来解决这个问题。我一直让时间过期。任何建议优化将不胜感激。 – rizzz86

答

对不起请问，但你是如何得到邀请？

当每个人都注意到它时（当不可能的游戏出现时）有一个，但没有及时解决所有挑战，并且我只是邀请过期。

而且有人在堆栈溢出居然进了同一个问题，本书虽然不知道是不是想通了：Google foobar responds with Error(400)

谷歌foobar挑战与dfs解决方案的错误

相关推荐