やること

最大の移動距離を求めたい。
すべての頂点を始点として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]