E - Christmas Color Grid 1 https://atcoder.jp/contests/abc334/tasks/abc334_e

abc334_e.py

from collections import deque


def bfs(island_id, i, j):
    G[i][j] = island_id
    que = deque([(i, j)])
    while que:
        i, j = que.popleft()
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if ni < 0 or ni >= H or nj < 0 or nj >= W:
                continue
            if S[ni][nj] == ".":
                continue
            if G[ni][nj] > 0:
                continue
            G[ni][nj] = island_id
            que.append((ni, nj))
    return


MOD = 998244353
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
G = [[0] * W for _ in range(H)]
dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]

# いくつ島があるか数え、IDを振る
island_id = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#" and G[i][j] == 0:
            island_id += 1
            bfs(island_id, i, j)

# 各赤マスを緑に変えたときの島の数の合計を求める。
total = 0
red_cnt = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            red_cnt += 1
            s = set()
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= H or nj < 0 or nj >= W:
                    continue
                if G[ni][nj] > 0:
                    s.add(G[ni][nj])
            total += island_id - (len(s) - 1)

# 期待値の計算(MOD)
ans = total * pow(red_cnt, MOD - 2, MOD) % MOD
print(ans)