Flood Fill Algorithm using Breadth First Search

You are given a two dimensional array matrix, containing strings “r”, “g”, and “b”. Perform a floodfill operation at row r, column c with the color target.

A floodfill operation replaces elements that are connected to matrix[r][c] (up/right/down/left) and have the same color as matrix[r][c] with the color of target.

Constraints
n, m ≤ 200 where n and m are the number of rows and columns in matrix
Example 1
Input

1 2 3 4 5

matrix = [     ["r", "r", "r"],     ["r", "g", "b"],     ["g", "b", "b"] ]

matrix = [
    ["r", "r", "r"],
    ["r", "g", "b"],
    ["g", "b", "b"]
]

r = 0
c = 0
target = “g”
Output

1 2 3 4 5

[     ["g", "g", "g"],     ["g", "g", "b"],     ["g", "b", "b"] ]

[
    ["g", "g", "g"],
    ["g", "g", "b"],
    ["g", "b", "b"]
]

Explanation
The red elements connected to matrix[0][0] are replaced with “g”.

Using Breadth First Search Algorithm to Perform Flood Fill

We can use Breadth First Search Algorithm (BFS) to perform the flood fill. We need to note that starting pixel, and then also avoid to re-paint the pixel in case the starting pixel and the target pixel is the same. We can use a hash set to remember the pixels that we have painted.

Also, for each pixel, we need to check its four neighbour pixels and enqueue if they are qualified (in range and the same pixel as the starting pixel).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

vector<vector<string>> floodFill(vector<vector<string>>& matrix, int r, int c, string target) {
    int rows = matrix.size();
    if (0 == rows) return matrix;
    int cols = matrix[0].size();
    if (0 == cols) return matrix;
    unordered_set<string> vis;
    queue<vector<int>> Q;
    Q.push({r, c});
    vector<int> d{1, 0, -1, 0, 1};
    auto cur = matrix[r][c];
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        auto key = std::to_string(p[0]) + "," + std::to_string(p[1]);
        if (vis.count(key)) continue;
        vis.insert(key);  
        matrix[p[0]][p[1]] = target;
        for (int i = 0; i < 4; ++ i) {
            int nx = p[0] + d[i];
            int ny = p[1] + d[i + 1];
            if ((nx >= 0) && (ny >= 0) && (nx < rows) && (ny < cols) && (matrix[nx][ny] == cur)) {
                Q.push({nx, ny});
            }
        }
    }
    return matrix;
}

vector<vector<string>> floodFill(vector<vector<string>>& matrix, int r, int c, string target) {
    int rows = matrix.size();
    if (0 == rows) return matrix;
    int cols = matrix[0].size();
    if (0 == cols) return matrix;
    unordered_set<string> vis;
    queue<vector<int>> Q;
    Q.push({r, c});
    vector<int> d{1, 0, -1, 0, 1};
    auto cur = matrix[r][c];
    while (!Q.empty()) {
        auto p = Q.front();
        Q.pop();
        auto key = std::to_string(p[0]) + "," + std::to_string(p[1]);
        if (vis.count(key)) continue;
        vis.insert(key);  
        matrix[p[0]][p[1]] = target;
        for (int i = 0; i < 4; ++ i) {
            int nx = p[0] + d[i];
            int ny = p[1] + d[i + 1];
            if ((nx >= 0) && (ny >= 0) && (nx < rows) && (ny < cols) && (matrix[nx][ny] == cur)) {
                Q.push({nx, ny});
            }
        }
    }
    return matrix;
}

The time complexity is O(NM) where N and M are the dimensions of the matrix. The space complexity is also O(NM) as we are using a queue to perform the BFS.

Flood Fill Algorithms

• Flood Fill Algorithm using Breadth First Search
• The Image Flood Fill Algorithm (C++)
• Teaching Kids Programming – Image Flood Fill via DFS and BFS Algorithm

–EOF (The Ultimate Computing & Technology Blog) —