Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                   continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        if ans >= 1 and (abs(sh - gh) + abs(sw - gw) <= 1):
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                        else:
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                            visited = [[-1] * W for _ in range(H)]
                            step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                            ans = max(ans, step_cnt)
    print(ans - 1)


Fixed submission:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                   continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        if ans >= 1 and (abs(sh - gh) + abs(sw - gw) <= 1):
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                        else:
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                            visited = [[-1] * W for _ in range(H)]
                            step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                            ans = max(ans, step_cnt)
    print(ans - 1)


Fixed submission:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                   continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        if ans > 1 and (abs(sh - gh) + abs(sw - gw) <= 1):
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                        else:
                            vd[sh][sw][gh][gw] = 1
                            vd[gh][gw][sh][sw] = 1
                            visited = [[-1] * W for _ in range(H)]
                            step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                            ans = max(ans, step_cnt)
    print(ans - 1)


Fixed submission:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                   continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#" and vd[sh][sw][gh][gw] == 0 and vd[gh][gw][sh][sw] == 0 and not (gh == sh and gw == sw):
                        vd[sh][sw][gh][gw] = 1
                        vd[gh][gw][sh][sw] = 1
                        visited = [[-1] * W for _ in range(H)]
                        step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                        ans = max(ans, step_cnt)

    print(ans - 1)


Fixed submission:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                 visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#":
                        visited = [[-1] * W for _ in range(H)]
                        step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                        ans = max(ans, step_cnt)

    print(ans - 1)


Fixed submission:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw, gh, gw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    while stack:
        h, w = stack.popleft()
        # ゴールの条件
        if h == gh and w == gw:
            break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
               new_w < 0 or new_w >= W:
                continue
            elif maze[new_h][new_w] != "#" and \
                 visited[new_h][new_w] == -1:
                visited[new_h][new_w] = visited[h][w] + 1
                stack.append([new_h, new_w])
    
    return visited[gh][gw]

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    ans = 0
    for sh in range(H):
        for sw in range(W):
            for gh in range(H):
                for gw in range(W):
                    if maze[sh][sw] != "#" and maze[gh][gw] != "#":
                        visited = [[-1] * W for _ in range(H)]
                        step_cnt = bfs(maze, visited, sh, sw, gh, gw)
                        ans = max(ans, step_cnt)

    print(ans - 1)


Fixed submission:
from collections import deque
"""
-1 -> not visited
else -> step count
"""
def bfs(maze, visited, sh, sw):
    stack = deque([[sh, sw]])
    visited[sh][sw] = 1
    longest = 0
    while stack:
        h, w = stack.popleft()
        # # ゴールの条件
        # if h == gh and w == gw:
        #     break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or \
                new_w < 0 or new_w >= W:
                    continue
            elif maze[new_h][new_w] != "#" and \
                visited[new_h][new_w] == -1:
                    visited[new_h][new_w] = visited[h][w] + 1
                    longest = max(longest, visited[new_h][new_w])
                    stack.append([new_h, new_w])
    
    # return visited[gh][gw]
    return longest

if __name__ == "__main__":
    H, W = map(int, input().split())
    maze = [input() for _ in range(H)]

    vd = [[[[0 for _ in range(W)] for _ in range(H)] for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if maze[sh][sw] != "#": 
                visited = [[-1] * W for _ in range(H)]
                step_cnt = bfs(maze, visited, sh, sw)
                ans = max(ans, step_cnt)
    print(ans - 1)