Question

Java-

Create a new class named Forest that has a 2D array of integers to store a forest.

Create a private inner class Position to store the row and column of the current cell.

Create a Depth First Search Method that uses a stack to remove the current tree and search its neighbors based on the following pseudocode:

// given a forest "f"
// store positions on fire
Stack<Position> cellsToExplore

// the forest is aflame!
for each tree in the top row:
  add position to cellsToExplore
  mark tree as "on fire"

// continue lighting neighbors on fire
while cellsToExplore is not empty
  pop the stack into currentPosition
  return true if currentPosition is on the bottom row
  for each neighboring tree
    push location onto the stack
    mark tree as "on fire"

// must not have reached the bottom row...
return false

Answer 1

The solution to the above problem in java is as follows:-

Code-

import java.io.*;
import java.util.*;

public class Forest {
   int [][] array; //To store 2d array
   public Forest(int r,int c){ //Constructor to initialize 2d array
       array=new int[r][c];
       for(int i=0;i<array.length;i++)
           for(int j=0;j<array[i].length;j++)
               array[i][j]=0; //Tree not on fire
   }
   public boolean dfs(){ // Dfs implemented according to question
       // store positions on fire
       Stack<Position> cellsToExplore=new Stack<Position>();
       // the forest is aflame!
       for(int i=0;i<array[0].length;i++){ //for each tree in the top row:
           Position x=new Position(0,i);
           cellsToExplore.push(x); // add position to cellsToExplore
           array[0][i]=1; // mark Tree as "on fire"
       }

       // continue lighting neighbors on fire
       while(!cellsToExplore.empty()){
           Position top=cellsToExplore.pop(); //pop the stack into currentPosition
           if(top.row==array.length-1) // Checking if we are in the bottom row
               return true; // return true if currentPosition is on the bottom row
           int x=top.row, y=top.col;
           if(x+1<array.length){
               array[x+1][y]=1; // mark Tree as "on fire"
               Position neighbour=new Position(x+1,y);
               cellsToExplore.push(neighbour); //push location onto the stack
           }
       }
       // must not have reached the bottom row...
       return false;
   }
   //Inner Postion Class
   private class Position{
       int row;
       int col;
       public Position(int r,int c){
           row=r;
           col=c;
       }
   }
   public static void main(String[] args) throws IOException {
       int r,c; // Taking row and column of dfs as input
       System.out.println("Enter row and columns for the 2D array of Forest:");
       Scanner sc= new Scanner(System.in);
       r=sc.nextInt();
       c=sc.nextInt();
       Forest x=new Forest(r,c); //initialize forest
       System.out.println("Are all trees burnt? "+x.dfs()); //run dfs
   }
}

Code Screenshots-

Outputs-

Feel free to comment for any issues, do rate the answer positively