`I got stack overflow error when using this code. i want it work if we already found the shortest path, then the recursive code will stop. the maze is contain character '#' and ' '. and if i found the shortest path, the path will mark with '.' please help thank you.
public static int getCoordinateY(String location){ //to get x coordinate
String y = location.substring(2, 4);
int coor = (y.charAt(0) - 'Q') * 10 + Character.getNumericValue(y.charAt(1));`enter code here`
return coor;
}
public boolean canPass(int y,int x) { //you can keep going if you not found # and .
if(map[y][x] == '#' || map[y][x] == '.' ) {
return false;
}
return true;
}
public Character[][] cloneArray(Character[][] src) { //copy array
int length = src.length;
Character[][] target = new Character[length][src[0].length];
for (int i = 0; i < length; i++) {
System.arraycopy(src[i], 0, target[i], 0, src[i].length);
}
return target;
}
public void finish(int x,int y){ //goal
xgoal=x;
ygoal=y;
}
public int getDistance(){ //shortest distance from shortest path
return finalDistance;
}
public void shortestPathStart(int xStart,int yStart, int xEnd, int yEnd){
set('S',xStart,yStart); //start coordinate
finish(xEnd,yEnd);
shortestPathRec(xStart+1,yStart,0,map);//to right
shortestPathRec(xStart-1,yStart,0,map);// to left
shortestPathRec(xStart,yStart+1,0,map);//to up
shortestPathRec(xStart,yStart-1,0,map);// to down
map = result; //final map with '.'
set('F',xEnd,yEnd);
print();
}
public void shortestPathRec(int x,int y,int step,Character[][] map){
if(canPass(x,y)){
step++;
Character[][] temp = cloneArray(map);
temp[x][y] = '.'; //in the maze, '.' using for flags
if(x == xgoal && y == ygoal){//if already found the goal
hasDone = true;
finalDistance = step;
result = temp;
return;
}
if(hasDone==true && finalDistance<step){ //if shortest path is found other path should be in this condition
return;
}
shortestPathRec(x+1,y,step,temp);//calltherecursive again
shortestPathRec(x-1,y,step,temp);
shortestPathRec(x,y+1,step,temp);
shortestPathRec(x,y-1,step,temp);
}
}
PROBLEM ANALYSIS
You fail to guard against physical backtracking: you move to a wall, but instead of backing up in your call stack (undo the last move), you go to the next recursion call and do the opposite move -- taking a second useless step instead of backing up to 0 useless steps. Your code will infinitely walk between those two squares until you exceed the stack limit.
REPAIR
Madify your code so that you never walk to a square you've already visited on this path. This is easy enough to research on line; Dijkstra's Algorithm is one of the earliest general solutions.
AVOIDANCE
Learn basic debugging. Among other things, insert print statements at entry and exit to each routine, printing the input parameters and return values. For extra clarity, keep an depth counter and indent the prints appropriately.