optimize destination not reachable or stoppable then dfs, beat 93% java


  • 1
    Y

    it can optimize by the destination is not reachable or is not stoppable. and then dfs
    refer @monkeyGoCrazy https://discuss.leetcode.com/topic/78133/simple-dfs-solution-beat-97

     public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;       
        int x = destination[0], y = destination[1];
        boolean dL = canRoll(maze,x,y-1);    
        boolean dR = canRoll(maze,x,y+1);
        boolean dU = canRoll(maze,x-1,y);
        boolean dD = canRoll(maze,x+1,y);
        if(dL && dR && dD && dU) return false; //all neighbors are walls
        if(!(dL || dR || dD || dU)) return false; //all neighbors are empty 
        if(dL&& dR && ! dD && !dU) return false; //two opposite walls
        if(!dL&& !dR && dD && dU) return false; //two opposite walls      
        boolean[][] flag = new boolean[m][n];
        return dfs(maze,start,destination,flag);
     }
    
    public boolean dfs(int[][] maze, int[] start, int[] dest,boolean[][] flag){
        int m = maze.length, n = maze[0].length;
        int x = start[0], y = start[1];
        if(flag[x][y]) return false;
        flag[x][y] = true;
        if(x == dest[0] && y == dest[1]) return true;
        
        //left
        if (y > 0 && maze[x][y-1] == 0 ) {
            int i = y - 1;
            while (i > 0 && maze[x][i-1] == 0 ) i--;
            if (dfs(maze, new int[]{x, i}, dest, flag)) return true;
        }
        //right
        if (y < n-1 && maze[x][y+1] == 0) {
            int i = y+1;
            while (i < n-1 && maze[x][i+1] == 0 ) i++;
            if (dfs(maze, new int[]{x, i}, dest, flag)) return true;
        }
        
        //up
        if ( x > 0 && maze[x-1][y] == 0 ) {
            int i = x - 1;
            while (i > 0 && maze[i-1][y] == 0 ) i--;
            if (dfs(maze, new int[]{i, y}, dest, flag)) return true;
        }
        //down
        if (x < m-1 && maze[x+1][y] == 0) {
            int i = x+1;
            while (i < m-1 && maze[i+1][y] == 0 ) i++;
            if (dfs(maze, new int[]{i, y}, dest, flag)) return true;
        }
        return false;
    }
    
      public boolean canRoll(int[][] maze, int x, int y){
        if(x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] == 1) 
          return false;
        return true;
    }

  • 1
    I

    Obviously you mismatched all the directions comments...


  • 0
    Y

    @iamone14 modify the direct comment


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.