I am currently attempting to write a method for a maze. I pass the starting poin
ID: 3627466 • Letter: I
Question
I am currently attempting to write a method for a maze. I pass the starting point to the method.1. I check to see it is within bounds if it isn't then it doesn't work
2. I check to see if it is the end point. If it is then exit method. If it is:
3. I check up down left and right
My code is:
public boolean solveMaze(int x, int y)
{
boolean solve=false;
if ( x<0 || x>=mazeSolve.length || y<0 || y>=mazeSolve[0].length )
solve=false;
if (x == endx && y==endy)//base case
{
solve = true; //the maze is solved
}
if(!solve){
if(mazeSolve[x+1][y]=='.')//moves down
solve=solveMaze(x+1,y);
if(mazeSolve[x][y+1]=='.')//moves right
solve=solveMaze(x,y+1);
if(mazeSolve[x-1][y]=='.')//moves up
solve=solveMaze(x-1,y);
if(mazeSolve[x][y-1]=='.')//moves left
solve=solveMaze(x,y-1);
}
return solve;
}//end solveMaze
It compiles but when I run it I get:
at MazeSolver.solveMaze(MazeSolver.java:92)
at MazeSolver.solveMaze(MazeSolver.java:88)
at MazeSolver.solveMaze(MazeSolver.java:92)
at MazeSolver.solveMaze(MazeSolver.java:88)
at MazeSolver.solveMaze(MazeSolver.java:92)
at MazeSolver.solveMaze(MazeSolver.java:88)
at MazeSolver.solveMaze(MazeSolver.java:92)
lines 88 and 92 are:
Line 88:
solve=solveMaze(x+1,y);
Line 92:
solve=solveMaze(x-1,y);
I can't get this right...please someone help!!
Explanation / Answer
You're getting a stack overflow because you're recursively calling solveMaze() on the same square many times. Mark locations as searched to fix this.
public boolean solveMaze(int x, int y)
{
boolean solve=false;
if ( x<0 || x>=mazeSolve.length || y<0 || y>=mazeSolve[0].length )
return false; // prevent IndexOutOfBoundsException
if (x == endx && y==endy)//base case
return true; //the maze is solved
if(!solve){
//****
// mark this location as searched
mazeSolve[x][y] = 's';
//****
if(mazeSolve[x+1][y]=='.')//moves down
solve = solve||solveMaze(x+1,y);
if(mazeSolve[x][y+1]=='.')//moves right
solve = solve||solveMaze(x,y+1);
if(mazeSolve[x-1][y]=='.')//moves up
solve = solve||solveMaze(x-1,y);
if(mazeSolve[x][y-1]=='.')//moves left
solve = solve|| solveMaze(x,y-1);
}
return solve;
}//end solveMaze
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.