Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

upsolving's blog

By upsolving, 8 years ago, In English,

I am stuck with this backtracking problem. I think there is mistake in my recursive code (loops or recursive calls) but I could not make out what it is.

I my pasting my code. Help from any one will be appreciated.

VERSION 1:

public class Obstacle {
    boolean[][] visited;
    int bestAnswer = 0;
    
    int[] dx = {0, 1, 0, -1};
    int[] dy = {1, 0, -1, 0};
    //**************PROGRAM STARTS HERE**********************
    public int getLongestPath(int[] a){
        visited = new boolean[5][5];
     
        for(int i = 0; i < a.length; i++) visited[a[i] / 5][a[i] % 5] = true;        
       
        doit(0, 0, 0, 0); //move down 
        doit(0, 0, 1, 0); //move right
        
        return bestAnswer;
    }
    
     boolean isSafe(int x, int y){
        if(x < 0 || x >= 5 || y < 0 || y >= 5 || visited[x][y]) return false;
        return true;
    }

   private void doit(int x, int y, int direction, int counts ){
        if(!isSafe(x, y)) return;
        
        visited[x][y] = true;
        counts = counts + 1; 
        bestAnswer = Math.max(bestAnswer, counts);
        
        //if safe to move in same direction move on
       if(isSafe(x + dx[direction], y + dy[direction])) doit(x + dx[direction], y + dy[direction], direction, counts);
       else{
           //if moving direction is vertical before getting blocked then try moving left & right
           if(direction % 2 == 0){ 
                doit(x + dx[1], y + dy[1], 1, counts);
                doit(x + dx[3], y + dy[3], 3, counts);
           }else{  //if moving direction is horizontal before getting blocked then try moving up & down
               doit(x + dx[1], y + dy[1], 0, counts);
               doit(x + dx[2], y + dy[2], 2, counts);
           }
       }
       //backtrack
        visited[x][y] = false;   
    }
            
}

please do explain why my backtracking approach is not working.

 
 
 
 
  • Vote: I like it
  • -22
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

mistake identified. Thanks for -22