Edit

【pythonでABC151を解説】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()

プログラミング

-Edit