Given a jungle matrix NxM: jungle = [ [1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1,1 1 Where O 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: If destination is reached Dest. 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 solutio If none of the above solution work, unmark the cell and return false
Please use Python
![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%2F1628c2fe-4549-4fee-9365-6836b65269c2%2Ffbs5ma_processed.png&w=3840&q=75)
1. Define a function `find_path(jungle)` to find a path through the jungle matrix and create a solution matrix.
2. Get the dimensions of the jungle matrix:
- `N` = number of rows
- `M` = number of columns
3. Create an empty solution matrix:
- `solution` = a 2D matrix filled with 0s of size N x M
4. Define a recursive function `find_path_recursive(x, y)` that takes the current position `(x, y)` as input:
- Check if the current position is the destination (i.e., `x == N - 1` and `y == M - 1`).
- If true, mark the destination cell in the solution matrix as 1 and return True (path found).
- Check if the current position is a valid path (i.e., `jungle[x][y] == 1`).
- If true, mark the current cell in the solution matrix as 1.
- Try moving forward horizontally by calling `find_path_recursive(x + 1, y)` recursively.
- If this leads to a solution (returns True), return True.
- If moving horizontally doesn't lead to a solution, try moving down by calling `find_path_recursive(x, y + 1)` recursively.
- If this leads to a solution (returns True), return True.
- If neither of the above options works, unmark the current cell in the solution matrix (backtrack) by setting it to 0 and return False (no path found).
- If the current position is not a valid path (i.e., `jungle[x][y] != 1`), return False.
5. Start the recursive search from the top-left corner (0, 0) by calling `find_path_recursive(0, 0)`.
6. After the search:
- If a path is found (the `find_path_recursive` function returns True), print the solution matrix, which now contains the marked path.
- If no path is found (the `find_path_recursive` function returns False), print the message "Trapped in the jungle - No path found."
Step by step
Solved in 4 steps with 1 images
