結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー ああ
提出日時 2026-03-30 21:40:03
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 1,367 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 291 ms
コンパイル使用メモリ 84,864 KB
実行使用メモリ 84,852 KB
最終ジャッジ日時 2026-03-30 21:40:31
合計ジャッジ時間 7,920 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

def max_flow(s,t):
  def bb(n,g,w):
    if n==g:
      return w
    v[n]=0
    while a[n]<len(flow[n]):
      to,fl,edge=flow[n][a[n]]
      if fl and dist[to]==dist[n]+1 and v[to]:
        f=bb(to,g,min(w,fl))
        if f:
          flow[n][a[n]][1]-=f
          flow[to][edge][1]+=f
          return f
      a[n]+=1
    return 0
  res=0;m=len(flow);INF=1<<60
  while 1:
    dist=[INF]*m;dist[s]=0;f=deque([s])
    while f:
      q=f.popleft()
      for to,fl,edge in flow[q]:
        if fl and dist[to]==INF:
          dist[to]=dist[q]+1
          f.append(to)
    if dist[t]==INF:
      break
    a=[0]*m
    while 1:
      v=[1]*m
      f=bb(s,t,INF)
      if f:
        res+=f
      else:
        break
    if not res:
      break
  return res

def aa(a,b,fl):
  q,w=len(flow[a]),len(flow[b])
  flow[a].append([b,fl,w])
  flow[b].append([a,0,q])

n,m=map(int,input().split())
flow=[[] for i in range(n*m+2)]
s=[list(input()) for i in range(n)]
ans=0
a,b=0,0
for i in range(n):
  for j in range(m):
    c=i*m+j+1
    if s[i][j]=="b":
      a+=1
      aa(0,c,1)
      for l in range(n):
        for k in range(m):
          
          if s[l][k]=="w" and abs(i-l)+abs(j-k)==1:
            aa(c,l*m+k+1,1)
    if s[i][j]=="w":
      b+=1
      aa(c,n*m+1,1)
ans=max_flow(0,n*m+1)
c=min(a,b)-ans
d=max(a,b)-ans-c
print(ans*100+c*10+d)
0