結果
問題 | No.2731 Two Colors |
ユーザー |
👑 ![]() |
提出日時 | 2024-04-19 23:25:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 880 ms / 3,000 ms |
コード長 | 1,603 bytes |
コンパイル時間 | 249 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 258,504 KB |
最終ジャッジ日時 | 2024-10-11 18:02:45 |
合計ジャッジ時間 | 17,877 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import heapqH,W = map(int,input().split())A = [ list(map(int,input().split())) for i in range(H) ]dic = {}lis = []for i in range(H):for j in range(W):lis.append( A[i][j] )lis.sort()for i in range(len(lis)):dic[lis[i]] = ifor i in range(H):for j in range(W):A[i][j] = dic[A[i][j]]rev = [0] * (H*W)for i in range(H):for j in range(W):rev[A[i][j]] = (i,j)color = [["#"] * W for i in range(H)]state = [[0] * W for i in range(H)]q0 = []q1 = []color[0][0] = 1q1.append( A[0][0] )color[H-1][W-1] = 0q0.append( A[H-1][W-1] )ans = -2for i in range(H*W+1):flag = Falseif i % 2 == 1:num = heapq.heappop(q0)x,y = rev[num]color[x][y] = 0for xx,yy in ( (x-1,y),(x+1,y),(x,y-1),(x,y+1) ):if not (0 <= xx < H and 0 <= yy < W):continueif state[xx][yy] & 1 == 0 and color[xx][yy] == "#":state[xx][yy] |= 1heapq.heappush( q0 , A[xx][yy])if color[xx][yy] == 1:flag = Trueelse:num = heapq.heappop(q1)x,y = rev[num]color[x][y] = 1for xx,yy in ( (x-1,y),(x+1,y),(x,y-1),(x,y+1) ):if not (0 <= xx < H and 0 <= yy < W):continueif state[xx][yy] & 2 == 0 and color[xx][yy] == "#":state[xx][yy] |= 2heapq.heappush( q1 , A[xx][yy])if color[xx][yy] == 0:flag = Trueans += 1#print (color)if flag:breakprint (ans)