Problem: Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i-th row from the top and the j-th column is a "wall" square if S_{ij} is `#`, and a "road" square if S_{ij} is `.`.  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.

Submission attempts (in order):
def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    max_way = []
    for start_i in range(len(points) - 1):
        for goal_i in range(start_i + 1, len(points)):
            if points[start_i] in max_way or points[goal_i] in max_way:
                continue
            step, way = count_step(MAP, points[start_i], points[goal_i])
            if step > max_step:
                max_step = step
                max_way = way

    print(max_step)


MOVES = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def count_step(MAP, start, goal):
    candidates = [(start, get_distance(start, goal), 0, [start])]

    checked = {}
    while True:
        pos, _, step, way = candidates.pop(0)
        for m in MOVES:
            next_pos = (pos[0] + m[0], pos[1] + m[1])
            if next_pos in checked:
                continue
            if not is_valid(MAP, next_pos):
                continue
            checked[next_pos] = True
            new_way = list(way)
            new_way.append(next_pos)
            distance = get_distance(next_pos, goal)
            if distance == 0:
                return step + 1, new_way
            candidates.append((next_pos, distance, step + 1, new_way))
        candidates.sort(key=lambda x: x[1] + x[2])


def get_distance(p, goal):
    return abs(p[0] - goal[0]) + abs(p[1] - goal[1])


def is_valid(MAP, pos):
    if pos[0] < 0 or pos[1] < 0:
        return False
    if pos[0] >= len(MAP) or pos[1] >= len(MAP[0]):
        return False

    if MAP[pos[0]][pos[1]] == '#':
        return False
    return True


if __name__ == "__main__":
    main()


import copy

MOVEMENT = [(-1, 0), (1, 0), (0, -1), (0, 1)]


def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for point in points:
        # print(point)
        map = copy.deepcopy(MAP)
        step = search(map, point)
        max_step = max(step, max_step)
    print(max_step)


def search(map, point):
    map[point[0]][point[1]] = "0"

    currents = [point]
    new_points = []
    cost = 1
    while True:
        if len(currents) == 0:
            if len(new_points) == 0:
                # print_map(map)
                return get_max_cost(map)
            currents = new_points
            new_points = []
            cost += 1
        point = currents.pop(0)

        for m in MOVEMENT:
            next_point = (point[0] + m[0], point[1] + m[1])
            if is_valid(map, next_point):
                map[next_point[0]][next_point[1]] = str(cost)
                new_points.append(next_point)


def print_map(map):
    for row in map:
        print("".join(row))


def is_valid(map, point):
    if point[0] < 0 or point[1] < 0:
        return False
    if point[0] >= len(map) or point[1] >= len(map[0]):
        return False
    if map[point[0]][point[1]] == ".":
        return True
    return False


def get_max_cost(map):
    max_cost = 0
    for row in map:
        for col in row:
            if col == '.':
                return None
            elif col == '#':
                continue
            max_cost = max(max_cost, int(col))
    return max_cost


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Accepted