結果
問題 | No.157 2つの空洞 |
ユーザー |
![]() |
提出日時 | 2015-02-28 03:02:55 |
言語 | Python2 (2.7.18) |
結果 |
AC
|
実行時間 | 15 ms / 2,000 ms |
コード長 | 893 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 7,040 KB |
実行使用メモリ | 6,656 KB |
最終ジャッジ日時 | 2024-06-23 22:45:47 |
合計ジャッジ時間 | 1,277 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
from heapq import heappop,heappush W,H=map(int,raw_input().split()) C=[raw_input() for i in range(H)] arrived=[[False for i in range(W)] for j in range(H)] directions=[(1,0),(-1,0),(0,1),(0,-1)] for i in range(H): for j in range(W): if C[i][j] =='.': hp=[] heappush(hp,(0,i,j)) arrived[i][j]=True while len(hp)!=0: (d,a,b)=heappop(hp) if d > 0 and C[a][b] == '.': print d exit() for da,db in directions: na=a+da nb=b+db nd=d if na>=0 and nb >= 0 and na <H and nb <W and arrived[na][nb]==False: if C[na][nb]=='#': nd+=1 arrived[na][nb]=True heappush(hp,(nd,na,nb))