結果
問題 | No.157 2つの空洞 |
ユーザー | roaris |
提出日時 | 2019-08-04 13:48:30 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 92 ms |
コンパイル使用メモリ | 10,936 KB |
実行使用メモリ | 8,792 KB |
最終ジャッジ日時 | 2023-09-22 10:49:08 |
合計ジャッジ時間 | 1,647 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 19 ms
8,708 KB |
testcase_01 | AC | 18 ms
8,680 KB |
testcase_02 | AC | 18 ms
8,636 KB |
testcase_03 | AC | 19 ms
8,740 KB |
testcase_04 | AC | 19 ms
8,632 KB |
testcase_05 | AC | 19 ms
8,596 KB |
testcase_06 | AC | 20 ms
8,700 KB |
testcase_07 | AC | 19 ms
8,612 KB |
testcase_08 | AC | 20 ms
8,792 KB |
testcase_09 | AC | 20 ms
8,756 KB |
testcase_10 | AC | 19 ms
8,628 KB |
testcase_11 | AC | 19 ms
8,632 KB |
testcase_12 | AC | 20 ms
8,704 KB |
testcase_13 | AC | 20 ms
8,608 KB |
testcase_14 | AC | 20 ms
8,684 KB |
testcase_15 | AC | 21 ms
8,624 KB |
testcase_16 | AC | 20 ms
8,696 KB |
testcase_17 | AC | 20 ms
8,656 KB |
testcase_18 | AC | 19 ms
8,648 KB |
testcase_19 | AC | 20 ms
8,708 KB |
ソースコード
from collections import deque def bfs(sx, sy): queue = deque([]) queue.append((sx, sy)) visited = [[-1 for _ in range(W)] for _ in range(H)] visited[sx][sy] = 1 while len(queue) > 0: current_x, current_y = queue.popleft() for next_x, next_y in [(current_x-1, current_y), (current_x+1, current_y), (current_x, current_y-1), (current_x, current_y+1)]: if 0 <= next_x < H and 0 <= next_y < W: if C[next_x][next_y] == '.' and visited[next_x][next_y] == -1: visited[next_x][next_y] = 1 queue.append((next_x, next_y)) return visited W, H = map(int, input().split()) C = [input() for _ in range(H)] for i in range(H): for j in range(W): if C[i][j] == '.': amx, amy = i, j break visitedA = bfs(amx, amy) holeA = [] for i in range(H): for j in range(W): if visitedA[i][j] == 1: holeA.append((i, j)) for i in range(H): for j in range(W): if C[i][j] == '.' and visitedA[i][j] == -1: bmx, bmy = i, j break visitedB = bfs(bmx, bmy) holeB = [] for i in range(H): for j in range(W): if visitedB[i][j] == 1: holeB.append((i, j)) ans = 10 ** 18 for Ax, Ay in holeA: for Bx, By in holeB: ans = min(ans, abs(Ax-Bx) + abs(Ay-By) - 1) print(ans)