結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-04-19 22:13:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,634 ms / 3,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 654 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 129,064 KB |
最終ジャッジ日時 | 2024-10-11 15:35:04 |
合計ジャッジ時間 | 19,674 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import sysinput = sys.stdin.readlinefrom heapq import heappop,heappush,heapifyH,W=map(int,input().split())A=[list(map(int,input().split())) for i in range(H)]Q1=[]Q2=[]USE=[[0]*W for i in range(H)]USE2=[[0]*W for i in range(H)]USE3=[[0]*W for i in range(H)]USE4=[[0]*W for i in range(H)]Q1.append((A[0][1],0,1))Q1.append((A[1][0],1,0))Q2.append((A[H-1][W-2],H-1,W-2))Q2.append((A[H-2][W-1],H-2,W-1))heapify(Q1)heapify(Q2)USE[0][0]=1USE2[H-1][W-1]=1flag=0for tt in range(10**9):if flag==1:breakif tt%2==0:while True:_,x,y=heappop(Q1)if USE[x][y]==1:continueUSE[x][y]=1breakfor z,w in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:if 0<=z<H and 0<=w<W:if USE3[z][w]==0:heappush(Q1,(A[z][w],z,w))USE3[z][w]=1if USE2[z][w]==1:flag=1else:while True:_,x,y=heappop(Q2)if USE2[x][y]==1:continueUSE2[x][y]=1breakfor z,w in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:if 0<=z<H and 0<=w<W:if USE4[z][w]==0:heappush(Q2,(A[z][w],z,w))USE4[z][w]=1if USE[z][w]==1:flag=1print(tt)