READ AND SOLVE VERY CAREFULLY WITH PYTHON thanks in advance Given a jungle matrix N*M: 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: (Use Python) 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 4*4 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 move in two directions: forward and down. - You can only pass thru spaces on the jungle matrix marked ‘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
READ AND SOLVE VERY CAREFULLY WITH PYTHON
thanks in advance
Given a jungle matrix N*M:
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: (Use Python)
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 4*4 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 move in two directions: forward and down.
- You can only pass thru spaces on the jungle matrix marked ‘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
![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.
Source
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 marked '1'
If you cannot reach the ending position-print a message that you're trapped in the
jungle
Algorithm:
Dest.
If destination is reached
Else
print the solution matrix
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](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F647bdb98-546a-4b87-b943-0637858a6273%2F47ccdf3d-9fa4-4393-86a8-3e04419484dd%2F0m5j2xt_processed.png&w=3840&q=75)
In the given problem, we are provided with a "jungle" represented as a 2D matrix. The objective is to navigate through this matrix starting from the top-left corner and arriving at the bottom-right corner. In the matrix, the number '1' represents a path, while the number '0' represents a dead end. The challenge lies in determining a path (if it exists) through the maze based on the rules provided.
Algorithm
Initialization: Start from the first cell of the matrix (0,0).
Destination Check: If the destination (N-1, M-1) is reached and it's a valid path (value 1), mark the cell and conclude that a solution exists.
Validity Check: For the current cell, check if it is within the matrix boundaries and has a value of 1. If not, return False indicating the path cannot proceed from this cell.
Mark Current Cell: If the current cell is valid, mark it as part of the solution path.
Recursive Movement - Horizontal: Move horizontally (i.e., to the cell on the immediate right). Recursively apply the algorithm. If this leads to a solution (eventually reaching the destination), the function returns True.
Recursive Movement - Vertical: If the horizontal move doesn't lead to a solution, move vertically (i.e., to the cell immediately below). Again, apply the algorithm recursively. If this path reaches the destination, the function returns True.
Backtracking: If neither horizontal nor vertical movements lead to a solution, it means the current cell does not lie on the correct path. Therefore, unmark the cell (reset its value in the solution matrix) and backtrack, returning False.
Solution Matrix: If a path through the jungle exists, the solution matrix will have '1' marked in all cells that are part of the path from the start to the destination. If no path exists, an appropriate message is shown.
Step by step
Solved in 5 steps with 1 images
