$\gets$ 点个赞吧QWQ
AcWing 1923. 奶牛艺术
题目描述
一个关于奶牛的鲜为人知的事实是它们其实是红绿色盲,也就是说红色和绿色在它们看来完全一样。
这使得设计出对奶牛和人类都有巨大吸引力的艺术作品变得非常困难。
考虑一个正方形绘画,它用一个字符矩阵来描述,每个字符要么是 $R$(红色),要么是 $G$(绿色),要么是 $B$(蓝色)。
如果一幅画有许多可以彼此区分的彩色“区域”,那么它就很有趣。
如果两个字符直接相邻(东、西、南或北),并且在颜色上无法区分,则它们属于同一区域。
例如,下列图画:
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
在人看来有 $4$ 个区域($2$ 个红色区域,$1$ 个蓝色区域,$1$ 个绿色区域),而在牛看来只有 $3$ 个区域($2$ 个红绿区域,$1$ 个蓝色区域)。
给定一幅画作,请计算该画作在人和牛眼中的区域数量。
输入格式
第一行包含整数 $N$。
接下来 $N$ 行,每行包含一个长度为 $N$ 的字符串,用来描述画作。
输出格式
两个整数,分别表示人和牛眼中的区域数量。
数据范围
$1 \le N \le 100$
输入样例:
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
输出样例:
4 3
算法
(Flood Fill)
Flood Fill 算法的提高版, 可以先用 unordered_map 预处理出人眼和牛眼能看到颜色的权值(每个都除了牛的红色和绿色外互不相同就行了), 然后分别枚举两个答案, 统计不同联通块的次数, 只是判断条件改成是否同一权值就行了。
时间复杂度 $O(n^2)$
C++ 代码
// 运行时间: 45 ms
// 运行空间: 344 KB
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII; // 由于是坐标, 最好用pair存
char g[110][110];
int n;
bool st[110][110];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
void bfs(int sx, int sy, unordered_map<char, int> mp){ // 记得传入每个对应的哈希表
queue<PII> q;
q.push({sx, sy});
st[sx][sy] = true;
while (q.size()){
auto t = q.front();
q.pop();
for (int i = 0; i < 4; i ++ ){
int a = t.x + dx[i], b = t.y + dy[i];
if(a < 1 || a > n || b < 1 || b > n) continue;
if(st[a][b] || mp[g[t.x][t.y]] != mp[g[a][b]]) continue;
q.push({a, b});
st[a][b] = true;
}
}
}
int main(){
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> g[i] + 1;
unordered_map<char, int> c = {{'R', 1}, {'G', 1}, {'B', 2}};
// ^ ^ 必须相同
unordered_map<char, int> p = {{'R', 1}, {'G', 2}, {'B', 3}}; // 这两行的数字取几都行
int cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if(!st[i][j]){
cnt1 ++ ;
bfs(i, j, p);
}
memset(st, 0, sizeof st); // 枚举完人眼后, 记得memset
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if(!st[i][j]){
cnt2 ++ ;
bfs(i, j, c);
}
cout << cnt1 << " " << cnt2 << "\n";
}