結果

問題 No.421 しろくろチョコレート
ユーザー ntuda
提出日時 2025-03-21 19:08:01
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,846 bytes
コンパイル時間 461 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 80,916 KB
最終ジャッジ日時 2025-03-21 19:08:08
合計ジャッジ時間 5,971 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23 WA * 40 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

N, M = map(int, input().split())
S = [input() for _ in range(N)]
NM = N * M
E = [[] for _ in range(NM)]
D = [0] * NM
F = [0] * NM
WB = [0, 0]
ans = 0
Q = []

nv = [1] * NM
for i in range(N):
    for j in range(M):
        ij = i * M + j
        if S[i][j] == ".":
            nv[ij] = 0
            continue
        if i < N - 1 and S[i + 1][j] != ".":
            ij2 = (i + 1) * M + j
            D[ij] += 1
            D[ij2] += 1
            E[ij].append(ij2)
            E[ij2].append(ij)
        if j < M - 1 and S[i][j + 1] != ".":
            ij2 = i * M + j + 1
            D[ij] += 1
            D[ij2] += 1
            E[ij].append(ij2)
            E[ij2].append(ij)
        if D[ij] == 0:
            nv[ij] = 0
            WB[ij % 2] += 1
        elif D[ij] == 1:
            nv[ij] = 0
            Q.append(ij)

ans = 0
while Q:
    x = Q.pop()
    cnt = 0
    for y in E[x]:
        if nv[y]:
            D[y] -= 1
            if F[x] == 0:
                nv[y] = 0
                F[x] = 1
                F[y] = 1
                ans += 100
                Q.append(y)
            elif D[y] == 1:
                nv[y] = 0
                Q.append(y)
        else:
            if F[x] == 0:
                if F[y] == 0:
                    F[x] = 1
                    F[y] = 1
                    ans += 100
    if F[x] == 0:
        WB[x % 2] += 1

    #print(x, nv, D, F, ans, Q)


def dfs(x):
    for y in E[x]:
        if nv[y]:
            nv[y] = 0
            WB2[y % 2] += 1
            dfs(y)


for i in range(NM):
    if nv[i]:
        nv[i] = 0
        WB2 = [0, 0]
        WB2[i % 2] += 1
        dfs(i)
        a, b = WB2
        ans += 100 * min(a, b)
        if a > b:
            WB[0] += 1
        elif a < b:
            WB[1] += 1

a, b = WB
if a < b:
    a, b = b, a
ans += 10 * b
ans += a - b

print(ans)
0