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.
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);
}
}
Java maze problem: Given a maze represented by a 2-dimensional array with 0’s (wall) and 1’s...
Maze Solving with Stacks Problem Statement Consider a maze made up of rectangular array of squares, such as the following one: X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X Figure...
JAVA QUESTION!!! please help! The following codes are a Maze program. There are TWO traversable paths possible in this maze. The program uses recursion. Can someone please explain to me why the program will pick one path if multiple traversable paths are available? Why does the program choose one path over a different path? (I believe it has something to do with the recursion terminating when a solution is found but I'm not sure.) Thank you!!!! The codes: public class...
In this question, you will test, using a backtracking algorithm, if a mouse can escape from a rectangular maze. To ensure consistency of design, start your solution with maze_start.c. The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the escape hatch or exhausts all possible routes (and concludes that the mouse is trapped in the maze). If the backtracking algorithm finds a dead end, it retraces its path until it...
The Problem A robot is asked to navigate a maze. It is placed at a certain position (the starting position) in the maze and is asked to try to reach another position (the goal position). Positions in the maze will either be open or blocked with an obstacle. Positions are identified by (x,y) coordinates. At any given moment, the robot can only move 1 step in one of 4 directions. Valid moves are: ● Go North: (x,y) -> (x,y-1) ●...
This program will make Maze game. Please Help in c++ Prompt the user for a file that contains the maze. Read it into a two-dimensional array Remember you can use inputStream.get(c) to read the next character from the inputStream. This will read whitespace and non-whitespace characters Don’t forget to read the newline character at the end of each line Print the maze to the screen from your array You should include a ‘*’ in your maze to indicate where the...
I NEED HELP IN MAZE PROBLEM. Re-write the following program using classes. The design is up to you, but at a minimum, you should have a Maze class with appropriate constructors and methods. You can add additional classes you may deem necessary. // This program fills in a maze with random positions and then runs the solver to solve it. // The moves are saved in two arrays, which store the X/Y coordinates we are moving to. // They are...
1.The code box below includes a live 2 dimensional array variable called gridNums. This array holds integers. You cannot see its declaration or initialization. What value is in the zeroth (initial) position of the second row? Print this array entry to the console. (Note: remember that the second row is actually row 1). Enter your code in the box below. 2.The code box below includes a live 3x3 2-dimensional array variable called fredsNums. This array holds integers. You cannot see...
Write Java code to implement a FSM machine that recognizes the language for the alphabet {a,b,c} consisting of all strings that contain two consecutive c's and end with b. Your FSM program should include the following three static methods (Java) or functions (C): a. int nextState(int state, char symbol) A state-transition function that returns the next state based on the current state and an input symbol. This function should also return -1 when an invalid input character is detected. State...
Assignment 1) Your function will only write the Nth character of the array, supplied as a parameter by the caller. This is an example prototype (although you may want to change the return value type, based on the second twist, below). void writeArrayNthBackward(const char [], int, int, int); The first three arguments serve the same purpose as in the iterative example. The fourth argument (an int) supplies the N for the Nth character to print in the array. If n...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(), valence(int vid), DFS(int start), and findPathBFS(int start, int end). I also have a JUnit test file GraphTest.java for you to check your code. Here is Graph.java: import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /* Generic vertex class */ class Vertex<T> { public T data; public boolean visited; public Vertex() { data = null; visited = false; } public Vertex(T _data) { data =...