Skip to content
CCC Python Course

BFS and flood fill (iterative)

Stage
4
Module
M4.13
Lessons
1

In this module

  • Explain why a queue makes breadth-first search find shortest paths.
  • Write an iterative BFS that finds the fewest moves across a grid.
  • Use flood fill to count connected regions and measure their sizes.
  • Replace deep recursion with a deque so large grids do not crash.

Before this module

M4.8Stacks and queuesM4.12Graphs I: modelling and adjacency lists

Lessons

  1. 1BFS and flood fill (iterative)

Practice

Try these on the judges. Each link opens the problem on WMOJ or DMOJ.

  1. 2024 J5
    Harvest Waterloo (opens on WMOJ in a new tab) WMOJ

    Add up what a farmer can harvest from one patch of a field.

  2. 2020 S2
    Escape Room (opens on DMOJ in a new tab) DMOJ

    Decide whether you can escape a grid of numbered rooms.

    Why DMOJ: An older grid reachability problem, good extra practice with a queue.

  3. 2018 J5
    Choose your own path (opens on DMOJ in a new tab) DMOJ

    Check a choose-your-own-adventure book, page by page.

    Why DMOJ: An older problem where the search runs over pages instead of grid cells.