Painter Fill

See the original problem on HackerRank.

Solutions

This is a classical problem called Flood fill that can be solved in a relatively easy way: look for all pixels in the image that are connected to the start pixel by a path of the target color and changes them to the new color.

This algorithm is typically implemented using either recursion or a stack (or queue). This is a recursive implementation example:

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56


void recursivePaintFill(vector<vector<int>>& image, int r, int c, int color, int newColor) 
{
    if (image[r][c] == color) 
    {
        image[r][c] = newColor;
        if (r >= 1) 
        {
            recursivePaintFill(image, r - 1, c, color, newColor);
        }
        if (c >= 1) 
        {
            recursivePaintFill(image, r, c - 1, color, newColor);
        }
        if (r + 1 < image.size()) 
        {
            recursivePaintFill(image, r + 1, c, color, newColor);
        }
        if (c + 1 < image.front().size()) 
        {
            recursivePaintFill(image, r, c + 1, color, newColor);
        }
    }
}

void paintFill(vector<vector<int>>& image, int sr, int sc, int color)
{
    if (color != image[sr][sc])
    {
        recursivePaintFill(image, sr, sc, image[sr][sc], color);
    }
}

void printImage(vector<vector<int>>& image)
{
    for (const auto& row : image)
    {
        copy(begin(row), prev(end(row)), ostream_iterator<int>(cout, " "));
        os << row.back() << '\n';
    }
    os << '\n';
}

int main()
{
    int m, n, sr, sc, color;
    cin >> m >> n >> sr >> sc >> color;
    vector<vector<int>> image(m);
    for (auto& row : image)
    {
        copy_n(istream_iterator<int>(file), n, back_inserter(row));
    }

    paintFill(image, sr, sc, color);
    printImage(image);
}

Alternatively, here is a stack-based implementation:

 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
28
29
30
31

void paintFill(vector<vector<int>>& image, int sr, int sc, int color)
{
    const auto oldColor = image[sr][sc];
    if (oldColor == color)
        return;

    const auto m = image.size();
    const auto n = image.front().size();

    stack<pair<int, int>> next;
    next.emplace(sr, sc);
    image[sr][sc] = color; 

    const auto visitIfRelevant = [&](int x, int y){            
        if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == oldColor)
        {
            image[x][y] = color;
            next.emplace(x, y);
        }
    };

    while (!next.empty())
    {
        const auto [x, y] = next.top();
        next.pop();
        visitIfRelevant(x+1, y);
        visitIfRelevant(x, y+1);
        visitIfRelevant(x-1, y);
        visitIfRelevant(x, y-1);
    }
}

Both are are linear in space and time, and apply a depth-first search pattern. These solutions pass all the test cases.

An optimization

The proposed solutions have three main disadvantages:

  • use a lot of memory
  • make a lot of pixel checks (at most four times per pixel)
  • their access pattern is not cache-friendly (especially for the queue-based solution, since we process pixels level by level - the stack variant is a bit better since it dives deep in one direction, so it tends to stay in one region of the image longer, this means better locality in practice, but its access pattern is still less predictable).

A possibile optimization consists in the span filling (or scanline) approach. Instead of queuing individual pixels, we work row by row:

  • from a seed pixel, fill the entire row left and right, noting the start and end (lx to rx)
  • then scan the rows immediately above and below that run, looking for new runs to fill.

The key optimization: you only need to remember the start of each new run, not every pixel in it (since once you have a starting point, you can always re-expand left and right automatically). Using a stack or queue just controls the order you tackle runs (depth-first vs breadth-first) but either way you’re processing contiguous chunks of memory at a time, which is what makes it cache-friendly.

Here is a possible implementation:

 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

void paintFillScanline(std::vector<std::vector<int>>& image, int sr, int sc, int color)
{
    const auto m = image.size();
    const auto n = image.front().size();
    const auto oldColor = image[sr][sc];

    if (oldColor == color) 
        return;

    std::stack<std::pair<int, int>> next;
    next.emplace(sr, sc);

    while (!next.empty())
    {
        auto [x, y] = next.top();
        next.pop();

        if (x < 0 || x >= m || y < 0 || y >= n || image[x][y] != oldColor)
            continue;

        // Expand left
        int left = y;
        while (left > 0 && image[x][left - 1] == oldColor)
            --left;

        // Expand right
        int right = y;
        while (right < n - 1 && image[x][right + 1] == oldColor)
            ++right;

        std::fill(begin(image[x])+left, begin(image[x])+right+1, color);

        // Add seeds for adjacent rows
        for (int i = left; i <= right; ++i) 
        {
            if (x > 0 && image[x - 1][i] == oldColor)
                next.emplace(x - 1, i);
            if (x < m - 1 && image[x + 1][i] == oldColor)
                next.emplace(x + 1, i);
        }
    }
}

Note that the “Expand left” and “Expand right” parts might be rewritten in terms of std::find_if (or std::find_if_not).

For the curious reader, there are other interesting ways to solve this problem:

comments powered by Disqus