Java maze problem: Given a maze represented by a 2-dimensional array with 0’s (w
ID: 3717634 • Letter: J
Question
Java maze problem: Given a maze represented by a 2-dimensional array with 0’s (wall) and 1’s (open path), the goal is to find the path from a given initial location (rowIni, colIni) to a final location (rown, coln) using recursive backtracking. A move can be made to a location only if there is 1 in the neighboring coordinate. A position that is part of path should be marked with the character +. When a path from initial location to final location is found, print the solution path of the maze.
Create a class Maze and code the method findMazePath:
public static boolean findPathMaze(int rowIni,int colIni,char[][] maze)
For example, consider the input maze:
1 0 1 0 0 0
1 1 1 1 1 0
1 0 0 0 1 0
0 1 1 1 1 0
1 0 1 0 0 0
0 1 1 1 1 1
Your code should find and mark with the character + the path from initial position (0, 0) to final position (nRow ? 1, nCol ? 1), where nRow is the number of rows and nCol is the number of columns. An example output for this maze is shown below:
+ 0 1 0 0 0
+ + + + + 0
1 0 0 0 + 0
0 # + + + 0
1 0 + 0 0 0
0 1 + + + +
The character # indicates when backtracking happened.
Explanation / Answer
Below code helps to solve the maze and is written in 4*4 grid you can simply extend the dimension length.
Hope this helps...
Thankyou..... :)
/* Java program to solve Rat in a Maze problem using
backtracking */
public class Maze
{
final int N = 4;
/* A utility function to print solution matrix
sol[N][N] */
void printSolution(int sol[][])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
System.out.print(" " + sol[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 sol[][] = {{0, 0, 0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}
};
if (solveMazeUtil(maze, 0, 0, sol) == false)
{
System.out.print("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
/* A recursive utility function to solve Maze
problem */
boolean solveMazeUtil(int maze[][], int x, int y,
int sol[][])
{
// 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 (solveMazeUtil(maze, x + 1, y, sol))
return true;
/* If moving in x direction doesn't give
solution then Move down in y direction */
if (solveMazeUtil(maze, x, y + 1, sol))
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;
}
public static void main(String args[])
{
Maze rat = new Maze();
int maze[][] =
{ {1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
rat.solveMaze(maze);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.