Java program for Forest Fire problem

July 6, 2020

Forest Fire problem

Forest fire problem was asked in TCS CodeVita which about the forest which catches the fire and every tree passed fire to all the trees around it in all eight directions. The level of the problem is really good. In this Java program for Forest Fire problem we will find how long it will take for the whole forest to catch fire.

Problem Statement

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

Constrains:

  • 3 ≤ M ≤ 20
  • 3 ≤ N ≤ 20

 

Sample Input 1:

3 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 Fire problem in few other Coding Languages

C

We don’t have the solution for this problem, you can contribute the answer of this code in C programming language, we post that answer on our page

C++

We don’t have the solution for this problem, you can contribute the answer of this code in C++ programming language, we post that answer on our page

Python

We don’t have the solution for this problem, you can contribute the answer of this code in C programming language, we post that answer on our page

 

25 comments on “Java program for Forest Fire problem”


  • Ravi

    C++ Code Using recursion
    #include

    using namespace std;
    void counttime(vector<vector>&g,int row,int column,vector<vector>&g1,int k,int l,int one)
    {
    // boundary condition
    if((krow-1) || (lcolumn-1))
    return;
    if(g[k][l]==’W’)
    return;
    if(g1[k][l]!=0 && one>=g1[k][l])
    return ;

    g1[k][l]=one;

    counttime(g,row,column,g1,k+1,l,one+1);
    counttime(g,row,column,g1,k-1,l,one+1);
    counttime(g,row,column,g1,k,l+1,one+1);
    counttime(g,row,column,g1,k,l-1,one+1);
    counttime(g,row,column,g1,k+1,l+1,one+1);
    counttime(g,row,column,g1,k+1,l-1,one+1);
    counttime(g,row,column,g1,k-1,l-1,one+1);
    counttime(g,row,column,g1,k-1,l+1,one+1);

    }

    int main()
    {
    // cout<>m>>n;
    int k,l;cin>>k>>l;
    //char g[m][n];
    vector<vector>g(m,vector(n));
    for(int i=0;i<m;i++)
    {
    for(int j=0;j>temp;
    g[i][j]=temp;

    }
    }
    vector<vector>g1(m,vector(n,0));

    counttime(g,m,n,g1,k-1,l-1,1);
    int ans=-1;
    for(int i=0;i<m;i++)
    {
    for(int j=0;j<n;j++)
    {
    if(ans<g1[i][j])
    ans=g1[i][j];
    }
    }
    cout <<ans<<endl;

    return 0;
    }


  • Sourav

    import java.util.*;
    public class Main
    {
    static int dir[][]={{1,1},{-1,-1},{-1,1},{1,-1},{1,0},{0,1},{-1,0},{0,-1}};
    public static void main(String args[])
    {
    Scanner sc=new Scanner(System.in);
    int m=sc.nextInt();
    int n=sc.nextInt();
    int tx=sc.nextInt();
    int ty=sc.nextInt();
    char grid[][]=new char[m][n];
    int time[][]=new int[m][n];
    int curr_time=1;
    Queue q = new LinkedList();
    for(int i=0;i<m;i++)
    {
    for(int j=0;j<n;j++)
    {
    grid[i][j]=sc.next().charAt(0);
    }
    }
    q.add(new int[]{tx-1,ty-1});
    time[tx-1][ty-1]=curr_time;
    int max=curr_time;
    while(!q.isEmpty())
    {
    int coordinate[]=q.poll();
    int x=coordinate[0];
    int y = coordinate[1];
    for(int i=0;i<dir.length;i++)
    {
    int nx=x+dir[i][0];
    int ny=y+dir[i][1];
    if(check(grid,time,nx,ny))
    {
    time[nx][ny]=time[x][y]+1;
    max=Math.max(max,time[nx][ny]);
    q.add(new int[]{nx,ny});
    }
    }
    }
    System.out.println(max);
    }
    public static boolean check(char grid[][], int time[][], int x, int y)
    {
    return x=0 && y=0 && grid[x][y]==’T’ && time[x][y]==0;
    }
    }

1 2