templates · Graph traversal

Grid BFS (flood fill & shortest steps)

  • A 2D grid of cells: land and water, open and blocked, like a game map
  • "Count the islands / regions" or "size of the biggest region"
  • "Fewest steps from here to there" when each move costs 1

Grid flood fillBFS shortest path (unweighted)

the one rule

The invariant

Every cell is marked the moment it is pushed, so no cell enters the queue twice.

write it from memory

The template

fewest steps in a grid

javajava.util.*
/** Fewest steps from the top-left to the bottom-right cell, moving through 0s only; -1 if impossible. */static int shortestSteps(int[][] grid) {    int rows = grid.length, cols = grid[0].length;    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};           // the 4 neighbours    if (grid[0][0] != 0 || grid[rows - 1][cols - 1] != 0) return -1; // blocked start or end    int[][] dist = new int[rows][cols];    for (int[] row : dist) Arrays.fill(row, -1);    Deque<int[]> queue = new ArrayDeque<>();    dist[0][0] = 0;    queue.offer(new int[] {0, 0});    while (!queue.isEmpty()) {        int[] cell = queue.poll();        int r = cell[0], c = cell[1];        if (r == rows - 1 && c == cols - 1) return dist[r][c];   // goal popped        for (int[] d : dirs) {            int nr = r + d[0], nc = c + d[1];            if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue; // off the grid            if (grid[nr][nc] != 0 || dist[nr][nc] != -1) continue;      // wall or seen            dist[nr][nc] = dist[r][c] + 1;                               // mark on push            queue.offer(new int[] {nr, nc});        }    }    return -1;}

The grid is the graph: a cell is a node, and its 4 neighbours are its edges. No adjacency list needed.

fill in the blanks — only these lines change per problem

  1. line 4Which moves are allowed: 4 directions here, 8 for Shortest Path in Binary Matrix, or knight moves.
  2. line 5Edge checks before the search, e.g. a blocked start or end means -1 straight away.
  3. line 18Which cells you may step on: 0 here, '1' for land, or "height difference ≤ k".
  4. line 14The answer to return. Some problems count cells, not steps, so you return dist + 1.

count regions (flood fill)

javajava.util.*
/** Number of islands: groups of '1' cells joined up, down, left or right. */static int countIslands(char[][] grid) {    int rows = grid.length, cols = grid[0].length;    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};    boolean[][] seen = new boolean[rows][cols];    int islands = 0;    for (int r = 0; r < rows; r++) {        for (int c = 0; c < cols; c++) {            if (grid[r][c] != '1' || seen[r][c]) continue;   // not a new land cell            islands++;                                       // a new island starts here            Deque<int[]> queue = new ArrayDeque<>();            seen[r][c] = true;            queue.offer(new int[] {r, c});            while (!queue.isEmpty()) {                       // flood the whole island                int[] cell = queue.poll();                for (int[] d : dirs) {                    int nr = cell[0] + d[0], nc = cell[1] + d[1];                    if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;                    if (grid[nr][nc] != '1' || seen[nr][nc]) continue;                    seen[nr][nc] = true;                    queue.offer(new int[] {nr, nc});                }            }        }    }    return islands;}

Scan every cell. Each new land cell starts one island, and the BFS floods all of it so it is never counted again.

fill in the blanks — only these lines change per problem

  1. line 10What to record per region: a count here, or the region's size for Max Area of Island.

complexity

What it costs

time O(rows × cols)
Each cell is pushed at most once and checks its 4 neighbours, so the work is 4 × rows × cols at most.
space O(rows × cols)
The dist or seen grid, plus a queue that can hold a large part of the grid at once.

watch out

Common bugs

  • Checking bounds after reading grid[nr][nc]. Check nr and nc first, or you get an index out of range.
  • Mixing up rows and columns: grid.length is rows, grid[0].length is columns.
  • Marking cells when they are popped. A cell can be pushed by up to 4 neighbours and the queue blows up.

use it

Practise it on

learn it properly