Comment on page
Paint Fill

8.10 Paint Fill: Implement the "paint fill" function that one might see on many image editing programs. That is, given a screen (represented by a two-dimensional array of colors), a point, and a new color, fill in the surrounding area until the color changes from the original color.
My first thought was just to prefrom an iterative form of breath first search, but since I have done this before, I figured that I'd write myself a depth first search algorithm.
The idea is simple. First I gathered information to make sure the inputs were valid, and other things such as the color the user selects.
Then I passed nessessary information into a recursive function that would color the cell if the it is a valid cell. This check has a few conditions such as checking cell boundaries, and valid colors. Depth first search basically defines a priority of operations to perform. In my case, there were arbitrary: look up, down, right, and then left. In that priority.
bool is_valid(pair<int, int> loc, vector<vector<char>> &image, int size_row, int size_col, char colorThis) {
    return (loc.first < size_row && 
        loc.second < size_col && 
        loc.first >= 0 && 
        loc.second >= 0 &&
        image.at(loc.first).at(loc.second) == colorThis);
}
​
void fillPaint_rec(vector<vector<char>> &image, char color, char colorThis, pair<int, int> loc) {
​
    // up
    if (is_valid(make_pair(loc.first - 1, loc.second), image, image.size(), image.at(0).size(), colorThis)) {
        image.at(--loc.first).at(loc.second) = color;
        fillPaint_rec(image, color, colorThis, loc);
    }
    // down
    if (is_valid(make_pair(loc.first + 1, loc.second), image, image.size(), image.at(0).size(), colorThis)) {
        image.at(++loc.first).at(loc.second) = color;
        fillPaint_rec(image, color, colorThis, loc);
    }
    // right
    if (is_valid(make_pair(loc.first, loc.second + 1), image, image.size(), image.at(0).size(), colorThis)) {
        image.at(loc.first).at(++loc.second) = color;
        fillPaint_rec(image, color, colorThis, loc);
    }
    // left
    if (is_valid(make_pair(loc.first, loc.second - 1), image, image.size(), image.at(0).size(), colorThis)) {
        image.at(loc.first).at(--loc.second) = color;
        fillPaint_rec(image, color, colorThis, loc);
    }
}
​
// loc = row | col
void fillPaint(vector<vector<char>> &image, char color, pair<int, int> loc) {
    // error checking
    if (image.empty() || loc.first >= image.size() || loc.second >= image.at(0).size())
        return;
​
    // get color clicked on
    char colorThis = image.at(loc.first).at(loc.second);
    fillPaint_rec(image, color, colorThis, loc);
}
​
int main()
{
    vector<vector<char>> image = {
        { 'B','.', '.', '.', '.', '.', '.', '.', '.', '.' },
        { '.','B', '.', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', 'Y', 'Y' },
        { '.','.', 'B', '.', '.', '.', '.', 'Y', '.', '.' },
        { '.','.', '.', 'B', '.', '.', 'Y', '.', '.', '.' },
        { '.','.', '.', '.', 'B', 'Y', '.', '.', '.', '.' },
        { '.','.', '.', '.', 'Y', 'B', '.', '.', '.', '.' },
        { '.','.', '.', '.', 'Y', '.', 'B', '.', '.', '.' },
        { '.','.', '.', '.', 'Y', '.', '.', 'B', '.', '.' },
        { '.','.', '.', 'Y', '.', '.', '.', '.', 'B', '.' },
        { '.','.', 'Y', '.', '.', '.', '.', '.', '.', 'B' },
        { '.','Y', '.', '.', '.', '.', '.', '.', '.', '.' },
        { 'Y','.', '.', '.', '.', '.', '.', '.', '.', '.' },
    };
​
    print2d(image);
​
    fillPaint(image, 'G', make_pair(4, 9));
​
    print2d(image);
​
    image = {
        { 'B','.', '.', '.', '.', '.', '.', '.', '.', '.' },
        { '.','B', '.', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', '.', '.' },
        { '.','.', 'B', '.', '.', '.', '.', '.', 'Y', 'Y' },
        { '.','.', 'B', '.', '.', '.', '.', 'Y', '.', '.' },
        { '.','.', '.', 'B', '.', '.', 'Y', '.', '.', '.' },
        { '.','.', '.', '.', 'B', 'Y', '.', '.', '.', '.' },
        { '.','.', '.', '.', 'Y', 'B', '.', '.', '.', '.' },
        { '.','.', '.', '.', 'Y', '.', 'B', '.', '.', '.' },
        { '.','.', '.', '.', 'Y', '.', '.', 'B', '.', '.' },
        { '.','.', '.', 'Y', '.', '.', '.', '.', 'B', '.' },
        { '.','.', 'Y', '.', '.', '.', '.', '.', '.', 'B' },
        { '.','Y', '.', '.', '.', '.', '.', '.', '.', '.' },
        { 'Y','.', '.', '.', '.', '.', '.', '.', '.', '.' },
    };
​
    print2d(image);
​
    fillPaint(image, 'H', make_pair(10, 0));
​
    print2d(image);
​
}
Parens
Coins
Last modified 4yr ago