Flood Fill

C++

Copy
#include <iostream>

using namespace std;

const int MAX_N = 1000;

int grid[MAX_N][MAX_N];
int row_num;
int col_num;

Java

Copy
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

Copy
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()])

C++

Copy
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

Java

Copy
public class Floodfill {
	private static int[][] grid;  // the grid itself
	private static int rowNum;
	private static int colNum;           // grid dimensions, rows and columns
	private static boolean[][] visited;  // keeps track of which nodes have been
	                                     // visited
	private static int currSize = 0;  // reset to 0 each time we start a new component

	public static void main(String[] args) {
		/*

Python

Copy
import sys

MAX_N = 100
sys.setrecursionlimit(2**30)  # pretty much disable the recurion limit

row_num = MAX_N
col_num = MAX_N
grid = [[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

C++

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

Copy
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

Copy
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.

Copy
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 here
grid.append(["#"] * len(grid[0]))  # Add the bottom row
visited.append([True] * len(visited[0]))
for row_grid, row_visited in zip(grid, visited):  # Add right side