Windows Paint is really handy!
(At least it’s quite fast when handling PrintScreen…)
Everyone knows that there’s a drawing tool in Paint called the paint bucket tool.
You just need to choose the color you want and the location to paint, then you can start filling the area.
The range that the paint bucket tool fills depends on the “same-colored adjacent” principle.
Now, please simulate this tool.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| Each test case contains only one dataset.
The first line contains an integer N (1 <= N <= 100), which indicates that the size of the grid is N x N characters. The following N lines each contain N characters, representing the appearance of the grid. The grid consists only of two characters, “+” and “-”, representing two different colors. In the last line, there are two integers, i and j, representing the location clicked by the paint bucket, which corresponds to the cell in row (i + 1) and column (j + 1). For example, given the following 3 x 3 grid: 012 0 --- 1 -+- 2 -++ The coordinates (0, 2) would correspond to this position: 012 0 --* 1 -+- 2 -++ Assume that the selected color is “+”, and the original color at the selected position must be “-”. The paint will only spread to adjacent cells in the four directions: up, down, left, and right. | Please directly output the image after applying the paint bucket tool. |
| 7 -+++— -+–+– -+—+- –+++– —++– 3 4 | -+++— -++++– -+++++- –+++– —++– |
Thought Process
Use BFS, and you need to keep track of each point that has been visited. Once a point is visited, it cannot be visited again to avoid an infinite loop. Additionally, each time you move to a new point, you must change the current character at that position to “+”.
Sample Code－ZeroJudge D626: MS Paint
#include <iostream>
#include <vector>
using namespace std;
int N, walk[200][200] = {}, loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char draw[200][200] = {};
void BFS(const vector<pair<int, int>>start) {
if (start.size() == 0) return;
vector<pair<int, int>>newStart;
for (int i = 0; i<start.size(); i++) {
const int y = start[i].first, x = start[i].second;
walk[y][x]++;
draw[y][x] = '+';
for (int j = 0; j<4; j++) {
const int yy = y + loc[j][0], xx = x + loc[j][1];
if (yy >= 0 && yy < N && xx >= 0 && xx < N && draw[yy][xx] == '-' && walk[yy][xx] == 0) {
newStart.push_back(make_pair(yy, xx));
}
}
}
BFS(newStart);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i<N; i++) {
for (int j = 0; j<N; j++) {
cin >> draw[i][j];
walk[i][j] = 0;
}
}
vector<pair<int, int>>start;
int x, y;
cin >> x >> y;
start.push_back(make_pair(x, y));
BFS(start);
for (int i = 0; i<N; i++) {
for (int j = 0; j<N; j++) {
cout << draw[i][j];
}
cout << "\n";
}
}
//ZeroJudge D626
//Dr. SeanXD