結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 22:47:43 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,988 ms / 3,000 ms |
コード長 | 708 bytes |
コンパイル時間 | 218 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 191,672 KB |
最終ジャッジ日時 | 2024-10-11 16:40:12 |
合計ジャッジ時間 | 21,792 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
from heapq import*(h,w),*a=[[*map(int,s.split())]for s in open(0)]c=[[-1]*w for _ in range(h)]c[0][0]=1c[-1][-1]=0q=[[]for _ in range(2)]for i,j,k in[(1,0,1),(0,1,1),(h-2,w-1,0),(h-1,w-2,0)]:if 0<=i<h and 0<=j<w:q[k]+=(a[i][j],i,j),q[0].sort()q[1].sort()f=[[[0]*2 for _ in range(w)]for _ in range(h)]k=1while q[k]:p,i,j=heappop(q[k])if c[i][j]!=-1:continuec[i][j]=kng=0for di,dj in[(-1,0),(1,0),(0,1),(0,-1)]:ni,nj=i+di,j+djif 0<=ni<h and 0<=nj<w:if c[ni][nj]==k^1:ng=1if c[ni][nj]==-1 and f[ni][nj][k]<1:heappush(q[k],(a[ni][nj],ni,nj))f[ni][nj][k]=1if ng:breakk^=1print(sum(i!=-1for j in c for i in j)-2)