You're not signed in!

Sign in to save your progress and sync your settings across devices.

Somewhat Frequent
 0/9

Flood Fill

Author: Darren Yao

Finding connected components in a graph respresented by a grid.

Focus Problem – read through this problem before continuing!

Resources

Resources
IUSACOmodule is based off this
CP2code + example

Introduction

Flood fill is an algorithm that identifies and labels the connected component that a particular cell belongs to, in a multi-dimensional array. Essentially, it’s DFS, but on a grid, and we want to find the connected component of all the connected cells with the same number.

For example, let’s look at the following grid and see how floodfill works, starting from the top-left cell. The color scheme will be the same: red for the node currently being processed, blue for nodes already visited, and uncolored for nodes not yet visited.

221
211
221

221
211
221

221
211
221

221
211
221

221
211
221

221
211
221

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 an 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:

C++

1int grid[MAXN][MAXM];
2int n, m;
3
4int main(){
5 cin >> n >> m;
6 for(int i = 0; i < n; i++){
7 for(int j = 0; j < m; j++){
8 cin >> grid[i][j];
9 }
10 }

Java

1static int[][] grid;
2static int n, m;
3
4public static void main(String[] args){
5 int n = r.nextInt();
6 int m = r.nextInt();
7 grid = new int[n][m];
8 for(int i = 0; i < n; i++){
9 for(int j = 0; j < m; j++){
10 grid[i][j] = r.nextInt();

Implementation

When doing floodfill, 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 from the squares above, below, and to the left and right of our current square. The algorithm to find the size of a connected component in a grid using floodfill 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 floodfill, and the floodfill algorithm itself.

C++

1int grid[MAXN][MAXM]; // the grid itself
2int n, m; // grid dimensions, rows and columns
3bool visited[MAXN][MAXM]; // keeps track of which nodes have been visited
4int currentSize = 0; // reset to 0 each time we start a new component
5
6void floodfill(int r, int c, int color){
7 if(r < 0 || r >= n || c < 0 || c >= m) return; // if outside grid
8 if(grid[r][c] != color) return; // wrong color
9 if(visited[r][c]) return; // already visited this square
10 visited[r][c] = true; // mark current square as visited

Java

1static int[][] grid; // the grid itself
2static int n, m; // grid dimensions, rows and columns
3static boolean[][] visited; // keeps track of which nodes have been visited
4static int currentSize = 0; // reset to 0 each time we start a new component
5
6public static void main(String[] args){
7 /**
8 * input code and other problem-specific stuff here
9 */
10 for(int i = 0; i < n; i++){

Solution - Counting Rooms

C++

1#include <bits/stdc++.h>
2using namespace std;
3
4#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
5#define F0R(i,a) FOR(i,0,a)
6
7const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};
8
9int n,m;
10string g[2500];

Java

Warning!

Recursive implementations of floodfill in Java can sometimes lead to StackOverflowError. To avoid Stack Overflow, use your own stack in an iterative implementation like the one below.
1import java.io.*;
2import java.util.*;
3
4public class test{
5 public static boolean[][] v;
6 public static char[][] g;
7 public static final int xd[] = {0,1,0,-1}, yd[] = {1,0,-1,0};
8 public static int N, M;
9 static class Pair{
10 public int a, b;

Problems

Module Progress:

Give Us Feedback on Flood Fill!