結果
問題 |
No.157 2つの空洞
|
ユーザー |
![]() |
提出日時 | 2022-12-21 12:48:32 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 43 ms / 2,000 ms |
コード長 | 991 bytes |
コンパイル時間 | 282 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-11-18 02:39:55 |
合計ジャッジ時間 | 1,859 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
from itertools import product def main(): w, h = map(int, input().split()) g = [list(input()) for _ in range(h)] def dfs(x, y): g[x][y] = '#' yield [x, y] dx = [1, 0, -1, 0, 1, -1, -1, 1] dy = [0, 1, 0, -1, 1, 1, -1, -1] for dx, dy in zip(dx[:4], dy[:4]): nx = x + dx ny = y + dy if not (0 <= nx < h and 0 <= ny < w): continue if g[nx][ny] == '.': yield from dfs(nx, ny) cave1, cave2 = [], [] is_first = True for i, j in product(range(h), range(w)): if g[i][j] == '.': if is_first: cave1 = list(dfs(i, j)) is_first = False else: cave2 = list(dfs(i, j)) break ans = 1 << 60 for x1, y1 in cave1: for x2, y2 in cave2: ans = min(ans, abs(x1 - x2) + abs(y1 - y2) - 1) print(ans) if __name__ == "__main__": main()