Python3で解く AtCoder Beginner Contest 151 D - Maze Master

startとgoalを自分で決める迷路で最長の手数のstartとgoalはなにかっていう問題。久しぶりに迷路問題解いた。普通はスタートとゴールを設定するんだけど、ゴールまで設定するとTLEになるので、スタートだけ設定して、BFSでやって最大手数の場所を結果的にゴールとするところがポイント。

目次

概要

問題

• のマスに'.'と'#'がある。
• '.'だけ通ることができる。　　
• '#'は通ることができない。（スタートやゴールも設定できない。）
• マスの外側にも動けない。
• 自分で適当にスタートとゴールを設定する。
• その上で最短距離でゴールまでにかかる手数のうち最大になる様なスタートとゴールの設定の時の手数は？

---

解くときに考えた内容

• とりあえず適当にスタートとゴールを設定した時の最短手数をだす。
  • キューを使った幅優先。
  • 移動時にはみ出ない時に次の位置に行ける設定をする。
    if (0 <= y + i < h) and (0 <= x + j < w )辺り。
• あとはあり得るスタートを設定する。
  • スタートは'.'であるどこかにする。
  • ゴールも最初に設定して全探索するととなってしまう。
  • 適当なスタートで迷路を解いて、手数の最大値をだす。
    （これが一番遠いゴールということになる!!）
  • あり得るスタート全てで最も手数がかかったものが求める答えとなる。

---

コード

import sys
from collections import deque

h, w = map(int, input().split())
maze = [input() for i in range(h)]
# 行ったかどうかのフラグ
visited = [[-1]*w for j in range(h)]
start_yx = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            sy = i
            sx = j
            start_yx .append([sy, sx])
# 移動パターン
mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
for sy, sx in start_yx :
    visited = [[-1]*w for j in range(h)]
    q = deque([[sy, sx]])
    visited[sy][sx] = 0 
    while q:
        y, x = q.popleft()
        # 普通はここでif 条件で条件を満たしたら終了っていう感じにするが、今回は解かせ切って終了とする。
        ans = max(ans, visited[y][x])
        for i, j in mv:
            if (0 <= y + i < h) and (0 <= x + j < w):  
                ny = y+i
                nx = x+j
                if visited[ny][nx] != -1:
                    continue
                if maze[ny][nx] == '.':
                    visited[ny][nx] = visited[y][x] + 1 
                    q.append([ny, nx])
            else:
                continue
print(ans)

---