Demo: Number of Forests

In this assignment, we'll work on a more challenging graph problem: "Number of Forests."

Problem Description

// You are provided with a 2D grid map where each cell is either
//  marked as a tree ('T') or open land ('O'). Your goal is to
// count the number of distinct forest regions on the map. A forest
// region consists of a contiguous group of tree cells ('T'). For
// this problem, two tree cells are considered connected if they
// share an edge horizontally or vertically, but not diagonally.

// Write a function numOfForests that accepts a nested array grid
// representing the 2D map. The function should return the total
// number of forest regions in the grid.

function numOfForests(grid) {
  // implementation goes here
}

const grid1 = [];
console.log(numOfForests(grid1) === 0);

const grid2 = [
  ['O', 'O', 'O'],
  ['O', 'O', 'O'],
  ['O', 'O', 'O']
];
console.log(numOfForests(grid2) === 0);
const grid3 = [
  ['T', 'T', 'O'],
  ['T', 'T', 'O'],
  ['O', 'O', 'O']
];
console.log(numOfForests(grid3) === 1);
const grid4 = [
  ['O', 'O', 'T', 'T', 'O'],
  ['T', 'T', 'O', 'T', 'O'],
  ['T', 'T', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'T', 'T'],
  ['O', 'O', 'O', 'O', 'O'],
];
console.log(numOfForests(grid4) === 3);

const grid5 = [
  ['T', 'T', 'T'],
  ['T', 'O', 'T'],
  ['T', 'T', 'T']
];
console.log(numOfForests(grid5) === 1);

const grid6 = [
  ['T', 'O', 'T', 'O', 'T'],
  ['O', 'O', 'O', 'O', 'O'],
  ['T', 'O', 'T', 'O', 'T'],
  ['O', 'O', 'O', 'O', 'O'],
  ['T', 'O', 'T', 'O', 'T']
];
console.log(numOfForests(grid6) === 9);

const grid7 = [
  ['T', 'T', 'T'],
  ['T', 'T', 'T'],
  ['T', 'T', 'T']
];
console.log(numOfForests(grid7) === 1);

// All test cases should log true

Problem Breakdown

In this problem, we are given a grid representing a map of "T"s (tree) and "O"s (open land).

Each square is one position represented by a coordinate pair representing a row and column index. For example, (1, 2).

Given any position (row, col) in the grid, we have four neighbors at most.

We'll take on the role of an explorer, traversing the grid from left to right within a single row before moving on to the next row. For this traversal, we will use a simple nested loop.

Whenever we land on a tree spot, we'll start exploring the boundaries of that forest using a depth-first search on all four sides. We'll mark each tree position as visited while exploring to avoid a stack overflow issue. Note that we could also use a breadth-first search in this case, and it wouldn't change the outcome.

Once we finish exploring one forest, we'll increment the forest count and continue the traversal. If we encounter a tree that has already been visited, we won't explore it again; instead, we'll continue with the iteration. We don't want to explore the same forest more than once. In the image below, we are not exploring this tree spot (0, 3), as it was already visited when we did our search starting at plot (0, 2).

Exploration Phase

Let's see how the exploration DFS phase would look with a simple example.

When we encounter a tree, we start a depth-first search which includes:
1. Checking if the cell is in bounds, part of a forest, and hasn't already been visited.
2. Adding that cell to the visited set, let's say in the form of a string "0,0"
3. Starting a depth-first search on all four sides. The order of the sides we explore is irrelevant. We can follow a clockwise pattern left->up->right->down, or a counterclockwise pattern left->down->right->up, or even start from the bottom, down->left->right->up. In this example, we'll follow the clockwise pattern starting from the left.

If you have trouble following the steps we take below, try writing out the neighbors we need to visit, as we did in the walkthrough in Graph Traversal Part II. Here, we could use a pattern like LURD to keep track of our progress, since we want to check first to the left, then up, then right, then down.

Since we are starting with the left neighbor, we are calling the dfs function passing in row, col - 1, which in this case is dfs(0, -1). Whenever we go out of the bounds of the grid, hit a cell that is open land, or encounter a cell that has already been visited, we stop exploration on that side; in other words, we return from the function. With this first neighbor, we went out of bounds.

The next cell would be the cell to the top at row - 1, col which means that we would call dfs(-1, 0). Since this is out of bounds, we would return from the function.

Next, we explore the right neighbor by calling dfs(0, 1). It's a tree cell we haven't visited before, so we first add it to the visited set. Then, we begin the depth-first search from that cell on all four sides, starting from the left.

From the cell (0, 1), we would first try to go left by calling dfs(0, 0), but that cell is already in the visited set, so we would immediately return. Next, we would go to the top, but that cell is out of bounds, and so is the cell to the right. Finally, we try to go down and encounter another tree cell. This is the cell (1, 1), and we repeat the process for it: first, add it to the visited set, then start exploring all four sides.

From the cell (1, 1), the cell to the left is open land, the cell to the top has already been visited, and the cells to the right and bottom are out of bounds. This means that we have explored all sides for dfs(1, 1), and we can pop that function from the stack. We have also explored all four sides for the cell (0, 1), so we return from that function. Finally, we haven't yet gone down from the cell (0, 0) to (1, 0), but that cell is out of bounds, so we immediately return, which concludes our exploration phase.

Walkthrough

Let's do a walkthrough of the graph example from the beginning of this assignment:

Step 1: We'll iterate through the grid until we hit a tree.

Step 2: Once we hit the tree cell, we'll perform a depth-first search and mark each plot of land as visited. Finally, we'll increment the number of forests by 1.

Step 3: In the next iteration we hit another tree cell, (0, 3), but it's already been visited so we continue until we find a tree cell that we haven't seen.

Step 4: We finally hit a new tree cell in the second row. We complete the exploration phase for this forest with a depth-first search, mark all tree squares as visited, and increment the count of forests.

Step 5: Next, we continue iteration until we hit another tree cell that has yet to be visited.

Step 6: In the third row, we find another tree cell that wasn't visited so we perform a depth-first search to explore that forest. We mark all tree cells as visited and increment the count of forests by 1.

Step 7: Finally, we continue with the iteration, but since there are no more unvisited tree cells we reach the end of the grid, and we know that the number of forests is 3.

Solution Code

Let's see the code implementation:

function numOfForests(grid) {
  if (!grid || grid.length === 0) return 0;

  const numRows = grid.length;
  const numCols = grid[0].length;
  const visited = new Set();

  function dfs(row, col) {
    if (
      row < 0 || row >= numRows || col < 0 || col >= numCols ||
      grid[row][col] === 'O' || visited.has(`${row},${col}`)
    ) {
      return;
    }

    visited.add(`${row},${col}`);

    dfs(row, col - 1);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row + 1, col);


  }

  let forestCount = 0;

  for (let row = 0; row < numRows; row++) {
    for (let col = 0; col < numCols; col++) {
      if (grid[row][col] === 'T' && !visited.has(`${row},${col}`)) {
        dfs(row, col);
        forestCount++;
      }
    }
  }

  return forestCount;
}

Further Exploration

In this problem, as in many other graph problems, we need a way to track visited squares. We used a set to solve this problem. However, do we need a set in this case? Is there another way to mark a square as visited?

Try to solve the problem without using an additional collection like a set. You can always reference the solution provided below.

Think about the type of square we never explore and how we can leverage that.

In this problem, aside from not exploring out of bounds squares and already visited squares, we are also never exploring an open land square.

While exploring the boundaries of the forest, we can "cut" the forest by converting that square to open land. This way, we ensure that we won't revisit it. If we do this, then every time we encounter a tree square, we can go ahead and increment the forest count. We know that every new tree square is part of a new forest. We don't recommend this approach for counting real forests.

function numOfForests(grid) {
  if (!grid || grid.length === 0) return 0;

  const numRows = grid.length;
  const numCols = grid[0].length;

  function dfs(row, col) {
    if (
      row < 0 || row >= numRows || col < 0 || col >= numCols ||
      grid[row][col] === 'O'
    ) {
      return;
    }

    grid[row][col] = 'O';

    dfs(row, col - 1);
    dfs(row - 1, col);
    dfs(row, col + 1);
    dfs(row + 1, col);
  }

  let forestCount = 0;

  for (let row = 0; row < numRows; row++) {
    for (let col = 0; col < numCols; col++) {
      if (grid[row][col] === 'T') {
        dfs(row, col);
        forestCount++;
      }
    }
  }

  return forestCount;
}