The first task is to model a forest of a certain density. We will model a forest as an two-dimensional array. Each cell can either be occupied by a tree, or can be empty. For a value d (between 0.0 and 1.0), we will say that a forest has density d if each cell is a tree with probability d, or empty with probability (1 - d).

For example:

A forest with density 0.0 has no trees (every cell is empty with 100% probability).

A forest with density 0.5 has roughly half of its cells filled with trees (each cell contains a tree with 50% probability).

A forest with density 1.0 has every cell occupied by a tree (every cell contains a tree with 100% probability).

Modeling the Spread of Fire

We model a forest fire by setting trees in the top row of our forest on fire. Fire then spreads to neighboring trees (left, right, up, or down). We say that a forest fire spreads if the fire makes it to the bottom row of the forest. In the figure below, fire does not spread in the left forest, as it has no path to the bottom row. Fire does spread in the forest on the right, as it reaches the bottom row.

What to Implement

Create a class Forest representing the forest, as described above. The class should have the following:

Member variables: A two-dimensional array of integers, and two integers for the height and width of the grid

Constructor: takes integers for the width and height of the grid, and a double d representing the density of the forest. The constructor will create the two-dimensional array, and set the cells to 1 (contains a tree) with probability d, or 0 (empty) with probability (1 - d)

toString(): returns a string representation of the two-dimensional array

depthFirstSearch(): returns true if the fire in the forest spreads and false otherwise. This algorithm uses a depth first search (defined in Part IV, below) to determine whether fire spreads

breadthFirstSearch(): returns true if the fire in the forest spreads and false otherwise. This algorithm uses a breadth first search (defined in Part IV, below) to determine whether fire spreads

Part II: Probability of Fire Spreading

Probability of Fire Spreading for a Single Density

Part I defined forests of a given density, and showed us how to check whether a fire spreads or not. However, this is only for a single forest. We want to check the probability of forest fire spreading in many forests of the same density!

In order to find this probability, we will simulate forest fires in many forests of the same density and size, using the following pseudocode:

// given a density "d" fireSpreadCount = 0 repeat 10,000 times: create a forest f of size 20x20 with density d if "fire spreads in f" fireSpreadCount++ // the probability of fire spreading in forests of density "d" is: fireSpreadCount / 10,000

Note that we have two possible methods for determining whether fire spreads: depthFirstSearch() and breadthFirstSearch(). Implement a version of the above algorithm for each of those methods, so we can test their relative efficiencies.

Finding the Maximum Density

Our original problem can now be stated as the following task:

Find the maximum density d, such that the probability of fire spreading in a forest of density d is less than 0.5

We'll need to find the probability of fire spreading for many densities (using the previous algorithm). But how should we select densities to search? We'll do so using a binary search, as below:

lowDensity = 0.0 highDensity = 1.0 repeat 20 times: // check the midpoint density = (highDensity + lowDensity) / 2.0 // get probability of fire spreading in forests of 'density' p = probabilityOfFireSpreading( density ) // check probability of fire spreading if p  
Again, we have two methods for finding the probability of fire spreading if forests of a given density; one using depthFirstSearch(), one using breadthFirstSearch(). Provide two implementations of this algorithm: one for each of those methods.
 
What to Implement
 
Create a class FireProbability to compute the probability of fire spreading. This class should implement the following static methods:
 
Two methods to compute the probability of fire spreading in a forest of density d(given as a parameter):
 
probabilityOfFireSpreadDFS(): Uses depth first search to determine if fire spreads
 
probabilityOfFireSpreadBFS(): Uses breadth first search to determine if fire spreads
 
Two methods to compute the highest density that results in fire spreading with less than 0.5 probability:
 
highestDensityDFS(): Uses the DFS version of the previous method
 
highestDensityBFS(): Uses the BFS version of the previous method
 
Part III: Comparing Running Times
 
We now have two methods for calculating the highest probability of fire spreading. Create a Driver class with a main method that runs both of these methods. Note that both methods should return approximately the same value. 
 
Part IV: DFS and BFS Algorithms
 
Both of these search algorithms are very similar; they only differ in whether they use a Stack or a Queue. In general, each keeps track of cells that are on fire. We remove elements one at a time, and add their neighbors back into that structure.
 
Note that each of these methods requires marking trees as "on fire". I suggest using an additional integer value 2 to mark cells as "trees on fire".
 
Depth First Search (DFS)
 
For a depth first search, we store elements in a stack. This has the effect of expanding one neighbor fully before moving onto the next (see demo). The pseudocode is as follows:
 
// given a forest "f" // store positions on fire Stack 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
 
Breadth First Search (BFS)
 
For a breadth first search, we store elements in a queue. This has the effect of expanding the neighbors of a cell, then the neighbors of those neighbors, and so on (see demo). The pseudocode is very similar to a DFS: the only change is using a Queue instead of a Stack:
 
// given a forest "f" // store positions on fire Queue 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 dequeue the queue into currentPosition return true if currentPosition is on the bottom row for each neighboring tree add location into the queue mark tree as "on fire" // must not have reached the bottom row... return false
  Start of the fire Forest where fire does not spread Forest where fire spreads  Start of the fire Forest where fire does not spread Forest where fire spreads