Practice › Graphs
Flood Fill
Easy · Graphs · Asked at Amazon, Google, Microsoft, Uber
Starting from cell (sr, sc), recolor that cell and every cell connected to it (up/down/left/right) that has the same original color to color. Print the resulting grid.
Input
First line: r c. Next r lines: c integers each. Last line: sr sc color (0-based row and column).
Output
The grid after the flood fill, r lines.
Constraints
- 1 ≤ r, c ≤ 50
- 0 ≤ values, color < 2^16
BFS or DFS from the start. If the start already has the new color, nothing changes — return immediately or you will loop forever.
Example 1
Input
3 3 1 1 1 1 1 0 1 0 1 1 1 2
Output
2 2 2 2 2 0 2 0 1
Example 2
Input
2 3 0 0 0 0 0 0 0 0 0
Output
0 0 0 0 0 0
Hints
- Remember the original color of the start cell.
- BFS/DFS to every neighbour with that original color, recoloring as you go. If the new color equals the original color, change nothing.
Approach
Let orig = g[sr][sc]. If orig == color, print the grid unchanged — otherwise recolored cells would look unvisited and the search would never end. Else recolor the start and BFS: for each cell, recolor and enqueue every in-bounds neighbour whose value is still orig. Recoloring doubles as the visited mark.
Complexity: O(r · c) time · O(r · c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<vector<long long>> g(R, vector<long long>(C));
for (auto &row : g)
for (auto &x : row) cin >> x;
int sr, sc;
long long color;
cin >> sr >> sc >> color;
long long orig = g[sr][sc];
if (orig != color) {
queue<pair<int, int>> q;
q.push({sr, sc});
g[sr][sc] = color;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int a = x + dx[d], b = y + dy[d];
if (a >= 0 && b >= 0 && a < R && b < C && g[a][b] == orig) g[a][b] = color, q.push({a, b});
}
}
}
for (auto &row : g)
for (int j = 0; j < C; j++) cout << row[j] << (j + 1 < C ? " " : "\n");
return 0;
}Python solution
import sys
from collections import deque
data = list(map(int, sys.stdin.read().split()))
R, C = data[0], data[1]
g = [data[2 + i * C : 2 + (i + 1) * C] for i in range(R)]
sr, sc, color = data[2 + R * C : 5 + R * C]
orig = g[sr][sc]
if orig != color:
g[sr][sc] = color
q = deque([(sr, sc)])
while q:
x, y = q.popleft()
for a, b in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
if 0 <= a < R and 0 <= b < C and g[a][b] == orig:
g[a][b] = color
q.append((a, b))
print("\n".join(" ".join(map(str, row)) for row in g))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int R = sc.nextInt(), C = sc.nextInt();
long[][] g = new long[R][C];
for (int i = 0; i < R; i++)
for (int j = 0; j < C; j++) g[i][j] = sc.nextLong();
int sr = sc.nextInt(), scol = sc.nextInt();
long color = sc.nextLong(), orig = g[sr][scol];
if (orig != color) {
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] {sr, scol});
g[sr][scol] = color;
int[] dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};
while (!q.isEmpty()) {
int[] p = q.poll();
for (int d = 0; d < 4; d++) {
int a = p[0] + dx[d], b = p[1] + dy[d];
if (a >= 0 && b >= 0 && a < R && b < C && g[a][b] == orig) {
g[a][b] = color;
q.add(new int[] {a, b});
}
}
}
}
StringBuilder sb = new StringBuilder();
for (long[] row : g) {
for (int j = 0; j < C; j++) sb.append(row[j]).append(j + 1 < C ? " " : "\n");
}
System.out.print(sb);
}
}