QUESTION 04 bookmark_border Roco is an island near Africa which is very prone to forest fire. Forest fire is such that it destroys the complete forest. Not a single tree is left. This island has been cursed by God , and the curse is that whenever a tree catches fire, it passes the fire to all its adjacent tree in all 8 directions, North, South, East, West, North-East, North-West, South-East, and South-West. And it is given that the fire is spreading every minute. Trees (indicated by T) and water (indicated by W) spots are arranged in a grid of MxN M-rows N-Columns. Your task is that given the location of the first tree that catches fire, determine how long would it take for the entire forest to be on fire. You may assume that the lay out of the forest is such that the whole forest will catch fire for sure and that there will be at least one tree in the forest. Input Format: First line contains two integers, M, N, space separated, giving the size of the forest in terms of the number of rows and columns respectively The next line contains two integers X,Y, space separated, giving the coordinates of the first tree that catches the fire The next M lines, where ith line containing N characters each of which is either T or W, giving the position of the Tree and Water in the ith row of the forest. Output Format: Single integer indicating the number of minutes taken for the entire forest to catch fire Constraints: 3 ≤ M ≤ 20 3 ≤ N ≤ 20 Sample Input - 1: 3 3 1 3 W T T T W W W T T Sample Output - 1: 5 Explanation: In the second minute, tree at (1,2) catches fire. In the third minute, the tree at (2,1) catches fire, fourth minute tree at (3,2) catches fire and in the fifth minute the last tree at (3,3) catches fire. Sample Input - 2: 6 6 1 6 W T T T T T T W W W W W W T T T T T W W W W W T T T T T T T T W W W W W Sample Output - 2: 16 give the code in python
Question
QUESTION 04 bookmark_border Roco is an island near Africa which is very prone to forest fire. Forest fire is such that it destroys the complete forest. Not a single tree is left. This island has been cursed by God , and the curse is that whenever a tree catches fire, it passes the fire to all its adjacent tree in all 8 directions, North, South, East, West, North-East, North-West, South-East, and South-West. And it is given that the fire is spreading every minute. Trees (indicated by T) and water (indicated by W) spots are arranged in a grid of MxN M-rows N-Columns.
Your task is that given the location of the first tree that catches fire, determine how long would it take for the entire forest to be on fire. You may assume that the lay out of the forest is such that the whole forest will catch fire for sure and that there will be at least one tree in the forest.
Input Format:
First line contains two integers, M, N, space separated, giving the size of the forest in terms of the number of rows and columns respectively
The next line contains two integers X,Y, space separated, giving the coordinates of the first tree that catches the fire
The next M lines, where ith line containing N characters each of which is either T or W, giving the position of the Tree and Water in the ith row of the forest.
Output Format:
Single integer indicating the number of minutes taken for the entire forest to catch fire
Constraints:
3 ≤ M ≤ 20
3 ≤ N ≤ 20
Sample Input - 1:
3 3
1 3
W T T
T W W
W T T
Sample Output - 1:
5
Explanation:
In the second minute, tree at (1,2) catches fire. In the third minute, the tree at (2,1) catches fire, fourth minute tree at (3,2) catches fire and in the fifth minute the last tree at (3,3) catches fire.
Sample Input - 2:
6 6
1 6
W T T T T T
T W W W W W
W T T T T T
W W W W W T
T T T T T T
T W W W W W
Sample Output - 2:
16
give the code in python
Solution
This problem can be solved using Breadth-First Search (BFS) algorithm. The idea is to start from the initial position of the fire and then spread the fire in all 8 directions. The time taken to burn the entire forest will be the maximum distance from the initial position to any tree.
Here is the Python code for the problem:
from collections import deque
def is_valid(x, y, m, n):
return 0 <= x < m and 0 <= y < n
def bfs(forest, m, n, x, y):
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
visited = [[False]*n for _ in range(m)]
queue = deque([(x, y, 0)])
visited[x][y] = True
max_time = 0
while queue:
x, y, time = queue.popleft()
max_time = max(max_time, time)
for i in range(8):
nx, ny = x + dx[i], y + dy[i]
if is_valid(nx, ny, m, n) and not visited[nx][ny] and forest[nx][ny] == 'T':
queue.append((nx, ny, time + 1))
visited[nx][ny] = True
return max_time
m, n = map(int, input().split())
x, y = map(int, input().split())
x -= 1
y -= 1
forest = [list(input()) for _ in range(m)]
print(bfs(forest, m, n, x, y))
This code first reads the input, then it uses BFS to spread the fire. The is_valid function checks if a position is within the forest. The bfs function starts from the initial position of the fire and spreads the fire in all 8 directions. It keeps track of the maximum time taken to reach any tree, which is the time taken to burn the entire forest.
Similar Questions
QUESTION 04 bookmark_border Roco is an island near Africa which is very prone to forest fire. Forest fire is such that it destroys the complete forest. Not a single tree is left. This island has been cursed by God , and the curse is that whenever a tree catches fire, it passes the fire to all its adjacent tree in all 8 directions, North, South, East, West, North-East, North-West, South-East, and South-West. And it is given that the fire is spreading every minute. Trees (indicated by T) and water (indicated by W) spots are arranged in a grid of MxN M-rows N-Columns. Your task is that given the location of the first tree that catches fire, determine how long would it take for the entire forest to be on fire. You may assume that the lay out of the forest is such that the whole forest will catch fire for sure and that there will be at least one tree in the forest. Input Format: First line contains two integers, M, N, space separated, giving the size of the forest in terms of the number of rows and columns respectively The next line contains two integers X,Y, space separated, giving the coordinates of the first tree that catches the fire The next M lines, where ith line containing N characters each of which is either T or W, giving the position of the Tree and Water in the ith row of the forest. Output Format: Single integer indicating the number of minutes taken for the entire forest to catch fire Constraints: 3 ≤ M ≤ 20 3 ≤ N ≤ 20 Sample Input - 1: 3 3 1 3 W T T T W W W T T Sample Output - 1: 5 Explanation: In the second minute, tree at (1,2) catches fire. In the third minute, the tree at (2,1) catches fire, fourth minute tree at (3,2) catches fire and in the fifth minute the last tree at (3,3) catches fire. Sample Input - 2: 6 6 1 6 W T T T T T T W W W W W W T T T T T W W W W W T T T T T T T T W W W W W Sample Output - 2: 16
Forest FireRoco is an island near Africa which is very prone to forest fire. Forest fire is such that it destroys the complete forest. Not a single tree is left.This island has been cursed by God , and the curse is that whenever a tree catches fire, it passes the fire to all its adjacent tree in all 8 directions,North, South, East, West, North-East, North-West, South-East, and South-West.And it is given that the fire is spreading every minute in the given manner, i.e every tree is passing fire to its adjacent tree.Suppose that the forest layout is as follows where T denotes tree and W denotes water.Your task is that given the location of the first tree that catches fire, determine how long would it take for the entire forest to be on fire. You may assume that the lay out of the forest is such that the whole forest will catch fire for sure and that there will be at least one tree in the forestConstraints:Input Format:First line contains two integers, M, N, space separated, giving the size of the forest in terms of the number of rows and columns respectively.The next line contains two integers X,Y, space separated, giving the coordinates of the first tree that catches the fire.The next M lines, where ith line containing N characters each of which is either T or W, giving the position of the Tree and Water in the ith row of the forest.Output Format:Single integer indicating the number of minutes taken for the entire forest to catch fireConstraints:3 ≤ M ≤ 203 ≤ N ≤ 20Example:Example 1Input 1:6 61 6W T T T T TT W W W W WW T T T T TW W W W W TT T T T T TT W W W W WOutput:16Example 2:Input:3 31 3W T TT W WW T TOutput:5Explanation:Explanation - Example 2:In the second minute, tree at (1,2) catches fire,in the third minute,the tree at (2,1) catches fire,the fourth minute tree at (3,2) catches fire and in the fifth minute the last tree at (3,3) catches fire.
In West Africa, the rainforests cover a wide strip ___Q1___ the coast from Sierra Leone to Gabon. In the last century these forests ___Q2___ mostly uninhabited. The Europeans arrived and soon began chopping ___Q3___ the trees for timber and to make way for massive plantations of cocoa, peanuts and cotton. Today, two-third of the West African forests ___Q4___ gone. QUESTION 03 bookmark_border Select the correct answer Q4 radio_button_unchecked has radio_button_unchecked is radio_button_unchecked have radio_button_checked were
Question 8SavedDetermine whether the following is true or false.Most of the fires were likely to have occurred on land that was previously damaged or cleared. However, these fires could still threaten untouched rainforest as they could spread to unintended areas.TrueFalseI'm not sure
In West Africa, the rainforests cover a wide strip ___Q1___ the coast from Sierra Leone to Gabon. In the last century these forests ___Q2___ mostly uninhabited. The Europeans arrived and soon began chopping ___Q3___ the trees for timber and to make way for massive plantations of cocoa, peanuts and cotton. Today, two-third of the West African forests ___Q4___ gone.QUESTION 14bookmark_borderSelect the correct answerQ1radio_button_uncheckedforradio_button_uncheckedonradio_button_checkedalongradio_button_uncheckedof
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.