Function Name: lostWoods Inputs: 1. 2. 3. (char) The file name of an image of a
ID: 3700482 • Letter: F
Question
Function Name: lostWoods Inputs: 1. 2. 3. (char) The file name of an image of a maze (double) The row index of the maze entrance (double) The column index of the maze entrance File Outputs 1. An image of the solved maze Background You stand at the entrance of a dark, deep forest You only see shadow ahead of you, but still you step in. The old stories say that somewhere deep in these woods lie riches and glory beyond your wildest imagination, and the allure of the treasure overcomes your fear. You take a few steps into the woods and are shrouded in darkness-you stop while you can still see the light of the entrance behind you. There must be a better way... Function Description: Write a function in MATLAB that takes in the name of an image file. This image is a map of the forest, and you are going to find the path to the treasure before you even step into the maze! The image can be of any size, but the rows and columns are divisible by 20- the maze is made of 20x20 solid colored squares. The walls of the maze are dark green, RGB(13,102,35) the paths of the maze are a lighter green, RGB(66,244,92), and the treasure is a gold colo RGB(255,223,0). The second and third inputs to the function are the indices of where the start square is on the edge of the maze. Your job is to solve the maze by drawing a path from the maze entrance to the treasure. To draw this path, change the color from the lighter green to gold (RGB(255,223,0)) at every square along the path. You will save this to a new image that has the original filename with 'solved' appended. Example If the image on the left is called maze.png, then running lostwoods( maze.png,1,7) should produce the image on the right, maze solved.png ContinuedExplanation / Answer
public class SolvedMaze
{
final int N = 4;
/* A utility function that will print solution matrix solution[N][N] */
void printSolution(int solution[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + solution[i][j] + " ");
System.out.println();
}
}
/* A utility function to check if x,y is valid index for N*N maze */
boolean isSafe(int maze[][], int x, int y)
{
// if (x,y outside maze) return false
return (x >= 0 && x < N && y >= 0 &&
y < N && maze[x][y] == 1);
}
/* This function solves the Maze problem using Backtracking. It mainly uses solveMazeUtil() to solve the problem. It returns false if no path is possible,
otherwise return true and prints the path in the form of 1s. Please note that there may be more than one solutions, this function prints one of the feasible solutions.*/
boolean solveMaze(int maze[][])
{
int solution[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if (solveMazeUtil(maze, 0, 0, solution) == false)
{
System.out.println("Solution doesn't exist");
return false;
}
printSolution(solution);
return true;
}
/* A recursive utility function to solve Maze problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int solution[][])
{
// 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
solution[x][y] = 1;
/* Move forward in x direction */
if (solveMazeUtil(maze, x + 1, y, solution))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, solution))
return true;
/* If none of the above movements work then
BACKTRACK: unmark x,y as part of solution
path */
solution[x][y] = 0;
return false;
}
return false;
}
/*Example problem to show that the solution works fine. */
public static void main(String args[])
{
SolvedMaze rat = new SolvedMaze();
int maze[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
rat.solveMaze(maze);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.