[ABC334E] Christmas Color Grid 1

洛谷题目链接

Atcoder题目链接

分析

发现将每个红色连通块涂成绿色连通块后，绿色连通块个数会加一，但是如果这个连通块之前已经跟绿色连通块相邻，则连通块数量减一。

代码

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1005, mod = 998244353;
int n, m, cnt, ans, tot, vis[N][N];
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
char c[N][N];

void dfs(int x, int y, int d){
	if(c[x][y] != '#' || vis[x][y]){
		return ;
	}
	vis[x][y] = d;
	for(int i = 0; i < 4; i ++){
		int nx = x + dx[i], ny = y + dy[i];
		dfs(nx, ny, d);
	}
}
int qpow(int n, int m, int p){ 
	int res = 1;
	while(m){
		if(m & 1){
			res = res % p * n % p;
		}
		n = n % p * n % p;
		m >>= 1;
	}
	return res; 
}

signed main(){
	cin >> n >> m;
	for(int i = 0; i <= n + 1; i ++){
		for(int j = 0; j <= m + 1; j ++){
			c[i][j] = '6';
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			cin >> c[i][j];
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(c[i][j] == '#' && !vis[i][j]){
				cnt ++;
				dfs(i, j, cnt);
			}
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(c[i][j] == '.'){
				tot ++;
				map <int, bool> mp;
				for(int k = 0; k < 4; k ++){
					int nx = i + dx[k], ny = j + dy[k];
					if(c[nx][ny] == '#'){
						mp[vis[nx][ny]] = true;
					}
				}
				ans += cnt - mp.size() + 1;
				ans %= mod;
			}
		}
	}
	cout << ans * qpow(tot, mod - 2, mod) % mod;
	return 0;
}