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.
Question
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.
Solution
This problem can be solved using the Breadth-First Search (BFS) algorithm. Here are the steps:
-
Parse the input: Read the dimensions of the forest (M, N), the coordinates of the first tree that catches fire (X, Y), and the layout of the forest.
-
Initialize a queue: Add the first tree that catches fire to the queue. This tree will be the starting point of the BFS.
-
Initialize a 2D array to keep track of the time it takes for each tree to catch fire. Set the time for the first tree to 0.
-
Start the BFS: While the queue is not empty, remove a tree from the queue. For each of its 8 adjacent trees, if the tree is not on fire and is not water, set its fire time to the current tree's fire time plus 1, and add it to the queue.
-
After the BFS is done, the maximum value in the fire time array will be the time it takes for the entire forest to catch fire.
This algorithm works because BFS visits all the trees in the forest in the order they catch fire. The fire time array keeps track of the time it takes for each tree to catch fire, and the maximum value in this array is the time it takes for the last tree to catch fire, which is the time it takes for the entire forest to catch fire.
Similar Questions
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 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.Public Test Cases:# INPUT EXPECTED OUTPUT1 3 31 3W T TT W WW T T52 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 W16
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
discuss the causes extent and environmental impact of similpal forest fire 2021
Crown fire mostly takes place in which of the following forests ?(1) Dense Forest(2) Thorn Forest(3) Savanna Forest(4) Alpine Fores
If a fire destroys 75% of the trees in a forest, this is an example of what type of limiting factor?
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.