You are given as input a maze in the following format: • two integers h and w sp

Question

You are given as input a maze in the following format: • two integers h and w specifying the height and width of the maze, respectively. • the maze as a 2D array M[1...h][1...w], in the following form: – M[i][j] = 0: position (i, j) is free. – M[i][j] = 1: position (i, j) is a wall. You start the maze at position (1, 1) and the finish position is (h, w) (assume both of these positions are free). You can move between spaces in the maze if both spaces are free and are immediately adjacent either up, down, left, or right. Describe how to determine if a path in the maze exists from the start position to the finish position, and if such a path exists, output the length of the shortest path. Analyze the running time of your algorithm in terms of w and h. Here is an example maze with w = h = 4, where (1, 1) is the top left corner. The shortest path has length 6: (1, 1) (1, 2) (1, 3) (2, 3) (3, 3) (4, 3) (4, 4).

This is the matrix

0 0 0 0

1 1 0 1

0 1 0 1

0 0 0 0

Hint: Convert the maze into a graph)

Explanation / Answer

Alogrithm
int[][] maze = new int[w][h]; // The maze, w as width and h as height
boolean[][] wasHere = new boolean[w][h];
boolean[][] correctPath = new boolean[w][h]; // The solution to the maze
int startP, startQ; // Starting P and Q values of maze
int endP, endQ; // Ending P and Q values of maze

public void Mazesolve()
{
maze = generateMaze(); // Create Maze (1 IS path, 2 IS wall)
for (int row = 0; row < maze.length; row++)
// Fix the boolean Arrays to the default values
for (int col = 0; col < maze[row].length; col++){
wasHere[row][col] = false;
correctPath[row][col] = false;
}
boolean b = recursiveSolve(startP, startQ);
//WITH this it Will leave you with a boolean array i.e correctPath
// with the path indicated by true values.
// If b is set to false then there is no answer to the maze
}
public boolean recursiveSolve(int p, int q) {
if (p == endP && q == endQ)
return true; // If you reached the end
if (maze[p][q] == 2 || wasHere[p][q])
return false;
// If you are on a wall or already were here
wasHere[p][q] = true;
if (p != 0) // Checks if not on left edge
if (recursiveSolve(p-1, q)) { // Recalls method one to the left
correctPath[p][q] = true; // Sets that path value to true;
return true;
}
if (p != width - 1) // Checks if not on right edge
if (recursiveSolve(p+1, q)) { // Recalls method one to the right
correctPath[p][q] = true;
return true;
}
if (q != 0) // Checks if not on top edge
if (recursiveSolve(p, q-1)) { // Recalls method one up
correctPath[p][q] = true;
return true;
}
if (q != height- 1) // Checks if not on bottom edge
if (recursiveSolve(p, q+1)) { // Recalls method one down
correctPath[p][q] = true;
return true;
}
return false;
}

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.