Atcoder-abc334_e 题解

发表于2023-12-29更新于2023-12-29

题目传送门

一道 dfs 题……

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
}