結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-08-09 05:17:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,613 ms / 3,000 ms |
コード長 | 955 bytes |
コンパイル時間 | 373 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 135,276 KB |
最終ジャッジ日時 | 2024-08-09 05:17:59 |
合計ジャッジ時間 | 18,177 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import heapqH,W=map(int,input().split())A=[list(map(int,input().split())) for h in range(H)]color=[[None]*W for h in range(H)]queue=[[(A[0][1],0,1),(A[1][0],1,0)],[(A[H-1][W-2],H-1,W-2),(A[H-2][W-1],H-2,W-1)]]color[0][0]=0color[H-1][W-1]=1heapq.heapify(queue[0])heapq.heapify(queue[1])seen=[[[False]*W for h in range(H)] for c in range(2)]seen[0][0][1]=1seen[0][1][0]=1seen[1][H-1][W-2]=1seen[1][H-2][W-1]=1ans=0while True:c=ans%2a,h,w=heapq.heappop(queue[c])ans+=1color[h][w]=cskip=Falsefor dh,dw in ((0,1),(1,0),(0,-1),(-1,0)):if 0<=h+dh<H and 0<=w+dw<W:if color[h+dh][w+dw]==None:if seen[c][h+dh][w+dw]:continueheapq.heappush(queue[c],(A[h+dh][w+dw],h+dh,w+dw))seen[c][h+dh][w+dw]=Trueelse:if color[h+dh][w+dw]!=c:skip=Trueif skip:breakprint(ans)