結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-19 21:39:20 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,703 ms / 3,000 ms |
コード長 | 1,284 bytes |
コンパイル時間 | 565 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 275,688 KB |
最終ジャッジ日時 | 2024-10-11 14:25:52 |
合計ジャッジ時間 | 27,008 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import collections,sys,math,functools,operator,itertools,bisect,heapq,decimal,string,time,random#sys.setrecursionlimit(10**9)#sys.set_int_max_str_digits(0)#input = sys.stdin.readline#n = int(input())##alist = []#s = input()h,w = map(int,input().split())grid = [list(map(int,input().split())) for i in range(h)]color = [[],[]]s = [set(),set()]c = [[-1 for i in range(w)] for j in range(h)]c[0][0] = 0c[h-1][w-1] = 1heapq.heappush(color[0],(grid[0][1],0,1))heapq.heappush(color[0],(grid[1][0],1,0))s[0].add((0,1))s[0].add((1,0))s[0].add((0,0))heapq.heappush(color[1],(grid[h-2][w-1],h-2,w-1))heapq.heappush(color[1],(grid[h-1][w-2],h-1,w-2))s[1].add((h-2,w-1))s[1].add((h-1,w-2))s[1].add((h-1,w-1))ans = 0dxy = [[-1,0],[1,0],[0,1],[0,-1]]for i in range(h*w):v,x,y = heapq.heappop(color[i%2])while c[x][y] != -1:if not color[i%2]:print(ans)exit()v,x,y = heapq.heappop(color[i%2])c[x][y] = i%2ans += 1for dx,dy in dxy:if 0 <= x+dx < h and 0 <= y+dy < w:if c[x+dx][y+dy] == (i%2)^1:exit(print(ans))if (x+dx,y+dy) not in s[i%2]:s[i%2].add((x+dx,y+dy))heapq.heappush(color[i%2],(grid[x+dx][y+dy],x+dx,y+dy))