给定一个矩阵,每个元素表示该位置的颜色,填色原理只为渲染相邻的同色像素。输入n,输入n*n的颜色矩阵,输入染色坐标x,y以及颜色c,输出填色的像素总数。C++
时间: 2024-03-04 07:49:25 浏览: 75
C++实现求矩阵各行元素之和(含原理和步骤)
下面是一个可能的解法:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int fill(vector<vector<int>>& matrix, int x, int y, int c) {
int n = matrix.size();
int m = matrix[0].size();
int color = matrix[x][y];
int count = 0;
vector<vector<bool>> visited(n, vector<bool>(m, false));
vector<pair<int, int>> neighbors = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
// DFS
vector<pair<int, int>> stack = {{x, y}};
while (!stack.empty()) {
auto [i, j] = stack.back();
stack.pop_back();
if (visited[i][j]) continue;
visited[i][j] = true;
if (matrix[i][j] == color) {
matrix[i][j] = c;
count++;
for (auto [di, dj] : neighbors) {
int ni = i + di;
int nj = j + dj;
if (ni >= 0 && ni < n && nj >= 0 && nj < m && !visited[ni][nj]) {
stack.push_back({ni, nj});
}
}
}
}
return count;
}
int main() {
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
int x, y, c;
cin >> x >> y >> c;
int count = fill(matrix, x, y, c);
cout << count << endl;
return 0;
}
```
这个解法使用了深度优先搜索(DFS)来填色。我们首先记录下目标点的颜色,然后从目标点开始做 DFS,遍历与它相邻的同色像素,并将它们染色。为了避免重复访问同一个像素,我们使用一个二维布尔数组 `visited` 来记录已经访问过的像素。我们还使用一个栈 `stack` 来存储待访问的像素坐标。最后返回填色像素的总数。
阅读全文