READ AND SOLVE VERY CAREFULLY WITH PYTHON thanks in advance Given a jungle matrix NM: 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 44 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

Related questions

Question

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

Expert Solution

Step 1: Algorithm

Initialize the jungle matrix, where '0' represents dead ends, and '1' represents valid paths.
Create a solution matrix of the same size as the jungle matrix, initially filled with zeros.
Start at the top-left corner (0, 0) of the jungle matrix.
Call a recursive function solve_jungle with the current position (0, 0) and pass the jungle and solution matrices.
Inside solve_jungle:
- Check if the current position is the destination (bottom-right corner of the matrix).
  - If yes, mark the current position in the solution matrix as '1' and return True.
- Check if it's a valid move (within bounds and '1' in the jungle matrix).
  - If yes, mark the current position in the solution matrix as '1'.
  - Recursively call solve_jungle in two directions:
    - Move forward horizontally by calling solve_jungle(jungle, solution, x + 1, y).
    - Move down vertically by calling solve_jungle(jungle, solution, x, y + 1).
    - If either of these calls returns True, return True to indicate a valid path.
- If no valid move leads to a solution, unmark the current position in the solution matrix by setting it back to '0'.
- Return False to indicate that no path is found from this position.
In the main function:
- Initialize the jungle matrix and the solution matrix.
- Call solve_jungle starting from the top-left corner (0, 0).
- If a path is found, print the solution matrix.
- If no path is found, print a message indicating you're trapped in the jungle.

Step by step

Solved in 4 steps with 2 images

SEE SOLUTION Check out a sample Q&A here