Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Remember the original color of the start cell.
  2. 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);
    }
}

Solve Flood Fill online · All practice problems