Given a jungle matrix NxM: jungle = [ [1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1,] ] Where 0 means the block is dead end and 1 means the block can be used in the path from source to destination. Task: Starting at position (0, 0), the goal is to reach position (N-1, M-1). Your program needs to build and output the solution matrix – a 4x4 matrix with 1’s in positions used to get from the starting position (0,0) to the ending position (N-1,M-1) with the following constraints: You can only move one space at a time You can only in two directions: forward and down. You can only pass thru spaces on the jungle matrix mark ' 1 ' If you cannot reach the ending position - print a message that you're trapped in the jungle Algorithm: If destination is reached print the solution matrix Else Mark current cell in the solution matrix Move forward horizontally and recursively check if this leads to a solution If there is no solution, move down and recursively check if this leads to a solution If none of the above solution work, unmark the cell and return False Solution matrix = [ [1, 0, 0, 0], [1, 1, 0, 0], [0, 1, 0, 0], [0, 1, 1, 1] ] CODE: import java.util.Arrays; /** * * * * J U N G L E E S C A P E A L G O R I T H M * * * * * if destination is reached * print the solution matrix * else * a. Mark current cell in the solution matrix * b. Move forward horizontaly and recursively check if this leads to a solution * c. If there is no solution, move down and recursively check if this leads to a solution * d. If none of the above solution work, unmark the cell and return False * */ public class JungleMaze { /** * Utility to check if the current cell position (x,y) is in the maze */ boolean isSafe(int maze[][], int x, int y, int sol[][]) { // Get maze dimensions int X = maze[1].length; int Y = maze.length; if (x >= 0 && x < X && y >= 0 && y < Y && maze[x][y] == 1) return true; return false; } /** * (x,y) is the current cell position */ boolean solveMaze(int maze[][], int x, int y, int[][] sol) { // Get maze size int X = maze[1].length; int Y = maze.length; // check if (x,y) is goal if (x == X - 1 && y == Y - 1) { sol[x][y] = 1; return true; } // Check if we're inside the maze if (isSafe(maze, x, y, sol)) { // Mark the current cell in solution (BACKTRACK) sol[x][y] = 1; // Move right // if recursive call // return true; // Move down // if recursive call // return true; // // Remove current cell from solution // do something to the sol // If the 2 moves above failed // return false; } // else return false; } public static void main(String[] args) { // Initiate the maze int maze[][] = { { 1, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 0 }, { 1, 1, 1, 1, } }; // Initiate the solution matrix int sol[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } }; JungleMaze mazeTester = new JungleMaze(); // Given a maze NxM, if (mazeTester.solveMaze(maze, 0, 0, sol)) { // print the solution matrix here System.out.println(Arrays.deepToString(sol)); }else System.out.println("No solution"); } }
Given a jungle matrix NxM:
jungle = []
Where 0 means the block is dead end and 1 means the block can be used in the path from source to destination.
Task:
Starting at position (0, 0), the goal is to reach position (N-1, M-1).
Your program needs to build and output the solution matrix – a 4x4 matrix with 1’s in positions used to get from the starting position (0,0) to the ending position (N-1,M-1) with the following constraints:
You can only move one space at a time
You can only in two directions: forward and down.
You can only pass thru spaces on the jungle matrix mark ' 1 '
If you cannot reach the ending position - print a message that you're trapped in the jungle
If destination is reached
print the solution matrix
Else
Mark current cell in the solution matrix
Move forward horizontally and recursively check if this leads to a solution
If there is no solution, move down and recursively check if this leads to a solution
If none of the above solution work, unmark the cell and return False
Solution matrix =
[ [1, 0, 0, 0],
[1, 1, 0, 0],
[0, 1, 0, 0],
[0, 1, 1, 1] ]
CODE:
import java.util.Arrays;
/**
*
* * * J U N G L E E S C A P E A L G O R I T H M * * *
*
* if destination is reached
* print the solution matrix
* else
* a. Mark current cell in the solution matrix
* b. Move forward horizontaly and recursively check if this leads to a solution
* c. If there is no solution, move down and recursively check if this leads to a solution
* d. If none of the above solution work, unmark the cell and return False
*
*/
public class JungleMaze {
/**
* Utility to check if the current cell position (x,y) is in the maze
*/
boolean isSafe(int maze[][], int x, int y, int sol[][]) {
// Get maze dimensions
int X = maze[1].length;
int Y = maze.length;
if (x >= 0 && x < X && y >= 0 && y < Y && maze[x][y] == 1)
return true;
return false;
}
/**
* (x,y) is the current cell position
*/
boolean solveMaze(int maze[][], int x, int y, int[][] sol) {
// Get maze size
int X = maze[1].length;
int Y = maze.length;
// check if (x,y) is goal
if (x == X - 1 && y == Y - 1) {
sol[x][y] = 1;
return true;
}
// Check if we're inside the maze
if (isSafe(maze, x, y, sol)) {
// Mark the current cell in solution (BACKTRACK)
sol[x][y] = 1;
// Move right
// if recursive call
// return true;
// Move down
// if recursive call
// return true;
//
// Remove current cell from solution
// do something to the sol
// If the 2 moves above failed
// return false;
}
// else
return false;
}
public static void main(String[] args) {
// Initiate the maze
int maze[][] = { { 1, 0, 0, 0 }, { 1, 1, 0, 1 }, { 0, 1, 0, 0 }, { 1, 1, 1, 1, } };
// Initiate the solution matrix
int sol[][] = { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
JungleMaze mazeTester = new JungleMaze();
// Given a maze NxM,
if (mazeTester.solveMaze(maze, 0, 0, sol)) {
// print the solution matrix here
System.out.println(Arrays.deepToString(sol));
}else
System.out.println("No solution");
}
}
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
