結果
問題 | No.2731 Two Colors |
ユーザー |
|
提出日時 | 2024-04-20 08:21:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,316 ms / 3,000 ms |
コード長 | 1,162 bytes |
コンパイル時間 | 461 ms |
コンパイル使用メモリ | 81,936 KB |
実行使用メモリ | 113,012 KB |
最終ジャッジ日時 | 2024-10-12 03:44:15 |
合計ジャッジ時間 | 17,576 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import typingimport sysfrom collections import defaultdictimport heapqinput = lambda: sys.stdin.readline().strip()inf = 10**18mod = 998244353# import pypyjit# pypyjit.set_param('max_unroll_recursion=-1')# sys.setrecursionlimit(10**6)def solve():H, W = map(int, input().split())def enc(h, w):return h*W + wdef dec(x):return x//W, x%Wgrid = []for _ in range(H):grid.append(list(map(int, input().split())))color = [[-1]*W for _ in range(H)]q = [[(grid[-1][-1], enc(H-1, W-1))], [(grid[0][0], enc(0, 0))]]cnt = -2while True:while True:_, x = heapq.heappop(q[(cnt-1)%2])h, w = dec(x)if color[h][w] == -1:breakcnt += 1color[h][w] = cnt%2# 隣あっているマスに異なるいろがあったら終わりfor dh, dw in zip([1, 0, -1, 0], [0, 1, 0, -1]):if 0 <= dh + h <= H-1 and 0 <= dw + w <= W-1:if color[dh + h][dw + w]==-1:heapq.heappush(q[cnt%2], (grid[dh+h][dw+w], enc(dh+h, dw+w)))if color[dh + h][dw + w]==(cnt-1)%2:print(cnt)returndef main():t = 1for _ in range(t):solve()main()