Programming
Aptitude
Syllabus
Interview Preparation
Interview Exp.
Off Campus
0
Notifications Mark All Read
- Login
- Get Prime
0
Java program for Forest Fire problem
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
Login/Signup to comment
import java.util.*;
public class ForestFire{
public static void main(String []args){
Scanner sc= new Scanner(System.in);
int m= sc.nextInt();
int n= sc.nextInt();
int X= sc.nextInt();
int Y= sc.nextInt();
String str[][]= new String[m][n];
for(int i=0;i<m;i++) {
for(int j=0;j<n;j++) {
str[i][j]= sc.next();
}
}
int min= 1, total=1;
boolean checked[][]= new boolean[m][n];
Queue q1= new LinkedList();
Queue q2= new LinkedList();
q1.add(X-1);
q2.add(Y-1);
checked[X-1][Y-1]= true;
while(!q1.isEmpty() && !q2.isEmpty()) {
int x1= q1.remove();
int y1= q2.remove();
int x[]= new int[8];
int y[]= new int[8];
y[3]= y[0]= y[5]= y1-1;
x[0]= x[1]= x[2]= x1-1;
x[5]= x[6]= x[7]= x1+1;
y[2]= y[4]= y[7]= y1+1;
x[3]= x[4]= x1;
y[1]= y[6]= y1;
int flag= 0;
for(int i=0;i=0 && x[i]=0 && y[i]<n && !checked[x[i]][y[i]]) {
if(str[x[i]][y[i]].equals("T")) {
q1.add(x[i]);
q2.add(y[i]);
checked[x[i]][y[i]]= true;
} else {
checked[x[i]][y[i]]= true;
}
total++;
flag= 1;
}
}
if(flag==1) min++;
if(total==m*n) break;
}
System.out.println(min);
}
}
#include
using namespace std;
vector<vector> t;
void calculate(vector<vector> a,int m,int n,int x,int y,int c)
{
if(x<0 || y=m || y>=n || a[x][y] == ‘W’)
{
return;
}
if(t[x][y]!=0 && t[x][y]>m>>n>>x>>y;
vector<vector> a;
for(int i=0;i<m;i++)
{
vectorb;
vector d;
char ch;
for(int j=0;j>ch;
b.push_back(ch) ;
d.push_back(0);
}
a.push_back(b);
t.push_back(d);
}
calculate(a,m,n,x-1,y-1,1);
int ma = INT_MIN;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(ma < t[i][j])
ma = t[i][j];
}
}
cout << ma;
return 0;
}
#Here is my Solution in Python using the BFS
r,c = [int(x) for x in input().split(‘ ‘)]
start =[int(x)-1 for x in input().split(‘ ‘)]
forest = [[x for x in input().split(‘ ‘)] for _ in range(r)]
time = [[None for _ in range(c)] for _ in range(r)]
time[start[0]][start[1]] = 1
no_of_trees = 0
for i in range(r):
for j in range(c):
if forest[i][j] == ‘T’:
no_of_trees+=1
queue=[]
queue.append(start)
trees_visited=0
p=[]
while queue:
current = queue.pop(0)
#print(current)
x = current[0]
y = current[1]
curr_time = time[x][y]
position=[]
if x-1>=0 and x-1=0 and y-1=0 and x=0 and y-1=0 and x+1=0 and y-1=0 and x-1=0 and y=0 and x+1=0 and y=0 and x-1=0 and y+1=0 and x=0 and y+1=0 and x+1=0 and y+1<c:
if forest[x+1][y+1]!='W' and time[x+1][y+1]==None:
position.append([x+1,y+1])
#print(position)
for coord in position:
j=coord[0]
k=coord[1]
time[j][k] = curr_time + 1
queue.append(coord)
trees_visited+=1
if trees_visited==no_of_trees:
break
#for i in p:
# print(i)
#for i in time:
# print(i)
print(max(time))
C++ Code using queue
#include
using namespace std;
int Solve(int r,int c,int start,int end,vector<vector> forest){
queue<pair> next;
next.push({start,end});
vector<pair> pairs={{-1,0},{-1,+1},{0,+1},{+1,+1},{+1,0},{+1,-1},{0,-1},{-1,-1}};
vector<vector> visited(forest.size(),vector(forest[0].size(),false));
visited[start][end]=true;
while (!next.empty()){
pair p=next.front();
next.pop();
int s=p.first;
int e=p.second;
int currentTrre=forest[s][e];
for (int i=0;i<pairs.size();i++){
if (pairs[i].first+s <r && pairs[i].second+e=0 && pairs[i].second+e>=0){
if (forest[pairs[i].first+s][pairs[i].second+e]!=0 && !visited[pairs[i].first+s][pairs[i].second+e]){
visited[pairs[i].first+s][pairs[i].second+e]=true;
forest[pairs[i].first+s][pairs[i].second+e]=currentTrre+1;
next.push({pairs[i].first+s,pairs[i].second+e});
}
}
}
}
int ma=0;
for(int i=0;i<forest.size();i++){
for (int j=0;j<forest[i].size();j++){
ma=max(ma,forest[i][j]);
}
}
return ma;
}
int main()
{
vector<vector> forest;
int rows,cols,startx,starty;
cin>>rows>>cols>>startx>>starty;
char p;
for (int i=0;i<rows;i++){
vector buff;
for (int j=0;j>p;
if (p==’T’){
buff.push_back(1);
}
else{
buff.push_back(0);
}
}
forest.push_back(buff);
}
cout<<Solve(rows,cols,startx-1,starty-1,forest);
return 0;
}
oh no, PREPINSTA please look in to this…..i am unable to post my code correctly….it keeps changes after posting. i tried 3 time.🤨🤨😑
Hey Sonendra relax about it, just write what are the mistakes that occur in your code after posting it, we’ll fix it from our end
i dont know but code at the time of posting was good but i tried it two times but after posting, at line 24 for loop is just printed wrongly.
so code after line 23(for loop for J) is
for(int j=0;j= 0 && x=0 && y =0 && y-1>=0){if(isvisited(x-1,y-1)){p.add(x-1);q.add(y-1);dq.add(d+1);}}
if(x+1<M && y+1=0 && y+1<N){if(isvisited(x-1,y+1)){p.add(x-1);q.add(y+1);dq.add(d+1);}}
if(x+1=0){if(isvisited(x+1,y-1)){p.add(x+1);q.add(y-1);dq.add(d+1);}}
if(y-1>=0){if(isvisited(x,y-1)){p.add(x);q.add(y-1);dq.add(d+1);}}
if(y+1=0){if(isvisited(x-1,y)){p.add(x-1);q.add(y);dq.add(d+1);}}
if(x+1 0)
return false;
else
return true;
}
public static int findMax(int mat[][],int M,int N)
{
int maxElement = Integer.MIN_VALUE;
for (int i = 0; i < M; i++) {
for (int j = 0; j maxElement) {
maxElement = mat[i][j];
}
}
}
return maxElement;
}
}
sorry and thankyou.
Don’t worry Sonendra we’ll fix it up from our end, by the way thanks a lot for contributing your code
import java.util.*;
import java.io.*;
public class forestfire {
static char[][] f;
static int [][] vis;
static int [][] dis;
static int M;
static int N;
public static Queue p
= new LinkedList();
public static Queue dq
= new LinkedList();
public static Queue q
= new LinkedList();
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
M=sc.nextInt();
N=sc.nextInt();
int x=sc.nextInt();
int y=sc.nextInt();
f = new char[M][N];
vis = new int[M][N];
dis = new int[M][N];
for(int i=0;i<M;i++){
for(int j=0;j= 0 && x=0 && y =0 && y-1>=0){if(isvisited(x-1,y-1)){p.add(x-1);q.add(y-1);dq.add(d+1);}}
if(x+1<M && y+1=0 && y+1<N){if(isvisited(x-1,y+1)){p.add(x-1);q.add(y+1);dq.add(d+1);}}
if(x+1=0){if(isvisited(x+1,y-1)){p.add(x+1);q.add(y-1);dq.add(d+1);}}
if(y-1>=0){if(isvisited(x,y-1)){p.add(x);q.add(y-1);dq.add(d+1);}}
if(y+1=0){if(isvisited(x-1,y)){p.add(x-1);q.add(y);dq.add(d+1);}}
if(x+1 0)
return false;
else
return true;
}
public static int findMax(int mat[][],int M,int N)
{
int maxElement = Integer.MIN_VALUE;
for (int i = 0; i < M; i++) {
for (int j = 0; j maxElement) {
maxElement = mat[i][j];
}
}
}
return maxElement;
}
}
JAVA CODE FOR FOREST FIRE PROBLEM
PLEASE INPUT ONE BY ONE NOT AS A LINE.
BFS USING RECURSION is used to solve the problem. Thankyou
import java.util.*;
import java.io.*;
public class forestfire {
static char[][] f;
static int [][] vis;
static int [][] dis;
static int M;
static int N;
public static Queue p
= new LinkedList();
public static Queue dq
= new LinkedList();
public static Queue q
= new LinkedList();
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
M=sc.nextInt();
N=sc.nextInt();
int x=sc.nextInt();
int y=sc.nextInt();
f = new char[M][N];
vis = new int[M][N];
dis = new int[M][N];
for(int i=0;i<M;i++){
for(int j=0;j= 0 && x=0 && y =0 && y-1>=0){if(isvisited(x-1,y-1)){p.add(x-1);q.add(y-1);dq.add(d+1);}}
if(x+1<M && y+1=0 && y+1<N){if(isvisited(x-1,y+1)){p.add(x-1);q.add(y+1);dq.add(d+1);}}
if(x+1=0){if(isvisited(x+1,y-1)){p.add(x+1);q.add(y-1);dq.add(d+1);}}
if(y-1>=0){if(isvisited(x,y-1)){p.add(x);q.add(y-1);dq.add(d+1);}}
if(y+1=0){if(isvisited(x-1,y)){p.add(x-1);q.add(y);dq.add(d+1);}}
if(x+1 0)
return false;
else
return true;
}
public static int findMax(int mat[][],int M,int N)
{
int maxElement = Integer.MIN_VALUE;
for (int i = 0; i < M; i++) {
for (int j = 0; j maxElement) {
maxElement = mat[i][j];
}
}
}
return maxElement;
}
}
Thanks Sonendra for contributing the code, and yeah we will surely keep it in mind to enter the input one by one
c++ SOLUTION ,graph problem,variation of rotten oranges problem
https://ide.geeksforgeeks.org/A2tQjOkara
Thanks for the link Gaurav, but we will be pleased if you can just simply comment the entire code here.
#by gokul r
from queue import Queue
m,n=list(map(int,input().split()))
x,y=list(map(int,input().split()))
forest =[list(map(str,input().split())) for _ in range(m)]
visited = [[0 for i in range(n)] for j in range(m)]
q = Queue(maxsize= m*n)
q.put([x-1,y-1])
visited[x-1][y-1]=1
time = 1
q1=Queue(maxsize= m*n)
temp=1
while temp:
found = 0
temp=0
k=q
while(not q.empty()):
ele = q.get()
check = [[ele[0],ele[1]-1],[ele[0],ele[1]+1],[ele[0]-1,ele[1]],[ele[0]+1,ele[1]],[ele[0]-1,ele[1]-1],[ele[0]+1,ele[1]+1],[ele[0]-1,ele[1]+1],[ele[0]+1,ele[1]-1]]
for i in check:
if (i[0]>=0 and i[0]=0 and i[1]<n):
if visited[i[0]][i[1]] == 0 and forest[i[0]][i[1]]=='T':
found = 1
q1.put(i)
visited[i[0]][i[1]] = 1
if not q1.empty():
temp=1
while not q1.empty():
q.put(q1.get())
if found:
time += 1
print(time)
Thanks for contributing the code Gokul
#
#
#By Akhil Maddukuri
from queue import Queue
m,n = list(map(int,input().split()))
indx,indy = list(map(int,input().split()))
forest = []
for i in range(m):
forest.append(input().split())
#print(forest)
visited = [[0 for i in range(m)] for j in range(n)]
q = Queue(maxsize= m*n)
q.put([indx-1,indy-1])
visited[indx-1][indy-1]=1
time = 1
while(not q.empty()):
ele = q.get()
#print(ele)
check = [[ele[0],ele[1]-1],[ele[0],ele[1]+1],[ele[0]-1,ele[1]],[ele[0]+1,ele[1]],[ele[0]-1,ele[1]-1],[ele[0]+1,ele[1]+1],[ele[0]-1,ele[1]+1],[ele[0]+1,ele[1]-1]]
# print(check)
found = 0
for i in check:
if (i[0]>=0 and i[0]=0 and i[1]<n):
if visited[i[0]][i[1]] == 0 and forest[i[0]][i[1]]=='T':
found = 1
q.put(i)
visited[i[0]][i[1]] = 1
if found:
time += 1
print(time)
Correction : modify visited array in line 10 as below
visited = [[0 for i in range(n)] for j in range(m)]
Thanks for contributing this code
if (i[0]>=0 and i[0]=0 and i[1]<n): there is one mistake in this statement
W T T T T T
T W W W T 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
for this input it should be 10 but for ur program it will be 15 so please make change in ur program
We surely will Gokul
#PYTHON
m, n = list(map(int,input().split()))
x, y = list(map(int,input().split()))
forest, fire, time = list(), list(), 1
for i in range(m):
z = input().strip().split()
forest.append(z)
fire.extend(z) # fire += z
forest[x-1][y-1] = fire[(x-1)*n + y-1] = 1
while ‘T’ in fire:
time += 1
while time-1 in fire:
z = fire.index(time-1)
x, y = z//n, z%n
forest[x][y] = fire[z] = -1
if y>0 and forest[x][y-1]==’T’:
forest[x][y-1] = fire[z-1] = time
if y0 and forest[x-1][y]==’T’:
forest[x-1][y] = fire[z-n] = time
if x0 and y>0 and forest[x-1][y-1]==’T’:
forest[x-1][y-1] = fire[z-n-1] = time
if x>0 and y<n-1 and forest[x-1][y+1]=='T':
forest[x-1][y+1] = fire[z-n+1] = time
if x0 and forest[x+1][y-1]==’T’:
forest[x+1][y-1] = fire[z+n-1] = time
if x<m-1 and y<n-1 and forest[x+1][y+1]=='T':
forest[x+1][y+1] = fire[z+n+1] = time
print(time)
Thanks Akhil for contributing this answer