Grid connected components

When to use it

Use it when a grid holds separate regions of joined cells and you must count them, measure them or mark them, and how far apart two cells are does not matter.

It belongs to the graphs group: Visit every place you can reach, once each, in the order that suits the question.

Watch it work

A floor plan is a grid: -1 is a wall and 0 is floor. A room is a group of floor cells joined side by side. Number the rooms from 1, in the order a row-by-row scan meets them, and write each room's number into its cells.

Input
plan = [[0, 0, -1, 0], [-1, 0, -1, 0], [0, -1, -1, -1]]

Output
[[1, 1, -1, 2], [-1, 1, -1, 2], [3, -1, -1, -1]]

The method

1. Start with no rooms numbered
2. Scan every cell, skipping walls and cells that have a number
3. New room found: number this cell and put it on a stack
4. While cells wait on the stack, take one off
5. Its floor neighbors with no number join the room
6. Return the plan with a room number in every floor cell

The run, one moment at a time

1. Step 1. The plan as given: -1 is a wall, and 0 is floor with no room number yet. A cell is named (row, column). No room is numbered.

   row 0: 0 0 -1 0
   row 1: -1 0 -1 0
   row 2: 0 -1 -1 -1
   stack: empty
   rooms: 0
   

2. Step 3. The scan starts at (0, 0). It is floor with no number, so room 1 begins here. Write 1 into the cell and put the cell on the stack.

   row 0: 1 0 -1 0
   row 1: -1 0 -1 0
   row 2: 0 -1 -1 -1
   stack: 0,0
   rooms: 1
   

3. Step 5. Take (0, 0) off the stack. Beside it, (0, 1) is floor with no number: it gets 1 and joins the stack. Its other sides are the edge of the plan and a wall.

   row 0: 1 1 -1 0
   row 1: -1 0 -1 0
   row 2: 0 -1 -1 -1
   stack: 0,1
   rooms: 1
   

4. Step 5. Take (0, 1) off the stack. Beside it, (1, 1) is floor with no number: it gets 1 and joins the stack. Its other sides are the edge of the plan, a numbered cell and a wall.

   row 0: 1 1 -1 0
   row 1: -1 1 -1 0
   row 2: 0 -1 -1 -1
   stack: 1,1
   rooms: 1
   

5. Step 4. Take (1, 1) off the stack. Beside it there is no floor without a number. (2, 0) touches it only at a corner, and corners do not join. The stack is empty: room 1 is complete, with 3 cells.

   row 0: 1 1 -1 0
   row 1: -1 1 -1 0
   row 2: 0 -1 -1 -1
   stack: empty
   rooms: 1
   

6. Step 2. The scan goes on. (0, 1) already has a number and (0, 2) is a wall, so the scan skips both.

   row 0: 1 1 -1 0
   row 1: -1 1 -1 0
   row 2: 0 -1 -1 -1
   stack: empty
   rooms: 1
   

7. Step 3. The scan reaches (0, 3). It is floor with no number, so room 2 begins here. Write 2 into the cell and put the cell on the stack.

   row 0: 1 1 -1 2
   row 1: -1 1 -1 0
   row 2: 0 -1 -1 -1
   stack: 0,3
   rooms: 2
   

8. Step 5. Take (0, 3) off the stack. Beside it, (1, 3) is floor with no number: it gets 2 and joins the stack. Its other sides are the edge of the plan and a wall.

   row 0: 1 1 -1 2
   row 1: -1 1 -1 2
   row 2: 0 -1 -1 -1
   stack: 1,3
   rooms: 2
   

9. Step 4. Take (1, 3) off the stack. Its sides are a numbered cell, a wall and the edge of the plan, so nothing joins. The stack is empty: room 2 is complete, with 2 cells.

   row 0: 1 1 -1 2
   row 1: -1 1 -1 2
   row 2: 0 -1 -1 -1
   stack: empty
   rooms: 2
   

10. Step 3. The scan skips 4 cells, walls and numbered floor, and reaches (2, 0). It is floor with no number, so room 3 begins here. Write 3 into the cell and put the cell on the stack.

    row 0: 1 1 -1 2
    row 1: -1 1 -1 2
    row 2: 3 -1 -1 -1
    stack: 2,0
    rooms: 3
    

11. Step 4. Take (2, 0) off the stack. Its sides are a wall and the edge of the plan, so nothing joins. The stack is empty: room 3 is complete, with 1 cell.

    row 0: 1 1 -1 2
    row 1: -1 1 -1 2
    row 2: 3 -1 -1 -1
    stack: empty
    rooms: 3
    

12. Step 6. The scan passes the last 3 cells and ends. Every floor cell now holds the number of its room, and the plan has 3 rooms.

    row 0: 1 1 -1 2
    row 1: -1 1 -1 2
    row 2: 3 -1 -1 -1
    stack: empty
    rooms: 3
    

The code

The numbered comments are the steps of the method.

function solve(plan) {
  // 1. Start with no rooms numbered
  let room = 0;
  // 2. Scan every cell, skipping walls and cells that have a number
  for (let r = 0; r < plan.length; r++)
    for (let c = 0; c < plan[r].length; c++) {
      if (plan[r][c] !== 0) continue;
      // 3. New room found: number this cell and put it on a stack
      room++;
      plan[r][c] = room;
      const stack = [[r, c]];
      // 4. While cells wait on the stack, take one off
      while (stack.length) {
        const [x, y] = stack.pop();
        // 5. Its floor neighbors with no number join the room
        for (const [a, b] of [
          [x - 1, y],
          [x + 1, y],
          [x, y - 1],
          [x, y + 1],
        ])
          // Outside the plan, plan[a]?.[b] is undefined, not 0.
          if (plan[a]?.[b] === 0) {
            plan[a][b] = room;
            stack.push([a, b]);
          }
      }
    }
  // 6. Return the plan with a room number in every floor cell
  return plan;
}

def solve(plan):
    # 1. Start with no rooms numbered
    room = 0
    # 2. Scan every cell, skipping walls and cells that have a number
    rows, cols = len(plan), len(plan[0])
    for r in range(rows):
        for c in range(cols):
            if plan[r][c] != 0:
                continue
            # 3. New room found: number this cell and put it on a stack
            room += 1
            plan[r][c] = room
            stack = [(r, c)]
            # 4. While cells wait on the stack, take one off
            while stack:
                x, y = stack.pop()
                # 5. Its floor neighbors with no number join the room
                for a, b in (
                    (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)
                ):
                    # Row -1 would read the last row: test the edges.
                    inside = 0 <= a < rows and 0 <= b < cols
                    if inside and plan[a][b] == 0:
                        plan[a][b] = room
                        stack.append((a, b))
    # 6. Return the plan with a room number in every floor cell
    return plan

How to spot it

Given: A grid whose cells are of two kinds, such as land and water

Cells of one kind that touch form regions. A problem that draws its grid this way usually asks something about those regions.

Given: Cells are joined side by side, and not at a corner

This sentence defines a region. It also names the neighbors to look at from each cell: up, down, left and right.

Asked: How many separate regions are there, or how large is the largest?

Each region is walked once, from the first of its cells that the scan meets. Count the walks, or count the cells in each walk.

Asked: Which regions touch the edge of the grid?

Start the walks from the cells on the edge. Everything they reach touches the edge, and every region left unmarked does not.

Looks like it, but is not

• You need the fewest steps from one cell to another, around the blocked cells. Use Breadth-first search by distance. A region walk takes cells in any order, so it knows what is joined but not how far. Distance needs the nearest cells first.
• The things that are joined are not cells: each has its own list of links to others. Use Graph traversal with a visited set. The walk is the same, but the neighbors come from a list, and a separate set must remember what was visited.
• You read every cell in a fixed order, such as a spiral, and nothing spreads. Use Matrix traversal. There the order of reading is the whole task. No cell asks its neighbors anything, and no regions are formed.

Cost and mistakes

Time grows with the number of cells, rows times columns, written O(rows * cols): the scan reads each cell once, and each cell joins the stack at most once and looks at four neighbors. Extra space is the stack, which can hold most cells.

Watch out

• Mark a cell when you add it to the stack, not when you take it off. Otherwise two neighbors can both add the same cell, and it is counted twice.
• Test that a neighbor is inside the grid before you read it. In Python, row -1 does not fail: it reads the last row of the grid.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.