给定一个矩阵,每个元素表示该位置的颜色,填色原理为只渲染相邻的同色像素。输入n,输入n*n的颜色矩阵,输入染色坐标x,y,以及颜色c,输出填色的像素总数。 输入样例:4 1 4 3 1 2 2 2 3 2 4 2 2 3 2 3 4 3 4 3 输出:6 C++98代码
时间: 2024-03-18 15:40:57 浏览: 64
以下是C++98的代码实现:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 105;
int n, ans;
int mat[MAXN][MAXN];
bool vis[MAXN][MAXN];
// 判断是否越界或已经染色
bool check(int x, int y, int c) {
if (x < 1 || x > n || y < 1 || y > n || vis[x][y] || mat[x][y] != c)
return false;
return true;
}
// DFS染色
void dfs(int x, int y, int c) {
vis[x][y] = true;
ans++;
if (check(x-1, y, c)) dfs(x-1, y, c);
if (check(x+1, y, c)) dfs(x+1, y, c);
if (check(x, y-1, c)) dfs(x, y-1, c);
if (check(x, y+1, c)) dfs(x, y+1, c);
}
int main() {
memset(vis, false, sizeof(vis)); // 初始化vis数组
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> mat[i][j];
int x, y, c;
cin >> x >> y >> c;
dfs(x, y, mat[x][y]); // 从x,y位置开始染色,颜色为mat[x][y]
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (vis[i][j]) // 统计染过色的像素总数
ans++;
cout << ans << endl;
return 0;
}
```
思路解析:
这道题可以使用DFS求解。从给定的坐标x,y开始,对其上下左右四个方向进行搜索,如果相邻的像素颜色和该点颜色相同,则继续往下搜索。搜索时需要记录哪些像素已经染过色,以避免重复染色。
具体实现时,可以使用一个vis数组记录哪些像素已经染过色,ans变量记录染过色的像素总数。在DFS函数中,首先将当前像素染色,并将vis数组对应位置标记为已染色。然后继续对当前像素上下左右四个方向进行搜索,如果满足条件(即不越界、未染色、颜色相同),则递归搜索。最后再次遍历整个矩阵,统计染过色的像素总数即为答案。
阅读全文