Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter

def init_maze(maze, H, W, start, goal):
    cost = np.zeros((H, W), dtype=int) + 999
    done = np.zeros((H, W), dtype=bool)
    barrier = np.zeros((H, W), dtype=bool)
    for i in range(H):
        for j in range(W):
            if (i, j) == start:
                # start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if (i, j) == goal:
                pass
                # goal = (i, j)
            if maze[i][j] == '#':
                barrier[i,j] = True
    return cost, done, barrier

def bnf(maze, cost, done, barrier, goal, g):
    for i in range(1, 999):
        done_next = maximum_filter(done, footprint=g) * ~done

        cost_next = minimum_filter(cost, footprint=g) * done_next
        cost_next[done_next] += 1

        cost[done_next] = cost_next[done_next]
        cost[barrier] = 999

        done[done_next] = done_next[done_next]
        done[barrier] = False

        if done[goal[0], goal[1]] == True:
            return max(cost_next[done_next])
            break
    return 0


if __name__ == '__main__':
    H, W = [ int(x) for x in stdin.readline().rstrip().split() ]
    maze = []
    for i in range(H):
        maze.append(stdin.readline().rstrip())

    index = []
    for i in range(H):
        for j in range(W):
            if maze[i][j] == '.':
                index.append((i, j))

    g = np.array([
        [0,1,0],
        [1,1,1],
        [0,1,0]
    ])

    costs = []
    for idx_start in index:
        start = idx_start
        for idx_goal in index:
            goal = idx_goal
            cost, done, barrier = init_maze(maze, H, W, start, goal)
            cost, done, barrier = init_maze(maze, H, W, start, goal)
            costs.append(bnf(maze, cost, done, barrier, goal, g))
    print(max(costs))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

from collections import deque

H, W = input_nums()
H += 2
W += 2
grid = '#' * W
for i in range(H - 2):
    grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
    INF = 10**9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (1, -1, W, -W):
            next_v = v + move
            if grid[next_v] == '#':
                continue
            d_next_v = dv + 1
            if d_next_v >= dist[next_v]:
                continue
            dist[next_v] = d_next_v
            q.append(next_v)
    return max([x for x in dist if x < INF])

ans = max([bfs(x) for x in range(H * W) if grid[x] != '#'])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter

def init_maze(maze, H, W, start, goal):
    cost = np.zeros((H, W), dtype=int) + 999
    done = np.zeros((H, W), dtype=bool)
    barrier = np.zeros((H, W), dtype=bool)
    for i in range(H):
        for j in range(W):
            if (i, j) == start:
                # start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if (i, j) == goal:
                pass
                # goal = (i, j)
            if maze[i][j] == '#':
                barrier[i,j] = True
    return cost, done, barrier

def bnf(maze, cost, done, barrier, goal, g):
    for i in range(1, 999):
        done_next = maximum_filter(done, footprint=g) * ~done

        cost_next = minimum_filter(cost, footprint=g) * done_next
        cost_next[done_next] += 1

        cost[done_next] = cost_next[done_next]
        cost[barrier] = 999

        done[done_next] = done_next[done_next]
        done[barrier] = False

        if done[goal[0], goal[1]] == True:
            return max(cost_next[done_next])
            break
    return 0


if __name__ == '__main__':
    H, W = [ int(x) for x in stdin.readline().rstrip().split() ]
    maze = []
    for i in range(H):
        maze.append(stdin.readline().rstrip())

    g = np.array([
        [0,1,0],
        [1,1,1],
        [0,1,0]
    ])

    start = (2, 0)
    goal = (0, 4)
    costs = []
    for i in range(H):
        for j in range(W):
            start = (i, j)
            for i_g in range(i, H):
                for j_g in range(j, W):
                    goal = (i_g, j_g)
                    cost, done, barrier = init_maze(maze, H, W, start, goal)
                    cost, done, barrier = init_maze(maze, H, W, start, goal)
                    costs.append(bnf(maze, cost, done, barrier, goal, g))
    print(max(costs))


Fixed submission:
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

from collections import deque

H, W = input_nums()
H += 2
W += 2
grid = '#' * W
for i in range(H - 2):
    grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
    INF = 10**9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (1, -1, W, -W):
            next_v = v + move
            if grid[next_v] == '#':
                continue
            d_next_v = dv + 1
            if d_next_v >= dist[next_v]:
                continue
            dist[next_v] = d_next_v
            q.append(next_v)
    return max([x for x in dist if x < INF])

ans = max([bfs(x) for x in range(H * W) if grid[x] != '#'])
print(ans)