結果
問題 |
No.2855 Move on Grid
|
ユーザー |
![]() |
提出日時 | 2024-08-25 14:03:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 925 ms / 3,000 ms |
コード長 | 1,062 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,792 KB |
実行使用メモリ | 197,656 KB |
最終ジャッジ日時 | 2024-08-25 14:04:22 |
合計ジャッジ時間 | 26,258 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
from collections import deque N,M,K=map(int,input().split()) A=[] for _ in range(N): A.append(list(map(int,input().split()))) def nibun(f): left,right=0,10**9+1 while right-left>1: mid=(right+left)//2 if f(mid): left=mid else: right=mid return left def isok(n): if bfs((0,0),n)<=K: return True return False def bfs(s,n): dq=deque() high=[[10**9 for _ in range(M)] for _ in range(N)] if A[0][0]<n: high[s[0]][s[1]]=1 dq.append([s[0],s[1],1]) else: high[s[0]][s[1]]=0 dq.append([s[0],s[1],0]) while len(dq)!=0: i,j,h=dq.popleft() for d1,d2 in [[1,0],[-1,0],[0,1],[0,-1]]: x=i+d1 y=j+d2 if 0<=x<N and 0<=y<M and high[x][y]==10**9: if A[x][y]<n: dq.append([x,y,h+1]) high[x][y]=h+1 else: dq.appendleft([x,y,h]) high[x][y]=h return high[-1][-1] print(nibun(isok))