ABC151 D - Maze Master
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time import datetime # 時々使う # import numpy as np # from decimal import Decimal, ROUND_HALF_UP # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def it(): return tuple(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) # MOD = 10 ** 9 + 7 MOD = 998244353 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") H, W = il() maze = [iss() for _ in range(H)] move = [[-1, 0], [1, 0], [0, -1], [0, 1]] ret = 0 for h in range(H): for w in range(W): if maze[h][w] == '#': continue visit = [[-1] * W for _ in range(H)] visit[h][w] = 0 que = queue.Queue() que.put((h, w)) while not que.empty(): nowh, noww = que.get() for hh, ww in move: nexth = nowh + hh nextw = noww + ww if 0 <= nexth < H and 0 <= nextw < W and maze[nexth][nextw] == '.' and visit[nexth][nextw] == -1: visit[nexth][nextw] = visit[nowh][noww] + 1 que.put((nexth, nextw)) for v in visit: ret = max(ret, *v) print(ret) if __name__ == '__main__': main()
考え方
あるマスをスタートとしたとき、そのマスから最も遠いマスをゴールと定めると最も移動回数が多くなります。
迷路の大きさは精々20マス×20マス程度のため、全てのマスに対して、
そのマスをスタートとしたとき、最も遠いマスの位置を求めます。
最も遠いマスまでの移動回数は様々な求め方がありますが、
上記の回答例では幅優先探索で求めました。
基本的な方針は、現在のマスから移動可能なマスの位置をキューにエンキューして、
移動可能なマス(キュー)が無くなるまで探索を続けます。
次のマスに到達するための移動回数は現在のマスに至るまでの移動回数 + 1回です。