# Flood Fill

Author: Darren Yao

Contributors: Kevin Sheng, George Pong

Finding connected components in a graph represented by a grid.

### Prerequisites

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

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

Java

import java.io.*;import java.util.StringTokenizer;public class Floodfill {private static int[][] grid;private static int rowNum;private static int colNum;public static void main(String[] args) throws IOException {BufferedReader read = new BufferedReader(new InputStreamReader(System.in));StringTokenizer dims = new StringTokenizer(read.readLine());

Python

row_num, col_num = [int(i) for i in input().split()]grid = []for _ in range(row_num):grid.append([int(i) for i in input().split()])

### Implementation

When doing flood fill, 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 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:

C++

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

Java

public class Floodfill {private static int[][] grid; // the grid itselfprivate static int rowNum;private static int colNum; // grid dimensions, rows and columnsprivate static boolean[][] visited; // keeps track of which nodes have been// visitedprivate static int currSize = 0; // reset to 0 each time we start a new componentpublic static void main(String[] args) {/*

Python

import sysMAX_N = 100sys.setrecursionlimit(2**30) # pretty much disable the recurion limitrow_num = MAX_Ncol_num = MAX_Ngrid = [[0 for _ in range(col_num)] for _ in range(row_num)]visited = [[False for _ in range(col_num)] for _ in range(row_num)]curr_size = 0

## 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\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:

C++

#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};

Java

import java.io.*;import java.util.*;public class RoomCount {public static final int R_CHANGE[] = {0, 1, 0, -1};public static final int C_CHANGE[] = {1, 0, -1, 0};private static boolean[][] visited;private static char[][] building;private static int rowNum;

Python

row_num, col_num = [int(i) for i in input().split()]grid = [input() for _ in range(row_num)]visited = [[False for _ in range(col_num)] for _ in range(row_num)]def floodfill(r: int, c: int):global visited"""Note: you can also use queue and pop from the

### Python Optimization: Padding

We can speed up floodfill by a constant time factor using an alternate way of ensuring no out-of-bounds accessing of the grid happens. Imagine a one-cell padding on all four sides of the array, for which the cells of which are marked as already having been visited. We can then get rid of the bound checking where we check if the next cell we visit is inclusive between 0 and the dimensions of the array. These cells in the padding may be added to the queue, but when they are visited in the floodfill loop, they are skipped for being marked visited and no out-of-bounds accessing happens. Furthermore, no additional out-of-bounds cells beyond the padding are added to the queue.

One option for adding padding would be to start our entire grid with a filler row in the beginning, and also start each row with an element before we take in input. After input, then we can add the padding at the ends of rows and bottom of the grid. However, in python we only need to do the latter part as we can have the padding at the right and bottom of the matrix act as the padding for the left and top as the coordinate for the left and top, -1, would be interpreted as the end of the array.

The speed benefit of this optimization is only noticeable for some large inputs (it may be even slower for small inputs) and likely only beneficial when using a slow language such as Python, where even the expected solution may TLE. Our new implementation for the previous problem would be as follows.

row_num, col_num = [int(i) for i in input().split()]# We make each row a list so we can append at the end.grid = [[char for char in input()] for _ in range(row_num)]visited = [[False for _ in range(col_num)] for _ in range(row_num)]# We add padding heregrid.append(["#"] * len(grid[0])) # Add the bottom rowvisited.append([True] * len(visited[0]))for row_grid, row_visited in zip(grid, visited): # Add right side

## Problems

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

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

CF | Easy | ## Show TagsFlood Fill | |||

Old Silver | Easy | ## Show TagsBinary Search, Flood 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 | |||

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!