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"); } }