Somewhat Frequent
 0/14

Flood Fill

Author: Darren Yao

Contributors: Kevin Sheng, George Pong

Finding connected components in a graph represented by a grid.

Edit This Page

Resources

Resources
IUSACO

module is based off this

CP2

code + example

Introduction

Flood fill is an algorithm that identifies and labels the connected component that a particular cell belongs to in a multidimensional array.

For example, suppose that we want to split the following grid into components of connected cells with the same number.

2 2 1
2 1 2
2 2 1

Let's start the flood fill from the top-left cell. The color scheme will be red for the node currently being processed, blue for nodes already visited, and uncolored for nodes not yet visited.

2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1
2 2 1
2 1 2
2 2 1

As opposed to an explicit graph where the edges are given, a grid is an implicit graph. This means that the neighbors are just the nodes directly adjacent in the four cardinal directions.

Usually, grids given in problems will be NN by MM, so the first line of the input contains the numbers NN and MM. In this example, we will use a two-dimensional integer array to store the grid, but depending on the problem, a two-dimensional character array or a two-dimensional boolean array may be more appropriate. Then, there are NN rows, each with MM numbers containing the contents of each square in the grid. Example input might look like the following (varies between problems):

3 4
1 1 2 1
2 3 2 1
1 3 3 3

And we’ll want to input the grid as follows:

#include <iostream>
using namespace std;
const int MAX_N = 1000;
int grid[MAX_N][MAX_N];
int row_num;
int col_num;

Implementation

When doing flood fill, we will maintain an N×MN\times M array of booleans to keep track of which squares have been visited, and a global variable to maintain the size of the current component we are visiting. Make sure to store the grid, the visited array, dimensions, and the current size variable globally.

This means that we want to recursively call the search function for the squares above, below, and to the left and right of our current square. Due to its recursive nature, floodfill can be thought of as a modified version of DFS. The algorithm to find the size of a connected component in a grid using flood fill is as follows (we’ll also maintain a 2D visited array).

The code below shows the global/static variables we need to maintain while doing flood fill and the flood fill algorithm itself:

const int MAX_N = 1000;
int grid[MAX_N][MAX_N]; // the grid itself
int row_num;
int col_num;
bool visited[MAX_N][MAX_N]; // keeps track of which nodes have been visited
int curr_size = 0; // reset to 0 each time we start a new component
void floodfill(int r, int c, int color) {
if ((r < 0 || r >= row_num || c < 0 || c >= col_num) // if out of bounds

Example - Counting Rooms

Focus Problem – try your best to solve this problem before continuing!

Implementation

Warning!

Recursive implementations of flood fill sometimes lead to

  • Stack overflow if you didn't include the appropriate compiler options for adjusting the stack size
  • Memory limit exceeded if you run the recursive implementation on a really big grid (i.e., running the above code on a 4000×40004000\times 4000 grid may exceed 256 MB)
    • Non-recursive implementations generally use less memory than recursive ones.

A non-recursive implementation of flood fill adds adjacent nodes to a stack or queue, similar to BFS, and is usually implemented as follows:

#include <iostream>
#include <stack>
#include <string>
using namespace std;
const int MAX_N = 2500;
const int R_CHANGE[]{0, 1, 0, -1};
const int C_CHANGE[]{1, 0, -1, 0};

Problems

StatusSourceProblem NameDifficultyTags
SilverEasy
Show TagsFlood Fill
CFEasy
Show TagsFlood Fill
Old SilverEasy
Show TagsBinary Search, Flood Fill
SilverNormal
Show TagsFlood Fill
SilverNormal
Show TagsFlood Fill
SilverNormal
Show TagsFlood Fill
SilverNormal
Show TagsFlood Fill
SilverNormal
Show TagsFlood Fill
SilverNormal
Show TagsFlood Fill
SilverNormal
Show TagsFlood Fill
SilverHard
Show TagsFlood Fill
SilverHard
Show TagsFlood Fill
SilverHard
Show TagsFlood Fill

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!