# 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.

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

}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/recursion_and_dynamic_programming/paint-fill.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.