BFSの練習がてら解いてみました。
DFS、BFSの練習にはちょうどいい問題だと思います。
問題へのリンク ABC 151 D - Maze Master
やること
最大の移動距離を求めたい。
すべての頂点を始点としてBFSなりで、各頂点への移動距離を求める。
そこから最大となるものを探す。
壁からはスタートできないところに少し注意が必要。
回答
from collections import deque
import numpy as np
H,W = map(int,input().split())
maze = [input() for _ in range(H)]
ans = 0
for x in range(H):
for y in range(W):
#壁からはスタートできない
if maze[x][y] == "#":
continue
#初期化
distance = [[0]*W for _ in range(H)]
#start位置
stack = deque([[x,y]])
while stack:
h,w = stack.popleft()
for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
new_h, new_w = h+i, w+j
if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
continue
elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
distance[new_h][new_w] = distance[h][w]+1
stack.append([new_h, new_w])
#start位置は0で初期化
distance[x][y] = 0
ans = max(ans, np.max(distance))
print(ans)
ポイント
ある点から上下左右すべてを調べます。
for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
new_h, new_w = h+i, w+j
調べる点が「#」壁でなく、まだ探索していなければ探索します。
ひとつ前の点から距離を1足してあげて、スタックに追加することで次の探索に移れます。
elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
distance[new_h][new_w] = distance[h][w]+1
stack.append([new_h, new_w])
2次元配列の最大値は、numpyのmaxを使うと簡単にとることができます。
ans = max(ans, np.max(distance))
探索結果の出力
各頂点からの探索終了後に下記コードを追加することで、探索結果を出力しました。
for i in range(H):
print(distance[i])
print()
入力
3 5
...#.
.#.#.
.#...
出力
きれいに各頂点からの移動距離が探索できていることがわかります。
[0, 1, 2, 0, 8]
[1, 0, 3, 0, 7]
[2, 0, 4, 5, 6]
[1, 0, 1, 0, 7]
[2, 0, 2, 0, 6]
[3, 0, 3, 4, 5]
[2, 1, 0, 0, 6]
[3, 0, 1, 0, 5]
[4, 0, 2, 3, 4]
[8, 7, 6, 0, 0]
[9, 0, 5, 0, 1]
[10, 0, 4, 3, 2]
[1, 2, 3, 0, 9]
[0, 0, 4, 0, 8]
[1, 0, 5, 6, 7]
[3, 2, 1, 0, 5]
[4, 0, 0, 0, 4]
[5, 0, 1, 2, 3]
[7, 6, 5, 0, 1]
[8, 0, 4, 0, 0]
[9, 0, 3, 2, 1]
[2, 3, 4, 0, 10]
[1, 0, 5, 0, 9]
[0, 0, 6, 7, 8]
[4, 3, 2, 0, 4]
[5, 0, 1, 0, 3]
[6, 0, 0, 1, 2]
[5, 4, 3, 0, 3]
[6, 0, 2, 0, 2]
[7, 0, 1, 0, 1]
[6, 5, 4, 0, 2]
[7, 0, 3, 0, 1]
[8, 0, 2, 1, 0]