ABC151 D - Maze Master

問題原文

atcoder.jp

問題要旨

. と # からなる迷路が与えられる。（# は通れない） スタートとゴールを好きに選ぶことで、移動距離を最大化せよ。ただし、スタートからゴールへは最短距離で移動する。

• 
• 迷路は必ず . を２つ以上含む
• 任意の道のマスから任意の道のマスまで必ず移動できる

解法

全てのありうる始点から、ありうるすべてのゴールについて、BFSで最短経路長を計算し、その最大値が答えになります。
考察というよりは、実装できますか？という問題っぽい。
計算量は、ありうる始点が 通りで、 各BFSのとりうる状態数が 通りなので、 になります。
制約がとても小さいので余裕で間に合います。

実装

通れないマスについて探索をしないように注意。
あとは基本のBFSです。

from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
 
ans = 0
for sh in range(H):
    for sw in range(W):
        # 通れないマスはスタートになり得ない
        if G[sh][sw] == '#':
            continue
 
        # BFS
        dist = [[-1] * W for i in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])
 
        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                # 迷路からはみ出す
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
 
                # 移動先が通れないマス
                if G[nh + dh][nw + dw] == '#':
                    continue
 
                # 探索済み
                if dist[nh + dh][nw + dw] != -1:
                    continue
 
                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])
 
        ans = max(ans, max([max(d) for d in dist]))
 
print(ans)

感想

ABCっぽい教育的な問題だ。。。！