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);

}