Use the following information to find if a possible solution exists for an input
ID: 3836718 • Letter: U
Question
Use the following information to find if a possible solution exists for an input maze.
The rules of traversal are:
S - represents the starting point (start)
D - represents the ending point (destination)
X - represents a cell you cannot enter
B - represents an open cell you can travel to (converted to a blank space within program)
# - represents a border cell
* - represents a cell you have already traveled to
@ - represents a cell that you found lead to an impossible solution
Travel from point S to point D using a recursive function solvemaze. You should start with the file maze.cpp attached to this assignment link.
Explanation / Answer
ANSWER:
Here is the code to solve maze using a recursive utility function 'solvemaze';
where,x=row and y=column,N= size,found=sol
//Solving a maze using recursive function
bool solveMaze(int maze[N][N], int x, int y, int sol[N][N])
{
// if (x,y is goal) return true
if(x == N-1 && y == N-1)
{
sol[x][y] = 1;
return true;
}
// Check if maze[x][y] is valid
if(isSafe(maze, x, y) == true)
{
// mark x,y as part of solution path
sol[x][y] = 1;
/* Move forward in x direction */
if (solveMaze(maze, x+1, y, sol) == true)
return true;
/* If moving in x direction doesn't give solution then
Move down in y direction */
if (solveMaze(maze, x, y+1, sol) == true)
return true;
/* If none of the above movements work then BACKTRACK:
unmark x,y as part of solution path */
sol[x][y] = 0;
return false;
}
return false;
}
// driver program to test above function
int main()
{
int maze[N][N] = { {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
solveMaze(maze);
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.