Problem p02803 (python)

Fixed submission:
from collections import deque

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(list(input()))


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x, y = current_node
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < W:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        solution = bfs((i, j))
        if ans < solution:
            ans = solution

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(list(input()))


def bfs(initial):
    # goal判定はなく、一番遠いところで返す
    distance = [[-1] * W for _ in range(H)]
    frontier = deque()
    frontier.append(initial) 
    while len(frontier):
        locations = []
        current_node = frontier.popleft()
        current_state = current_node[0]
        x, y = current_state
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_x, new_y = x + i, y + j
            if 0 <= new_x < H and 0 <= new_y < H:
                if maze[new_x][new_y] == '.' and maze[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]


ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == '#':
            continue
        solution = bfs((x, y))
        if ans < solution:
            ans = solution

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

H, W = map(int, input().split())
maze = []
for _ in range(H):
    maze.append(list(input()))


def successors(x, y):
    locations = []
    # 下に行けるかの判定
    if (x + 1 < H) and (maze[x + 1][y] != '#'):
        locations.append((x + 1, y))
    # 上に行けるかの判定
    if (x - 1 >= 0) and (maze[x - 1][y] != '#'):
        locations.append((x - 1, y))
    # 右に行けるかの判定
    if (y + 1 < W) and (maze[x][y + 1] != '#'):
        locations.append((x, y + 1))
    # 左に行けるかの判定
    if (y - 1 >= 0) and (maze[x][y - 1] != '#'):
        locations.append((x, y - 1))
    return locations


def bfs(initial, goal, successors):
    frontier = deque()
    frontier.append((initial, None))
    # tuple
    explored = {initial}

    while len(frontier):
        current_node = frontier.popleft()
        current_state = current_node[0]
        if current_state == goal:
            return current_node
        for child in successors(*current_state):
            if str(child) in [str(i) for i in explored]:
                continue
            explored.add(child)
            frontier.append((child, current_node))
    return None


def node_to_path_count(node):
    path = [node[0]]
    counter: int = 0
    while node[1] is not None:
        counter += 1
        node = node[1]
        path.append(node[0])
    path.reverse()
    #return path, counter
    return counter


ans = 0
for x in range(H):
    for y in range(W):
        for gx in range(H):
            for gy in range(W):
                if (x != gx and y != gy) and maze[x][y] == '.' and maze[gx][gy] == '.':
                    solution = bfs((x, y), (gx, gy), successors)
                    counter = node_to_path_count(solution)
                    if ans < counter:
                        ans = counter

print(ans)