[ABC334E] Christmas Color Grid 1 题解

题目传送门

一道 dfs 题。

先统计出绿连通块数量，然后对于每个红色方块统计涂成绿色方块后会变成多少个连通块。正常涂成绿色后应该会增加一个大小为 \(1\) 的绿连通块，但若是有不同的绿连通块与其相邻，答案又会减少 \(1\)。

Code

#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;
const long long MOD = 998244353;

using ll = long long;
using i128 = __int128;
using ld = long double;
using f128 = __float128;

namespace xvl_ { 
	#define SP(n, x) std :: setprecision(n) << std :: fixed << x
	#define REP(i, l, r) for (auto i = (l); i <= (r); i++)
	#define PER(i, r, l) for (auto i = (r); i >= (l); i--)
	#define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
	#define SZ(x) (x.size())
	#define fst first
	#define snd second
	template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
	template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
ll h, w, cnt, sum, ans;
ll dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}, id[1005][1005];
char c[1005][1005];
void dfs(int x, int y) {
    REP(i, 0, 3) {
        ll sx = dir[i][0] + x, sy = dir[i][1] + y;
        if (sx >= 1 and sy >= 1 and sx <= h and sy <= w and c[sx][sy] == '#' and !id[sx][sy]) {
			id[sx][sy] = cnt;
			dfs(sx, sy);
		}
    }
}
ll qpow(ll n, ll m, int p) { 
	ll res = 1;
	while (m) {
		if (m & 1) res = res % p * n % p;
		n = n % p * n % p;
		m >>= 1;
	}
	return res; 
}
int main() {
	// freopen("InName.in", "r", stdin);
	// freopen("OutName.out", "w", stdout);
	ios :: sync_with_stdio(0);
	cin.tie(nullptr);
	cin >> h >> w;
	REP(i, 1, h) { REP(j, 1, w) cin >> c[i][j]; }
	REP(i, 1, h) {
		REP(j, 1, w) {
			if (!id[i][j] and c[i][j] == '#') {
				cnt++;
				id[i][j] = cnt;
				dfs(i, j);
			}
		}
	}
	REP(i, 1, h) {
		REP(j, 1, w) {
			if (c[i][j] == '.') {
				sum++;
				set <int> S;
				REP(k, 0, 3) {
					ll sx = dir[k][0] + i, sy = dir[k][1] + j;
					if (sx >= 1 and sy >= 1 and sx <= h and sy <= w and c[sx][sy] == '#') S.insert(id[sx][sy]);
				}
				ans += cnt - S.size() + 1; // 原先的连通块数量 + 1 再减去相邻的不同的连通块
			}
		}
	}
	cout << ans % MOD * qpow(sum, MOD - 2, MOD) % MOD;
	return 0;
}