一道 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;
}