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.
mistake identified. Thanks for -22