# Flood Fill

Author: Darren Yao

### Prerequisites

Finding connected components in a graph represented by a grid.

## 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 floodfill 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 |

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 $N$ by $M$, so the first line of the input contains the numbers $N$ and $M$. 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 $N$ rows, each with $M$ 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++

int grid[MAXN][MAXM];int n, m;int main(){cin >> n >> m;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){cin >> grid[i][j];}}return 0;}

Java

static int[][] grid;static int n, m;public static void main(String[] args){int n = r.nextInt();int m = r.nextInt();grid = new int[n][m];for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){grid[i][j] = r.nextInt();}}}

### Implementation

When doing floodfill, we will maintain an $N\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++

int grid[MAXN][MAXM]; // the grid itselfint n, m; // grid dimensions, rows and columnsbool visited[MAXN][MAXM]; // keeps track of which nodes have been visitedint currentSize = 0; // reset to 0 each time we start a new componentvoid floodfill(int r, int c, int color){if(r < 0 || r >= n || c < 0 || c >= m) return; // if outside gridif(grid[r][c] != color) return; // wrong colorif(visited[r][c]) return; // already visited this squarevisited[r][c] = true; // mark current square as visited

Java

static int[][] grid; // the grid itselfstatic int n, m; // grid dimensions, rows and columnsstatic boolean[][] visited; // keeps track of which nodes have been visitedstatic int currentSize = 0; // reset to 0 each time we start a new componentpublic static void main(String[] args){/*** input code and other problem-specific stuff here*/for(int i = 0; i < n; i++){

## Example - Counting Rooms

Focus Problem – read through this problem before continuing!

### Implementation

C++

#include <bits/stdc++.h>using namespace std;#define FOR(i,a,b) for (int i = (a); i < (b); ++i)#define F0R(i,a) FOR(i,0,a)const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0};int n,m;string 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.

import java.io.*;import java.util.*;public class test{public static boolean[][] v;public static char[][] g;public static final int xd[] = {0,1,0,-1}, yd[] = {1,0,-1,0};public static int N, M;static class Pair{public int a, b;

## Problems

Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|

Silver | Easy | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

CCO | Normal | ## Show TagsFlood Fill | |||||||

Silver | Normal | ## Show TagsFlood Fill | |||||||

Silver | Hard | ## Show TagsFlood Fill | |||||||

Silver | Hard | ## Show TagsFlood Fill | |||||||

Silver | Hard | ## 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!