Codevita Previous Questions | Forest Fire

Forest Fire

LEVEL:Beginner

Description

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 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

Example 1:

Input

3 3
1 2
W T T
T W W
W T T

Output

Example 2:

Input

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

Output

Example 3:

Input

6 6
1 6
W T T T T T
T W W W T W
W T T T T T
W W T W W T
T T W T T T
T W T W W W

Output

Approach

The main approach is to use recursion to solve the problem
first we take the necessary inputs then we recurively count the time of each individual tree to burn
while doing this we skip where the tree is already burnt or where there are no trees or where there is water
then we store those values in the 2D array of same dimensions
then we traverse that array and find the maximum number which tells us when the last tree in the forest is burnt

Note :

Let us know if you can come up with a better approach, mail us at support@theinquisitive.in Your approach will be reviewed and posted with credits to you.

Beginner

Forest Fire

LEVEL:Beginner

Description

Input Format

Output Format

Approach

Recommended Questions

Topic: Codevita Previous Questions

Beginner