結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー hotcoffee
提出日時 2026-07-21 13:54:24
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 118 ms / 2,000 ms
+ 482µs
コード長 980 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 498 ms
コンパイル使用メモリ 21,408 KB
実行使用メモリ 15,872 KB
最終ジャッジ日時 2026-07-21 13:54:34
合計ジャッジ時間 9,882 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def dfs(v):
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[u] = v
            return True
    return False

N, M = map(int, input().split())
S = [input() for _ in range(N)]
X = (N * M + 1) // 2
Y = N * M // 2
G = [[] for _ in range(X)]
W, B = 0, 0
for n in range(N):
    for m in range(M):
        if S[n][m] == 'b':
            B += 1
        elif S[n][m] == 'w':
            W += 1
        else:
            continue
        if (n + m) % 2: continue
        x = (n * M + m) // 2
        for dn, dm in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            n2 = n + dn
            m2 = m + dm
            if 0 <= n2 < N and 0 <= m2 < M and S[n2][m2] != '.':
                y = (n2 * M + m2) // 2
                G[x].append(y)

meth3 = 0
match = [-1] * Y
for v in range(X):
    used = [0] * X
    if dfs(v):
        meth3 += 1
meth2 = min(W, B) - meth3
meth1 = abs(W - B)
print(meth1 + meth2 * 10 + meth3 * 100)
0