問題概要
問題ページ
-
-
D - Maze Master
問題ページへ移動する
問題文
高橋君は、縦 \(H\) マス、横 \(W\) マスの \(H \times W\) マスからなる迷路を持っています。
上から \(i\) 行目、左から \(j\) 列目のマス \((i,j)\) は、 \(S_{ij}\) が # のとき壁であり、. のとき道です。
道のマスからは、上下左右に隣接する道のマスに移動することができます。
迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。
高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。
青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。
高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか？
制約
- \(1 \leq H,W \leq 20\)
- \(S_{ij}\) は
.か# - \(S\) は
.を \(2\) つ以上含む - 任意の道のマスから任意の道のマスまで \(0\) 回以上の移動で到達できる
問題の考察
ACコード
import sys
import collections
def solve():
input = sys.stdin.readline
mod = 10 ** 9 + 7
h, w = list(map(int, input().rstrip('\n').split()))
s = [[True if v == "." else False for v in str(input().rstrip('\n'))] for _ in range(h)]
mx = 0
for i in range(h):
for j in range(w):
if s[i][j]:
ql = [[0, i, j]]
ql = collections.deque(ql)
fq = collections.defaultdict(list)
fq[i, j]
while True:
if len(ql) != 0:
cost, xv, yv = ql.popleft()
mx = max(mx, cost)
for xv, yv in [[xv + 1, yv], [xv - 1, yv], [xv, yv + 1], [xv, yv - 1]]:
if 0 <= xv < h and 0 <= yv < w:
if (xv, yv) not in fq and s[xv][yv]:
ql.append([cost + 1, xv, yv])
fq[xv, yv]
else:
break
print(mx)
if __name__ == '__main__':
solve()