Grid problems: flood fill

• Grid problems: flood fill
  • Counting areas
  • The pattern
  • Cost
  • C# note

§Grid problems: flood fill

Many interview questions give you a grid of cells: a map, an image, a maze. The key move is flood fill: from one cell, visit every connected cell of the same kind.

§Counting areas

Count the separate areas of 1s (cells connected up, down, left or right):

string[] map = { "11000", "11001", "00001" };
int rows = map.Length, cols = map[0].Length, areas = 0; var seen = new bool[rows, cols];
for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++)
    if (map[r][c] == '1' && !seen[r, c]) { areas++; Fill(r, c); }
Console.WriteLine(areas);
void Fill(int r, int c)
{
    if (r < 0 || c < 0 || r >= rows || c >= cols || seen[r, c] || map[r][c] == '0') return;
    seen[r, c] = true; Fill(r + 1, c); Fill(r - 1, c); Fill(r, c + 1); Fill(r, c - 1);
}

It prints 2: one area of four cells top-left, and one of two cells on the right.

§The pattern

1. Loop over every cell.
2. When you find an unvisited 1, count a new area and flood-fill it.
3. The fill marks cells as seen and spreads in four directions.
4. Check the bounds first (row and column inside the grid) before reading a cell; this is where most bugs are.

§Cost

Each cell is visited a constant number of times: O(rows × cols) time. The seen grid is O(rows × cols) memory. The recursion can go as deep as the area is big; for very large grids, use a queue (breadth-first) instead of recursion.

§C# note

int[,] is one rectangular block; int[][] (jagged) is an array of arrays, where rows can differ in length. Many online judges give you jagged arrays.

Read more: https://www.geeksforgeeks.org/dsa/matrix/

#tip · TIP-069