結果
問題 | No.2731 Two Colors |
ユーザー |
![]() |
提出日時 | 2024-03-14 17:03:33 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,636 bytes |
コンパイル時間 | 365 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 277,056 KB |
最終ジャッジ日時 | 2024-10-03 13:24:38 |
合計ジャッジ時間 | 11,471 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | WA * 30 TLE * 3 |
ソースコード
from heapq import *# 入力h,w = map(int,input().split())A = [list(map(int,input().split())) for _ in range(h)]# BFSで使うqueを用意queA = [(A[0][0], 0, 0)]heapify(queA)usedA = [[0 for j in range(w)]for i in range(h)]queB = [(A[-1][-1], h-1, w-1)]heapify(queB)usedB = [[0 for j in range(w)]for i in range(h)]# マス(i,j)と隣接している頂点リストを返すdef nextV(i,j):V = []# 上if((i == 0) == False):V.append((A[i-1][j], i-1, j))# 下if((i == h-1) == False):V.append((A[i+1][j], i+1, j))# 左if((j == 0) == False):V.append((A[i][j-1], i, j-1))# 右if((j == w-1) == False):V.append((A[i][j+1], i, j+1))return V# 色1を広げるdef f():v = heappop(queA)usedA[v[1]][v[2]] = 1# 色1と色0が隣接したら出力for nv in nextV(v[1], v[2]):if(usedB[nv[1]][nv[2]] == 1):print(i-1)exit()# 次の頂点をみるfor nv in nextV(v[1], v[2]):if(usedA[nv[1]][nv[2]] == 1):continueheappush(queA, nv)# 色0を広げるdef g():v = heappop(queB)usedB[v[1]][v[2]] = 1# 色1と色0が隣接したら出力for nv in nextV(v[1], v[2]):if(usedA[nv[1]][nv[2]] == 1):print(i-1)exit()# 次の頂点をみるfor nv in nextV(v[1], v[2]):if(usedB[nv[1]][nv[2]] == 1):continueheappush(queB, nv)# 愚直にシミュレーションfor i in range(h*w):if(i%2 == 0):f()elif(i%2 == 1):g()