AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。
出典：
AtCoder Beginner Contest 151 D – Maze Master
制約が小さいので、\(O(N^4)\)で全探索を頑張る。
# AtCoder Beginner Contest 151 D - Maze Master
# https://atcoder.jp/contests/abc151/tasks/abc151_d
# tag: グリッド 再長距離 BFS 高橋君 青木君
# どこからスタートするのかについて、全探索する。
# 一回一回の各最長距離については、BFS で取得すればいい。
from collections import deque
def main():
H, W = map(int, input().split())
field = [input() for _ in range(H)]
# BFS で距離を算出し、最大のものを返す関数を作っておく
def get_longest(sx, sy):
moves = ((-1, 0), (1, 0), (0, -1), (0, 1))
dist = [[-1] * W for _ in range(H)]
dist[sy][sx] = 0
queue = deque([(sx, sy)])
while queue:
now_x, now_y = queue.popleft()
for dx, dy in moves:
nxt_x, nxt_y = now_x + dx, now_y + dy
if not(0 <= nxt_x < W and 0 <= nxt_y < H):
continue
if dist[nxt_y][nxt_x] == -1 and field[nxt_y][nxt_x] == '.':
dist[nxt_y][nxt_x] = dist[now_y][now_x] + 1
queue.append((nxt_x, nxt_y))
return max(v for row in dist for v in row)
result = 0
# スタート地点を全て試す
for x in range(W):
for y in range(H):
if field[y][x] == '#':
continue
tmp_r = get_longest(x, y)
if tmp_r > result:
result = tmp_r
print(result)
main()
関連
