結果

問題 No.421 しろくろチョコレート
ユーザー ntuda
提出日時 2025-03-21 19:05:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,845 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 82,184 KB
実行使用メモリ 81,104 KB
最終ジャッジ日時 2025-03-21 19:06:09
合計ジャッジ時間 10,405 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 58 RE * 2 OLE * 1
権限があれば一括ダウンロードができます

ソースコード

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0