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);
}
Last modified 4yr ago