What is a flood fill?

Flood fill is operated on a multidimensional array (often a 2 x 2 rectangle), with a start row and column. From that start position, every connected position in the array is filled with the same value. For example, in paint programs, the "bucket" fill tool usually performs a flood fill with a certain color. In games such as Go and Minesweeper, flood fill is used to determine which pieces are cleared.

Flood fill is usually implemented as a recursive algorithm which makes four recursive calls. Each recursive call tries going north, south, east, and west. To avoid infinite recursion, some method is needed to prevent repeating the same positions in the array.

The flood fill algorithm

Here it is in pseudo code:

//void FloodFill ( current_position , start_value , visited_datastructure ) {
//    if current_position has been visited, return
//    if current_position is not equal to start_value, return
//    mark current_position as visited
//    change current_position to equal start_value in the array
//    run FloodFill ( one step north , start_value , visited_datastructure )
//    run FloodFill ( one step south , start_value , visited_datastructure )
//    run FloodFill ( one step east  , start_value , visited_datastructure )
//    run FloodFill ( one step west  , start_value , visited_datastructure )
//}

Floodfill in code

We will start with a two dimensional array of characters as an argument, such as the one commented below:

//##....###
//#...###..
//#.#..#..s
//####.#...
//##...####

As you can see, one of the positions is marked with a lower case 's', signifying the start position. The function should replace all dots "." that are reachable from the start position with a star "*", assuming you can go up down right and left. We assume you cannot move onto a pound symbol "#", and we assume you cannot move diagonally. The result should be:

//##....###
//#...###**
//#.#..#**s
//####.#***
//##...####

Here we have the full program that generates a map and runs the floodFill function:

public class MyProgram {
    public static void main(String[] args) {
		//Create the char[][] grid:
		String map = "##....###!#...###..!#.#..#..s!####.#...!##...###.";
		String[] lines = map.split("!");
		char[][] grid = new char[lines.length][lines[0].length()];
		for (int j=0;j<grid.length;j++) for (int i=0;i<grid[j].length;i++) grid[j][i] = lines[j].charAt(i);
		
		//Run floodFill on the grid given a start position and an empty visited array
		floodFill(grid, new boolean[grid.length][grid[0].length], 2, 8); //row 2, 8 is where the 's' is
		
		//Print the resulting grid:
		for (int j=0;j<grid.length;j++) {
			for (int i=0;i<grid[j].length;i++) System.out.print(grid[j][i]);
			System.out.println();
		}
    }
	
	//Floodfill algorithm:
	static void floodFill(char[][] grid, boolean[][] visited, int r, int c) {
		//quit if off the grid:
		if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
		
		//quit if visited:
		if(visited[r][c]) return;
		visited[r][c] = true;
		
		//quit if hit wall:
		if(grid[r][c]=='#') return;
		
		//we want to visit places with periods in them:
		if(grid[r][c]=='.') grid[r][c] = '*';
		
		//recursively fill in all directions
		floodFill(grid,visited,r+1,c);
		floodFill(grid,visited,r-1,c);
		floodFill(grid,visited,r,c+1);
		floodFill(grid,visited,r,c-1);
	}
}

What is a flood count?

Flood count is very similar to flood fill, except we want to determine how many locations would be filled. Additionally, this algorithm does not modify the array. For example, this is a commonly used algorithm in games where an action is performed when enough objects are adjacent to each other (Candy Crush, etc).

Here it is in pseudo code:

//int FloodCount ( current_position , start_value , visited_datastructure ) {
//    if current_position has been visited, return
//    if current_position is not equal to start_value, return
//    mark current_position as visited
//    set output to 1
//    output += FloodCount ( one step north , start_value , visited_datastructure )
//    output += FloodCount ( one step south , start_value , visited_datastructure )
//    output += FloodCount ( one step east  , start_value , visited_datastructure )
//    output += FloodCount ( one step west  , start_value , visited_datastructure )
//    return output;
//}

The key to this algorithm is that we return the sum of the recursive calls.

Floodcount in code

We will start with a two dimensional array of characters as an argument, such as the one commented below:

//##....###
//#...###..
//#.#..#..s
//####.#...
//##...####

Here we have the full program that generates a map and runs the floodCount function:

public class MyProgram {
    public static void main(String[] args) {
		//Create the char[][] grid:
		String map = "##....###!#...###..!#.#..#..s!####.#...!##...###.";
		String[] lines = map.split("!");
		char[][] grid = new char[lines.length][lines[0].length()];
		for (int j=0;j<grid.length;j++) for (int i=0;i<grid[j].length;i++) grid[j][i] = lines[j].charAt(i);
		
		//Run floodCount on the grid given a start position and an empty visited array
		int count = floodCount(grid, new boolean[grid.length][grid[0].length], 2, 8); //row 2, 8 is where the 's' is
		
		//Print the resulting grid which hasn't changed:
		for (int j=0;j<grid.length;j++) {
			for (int i=0;i<grid[j].length;i++) System.out.print(grid[j][i]);
			System.out.println();
		}
		
		//Print the sum count
		System.out.println(count);
    }
	
	//floodCount algorithm:
	static int floodCount(char[][] grid, boolean[][] visited, int r, int c) {
		if(r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return 0;
		if(visited[r][c]) return 0;
		visited[r][c] = true;
		if(grid[r][c]=='#') return 0;
		int out = 0;
		if(grid[r][c]=='.') out++;
		out += floodCount(grid,visited,r+1,c);
		out += floodCount(grid,visited,r-1,c);
		out += floodCount(grid,visited,r,c+1);
		out += floodCount(grid,visited,r,c-1);
		return out;
	}
}