結果
問題 | No.157 2つの空洞 |
ユーザー | matsu7874 |
提出日時 | 2015-12-20 11:29:08 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,048 bytes |
コンパイル時間 | 122 ms |
コンパイル使用メモリ | 11,876 KB |
実行使用メモリ | 15,016 KB |
最終ジャッジ日時 | 2023-10-17 14:10:17 |
合計ジャッジ時間 | 8,723 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 35 ms
10,220 KB |
testcase_01 | AC | 40 ms
10,156 KB |
testcase_02 | AC | 58 ms
10,160 KB |
testcase_03 | AC | 98 ms
10,172 KB |
testcase_04 | AC | 175 ms
10,184 KB |
testcase_05 | AC | 337 ms
10,164 KB |
testcase_06 | AC | 1,281 ms
10,268 KB |
testcase_07 | AC | 83 ms
10,172 KB |
testcase_08 | AC | 65 ms
10,160 KB |
testcase_09 | AC | 347 ms
10,164 KB |
testcase_10 | AC | 92 ms
10,172 KB |
testcase_11 | TLE | - |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
ソースコード
W, H = map(int, input().split()) maze = [input() for i in range(H)] dist = [[W * H for j in range(W * H)] for j in range(W * H)] for y in range(H): for x in range(W): dist[y * W + x][y * W + x] = 0 for dy, dx in ((0, 1), (0, -1), (-1, 0), (1, 0)): if 0 <= y + dy < H and 0 <= x + dx < W: if maze[y + dy][x + dx] == '#': dist[y * W + x][(y + dy) * W + (x + dx)] = 1 else: dist[y * W + x][(y + dy) * W + (x + dx)] = 0 for k in range(W * H): for i in range(W * H): for j in range(W * H): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) min_cost = W * H for y in range(H): for x in range(W): if maze[y][x] == '#': continue for i in range(y, H): for j in range(W): if maze[i][j] == '#': continue if dist[y * W + x][i * W + j] > 0: min_cost = min(min_cost, dist[y * W + x][i * W + j]) print(min_cost)