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, ,

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[] 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

}

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;

//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.

• -22

 » 8 years ago, # |   0 mistake identified. Thanks for -22