結果
問題 | No.157 2つの空洞 |
ユーザー | あかりき |
提出日時 | 2021-02-27 20:33:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 2,412 bytes |
コンパイル時間 | 132 ms |
コンパイル使用メモリ | 82,664 KB |
実行使用メモリ | 61,860 KB |
最終ジャッジ日時 | 2024-04-10 15:50:01 |
合計ジャッジ時間 | 1,652 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 36 ms
53,764 KB |
testcase_01 | AC | 34 ms
54,372 KB |
testcase_02 | AC | 35 ms
53,268 KB |
testcase_03 | AC | 34 ms
54,576 KB |
testcase_04 | AC | 34 ms
54,204 KB |
testcase_05 | AC | 35 ms
53,376 KB |
testcase_06 | AC | 35 ms
54,648 KB |
testcase_07 | AC | 34 ms
52,948 KB |
testcase_08 | AC | 35 ms
53,340 KB |
testcase_09 | AC | 35 ms
53,488 KB |
testcase_10 | AC | 35 ms
53,540 KB |
testcase_11 | AC | 34 ms
53,972 KB |
testcase_12 | AC | 37 ms
53,480 KB |
testcase_13 | AC | 40 ms
60,344 KB |
testcase_14 | AC | 41 ms
54,924 KB |
testcase_15 | AC | 37 ms
55,052 KB |
testcase_16 | AC | 41 ms
60,844 KB |
testcase_17 | AC | 42 ms
61,860 KB |
testcase_18 | AC | 42 ms
60,340 KB |
testcase_19 | AC | 42 ms
59,876 KB |
ソースコード
w,h=map(int,input().split()) l=[list(input()) for i in range(h)] n=h*w connection=[[] for i in range(h*w)] connection2=[[] for i in range(h*w)] for i in range(h): for j in range(w): if l[i][j]=='.': if i!=0: connection2[i*w+j].append((i-1)*w+j) if l[i-1][j]=='.': connection[i*w+j].append((i-1)*w+j) if i!=h-1: connection2[i*w+j].append((i+1)*w+j) if l[i+1][j]=='.': connection[i*w+j].append((i+1)*w+j) if j!=0: connection2[i*w+j].append(i*w+j-1) if l[i][j-1]=='.': connection[i*w+j].append(i*w+j-1) if j!=w-1: connection2[i*w+j].append(i*w+j+1) if l[i][j+1]=='.': connection[i*w+j].append(i*w+j+1) else: if i!=0: connection2[i*w+j].append((i-1)*w+j) if i!=h-1: connection2[i*w+j].append((i+1)*w+j) if j!=0: connection2[i*w+j].append(i*w+j-1) if j!=w-1: connection2[i*w+j].append(i*w+j+1) def bfs(v): distance=[-1]*n distance[v]=0 next=connection[v] next2=set() visited=[-1]*n visited[v]=1 visitct=1 ct=0 while len(next)!=0 and visitct!=n: ct+=1 for i in range(len(next)): if visited[next[i]]==-1: distance[next[i]]=ct visited[next[i]]=1 visitct+=1 for j in range(len(connection[next[i]])): if visited[connection[next[i]][j]]==-1: next2.add(connection[next[i]][j]) next=list(next2) next2=set() return distance def bfs2(l): distance=[-1]*n next=set() next2=set() visited=[-1]*n visitct=0 for i in range(len(l)): distance[l[i]]=0 for j in range(len(connection2[l[i]])): next.add(connection2[l[i]][j]) visited[l[i]]=1 visitct=+1 next=list(next) ct=0 while len(next)!=0 and visitct!=n: ct+=1 for i in range(len(next)): if visited[next[i]]==-1: distance[next[i]]=ct visited[next[i]]=1 visitct+=1 for j in range(len(connection2[next[i]])): if visited[connection2[next[i]][j]]==-1: next2.add(connection2[next[i]][j]) next=list(next2) next2=set() return distance for i in range(n): if l[i//w][i%w]=='.': x=i break L=bfs(x) L2=[] for i in range(n): if L[i]!=-1: L2.append(i) ans=[] L3=bfs2(L2) for i in range(n): if L[i]==-1 and l[i//w][i%w]=='.': ans.append(L3[i]-1) print(min(ans))