Problem:


Score : 400 points

Problem Statement

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.

Constraints

1 \leq H,W \leq 20

S_{ij} is . or #.

S contains at least two occurrences of ..

Any road square can be reached from any road square in zero or more moves.

Input

Input is given from Standard Input in the following format:

H W
S_{11}...S_{1W}
:
S_{H1}...S_{HW}

Output

Print the maximum possible number of moves Aoki has to make.

Sample Input 1

3 3
...
...
...

Sample Output 1

4

If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.

Sample Input 2

3 5
...#.
.#.#.
.#...

Sample Output 2

10

If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []
for _ in range(h):
    maze.append(list(input()))

def clear_maze(sx, sy, gx, gy, maze):
    INF = float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    def bfs():
        queue = deque([(sx, sy)])
        distance[sx][sy] = 0
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.appendleft((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
        return distance[gx][gy]
    return bfs()


pairs = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            pairs.append([i, j])

MAX = 0
s = set()
for i in range(len(pairs)):
    sx, sy = pairs[i]
    for j in range(len(pairs)):
        gx, gy = pairs[j]
        if i == j or (sx, sy, gx, gy) in s or (gx, gy, sx, sy) in s:
            continue
        s.add((sx, sy, gx, gy))
        s.add((gx, gy, sx, sy))
        r = clear_maze(sx, sy, gx, gy, maze)
        if r == float('infinity'):
            continue
        MAX = max(MAX, r)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import deque

H, W = map(int, input().split())
S = [list(input().split()[0]) for _ in range(H)]

def bfs(S, H, W, start, goal):
    INF = 100000000
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        if (x, y) == goal:
            break
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '#' and distance[next_y][next_x] == INF:
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return distance[goal[1]][goal[0]]

ans = 0
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if (i, j) == (k, l) or S[i][j] == "#" or S[k][l] == "#":
                    continue
                start = (j, i)
                goal = (l, k)
                ans = max(ans, bfs(S, H, W, start, goal))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
H, W = map(int, input().split())
 
init_field = [list(input()) for _ in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
 
def bfs(x, y):
    distance = [[-1]*W for _ in range(H)]
    que = deque([])
    que.append((y, x))
    distance[y][x] = 0
    while que:
        y, x = que.popleft()
        if x == gx and y == gy:
            break
        for i, j in zip(dx, dy):
            nx = x + i
            ny = y + j
            if 0 <= nx < W and 0 <= ny < H and field[ny][nx] == "." and distance[ny][nx] == -1:
                distance[ny][nx] = distance[y][x] + 1
                que.append((ny, nx))
    return distance

ans = 0
for sy in range(H):
    for sx in range(W):
        if init_field[sy][sx] == '#':
            continue
        for gy in range(H):
            for gx in range(W):
                if init_field[gy][gx] == "#":
                    continue
                field = [[i for i in row] for row in init_field]
                if sx == gx and sy == gy:
                    continue
                d = bfs(sx, sy)
                ans = max(ans, d[gy][gx])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
field=[list(input())for i in range(h)]

import copy
dp=[[1000 for i in range(w)]for i in range(h)]
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j=="#":
            dp[y][x]=9999

dydx=[[-1,0],[1,0],[0,-1],[0,1]]

maxi=0
for y,i in enumerate(field):
    for x,j in enumerate(i):
        if j==".":
            ndp=copy.deepcopy(dp)
            ndp[y][x]=0
            cnt=0
            for _ in range(280):
                for y,i in enumerate(ndp):
                    for x,j in enumerate(i):
                        if j<1000:
                            for dy,dx in dydx:
                                ny,nx=y+dy,x+dx
                                if 0<=ny<=h-1 and 0<=nx<=w-1 and field[ny][nx]!="#" and ndp[ny][nx]>ndp[y][x]:
                                    ndp[ny][nx]=ndp[y][x]+1
                                    flag=False
                                    if ndp[ny][nx]>maxi:
                                        maxi=ndp[ny][nx]
print(maxi)

Submission status: Time Limit Exceeded

Solution code:
def bfs(maze,sx, sy,gx, gy):
    """maze内の S から G への最短距離を求める。たどり着けないと-1"""
    # for y, row in enumerate(maze):
    #     for x, col in enumerate(row):
    #         if col == 'S':
    #             sy, sx = y, x
    #         if col == 'G':
    #             gy, gx = y, x

    # 各地点までの最短距離の配列（壁以外を-1にする)
    d = [[-1 if col != '#' else col for col in row] for row in maze]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = [(sy, sx)]
    d[sy][sx] = 0

    # キューが空(たどり着かない)かゴールにたどり着くまでキューの先頭を処理
    while que and que[0] != (gy, gx):
        py, px = que.pop(0)
        # 4方向を処理
        for ny, nx in (py - 1, px), (py + 1, px), (py, px - 1), (py, px + 1):
            if 0 <= ny < len(d) and 0 <= nx < len(d[ny]) and d[ny][nx] == -1:
                # -1の場所には移動できるのでキューに追加、nはpの距離+1で確定
                que.append((ny, nx))
                d[ny][nx] = d[py][px] + 1

    return d[gy][gx]


def solve():
    maze = []
    h, w = map(int, input().split())
    for _ in range(h):
        maze.append(input())
        
    # maze = [
    #     # '#S######.#',
    #     # '.......#.#',
    #     # '.#.##.##.#',
    #     # '.#........',
    #     # '##.##.####',
    #     # '....#....#',
    #     # '.#######.#',
    #     # '....#.....',
    #     # '.####.###.',
    #     # '....#...G#',
        
    #     '...#.',
    #     '.#.#.',
    #     '.#...',
    # ]
    
    max = 0
    for sx in range(w):
        for sy in range(h):
            for gx in range(w):
                for gy in range(h):
                    ans = bfs(maze,sx, sy, gx, gy )
                    if ans != '#':
                        if int(ans) > max:
                            max = int(ans)
                        
    print(max)

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
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 start_i in range(len(points) - 1):
        for goal_i in range(start_i + 1, len(points)):
            max_step = max(max_step, count_step(MAP, points[start_i], points[goal_i]))

    print(max_step)


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

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


def move(pos, move):
    return pos[0] + move[0], pos[1] + move[1]


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()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    count = 0
    while queue:
        #ここでforループを回している
        for _ in range(len(queue)):
            coord = queue.popleft()
            visited[coord[0]][coord[1]] = 1
            if coord == [gy, gx]:
                return count
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                next_coord = [coord[0]+j, coord[1]+k]
                if next_coord[0] < 0 or next_coord[0] > H-1 or next_coord[1] < 0 or next_coord[1] > W-1:
                    continue
                if maze[next_coord[0]][next_coord[1]] == "." and \
                   visited[next_coord[0]][next_coord[1]] != 1:
                    queue.append(next_coord)
        count += 1

H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    # tmp = input()
    maze.append(tmp[:])
# print(*maze, sep="\n")
# exit()
ans = -1
for sx in range(H):
    for sy in range(W):
        for ex in range(H):
            for ey in range(W):
                if maze[sx][sy] == "#" or maze[ex][ey] == "#":
                    continue
                if sx == ex and sy == ey:
                    continue
                # maze[ex][ey] = "g"
                top = [-1]
                visited = [[-1 for _ in range(W)] for _ in range(H)]
                # dfs(sx, sy, 0)
                tmp = bfs(maze, visited, sx, sy, ex, ey)
                ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
# sx, sy = map(int, input().split())
# gx, gy = map(int, input().split())
# sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
c = [input() for i in range(H)]
INF = 10**9
def bfs():
    dist = [[INF for i in range(W)] for j in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    dist[sx][sy] = 0
    while q:
        p = q.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if c[nx][ny] != '#' and dist[nx][ny] == INF:
                    q.append([nx, ny])
                    dist[nx][ny] = dist[p[0]][p[1]] + 1
    return dist[gx][gy]

ans = -1
can = []
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                sx, sy = i, j
                gx, gy = k, l
                if c[sx][sy] == '#' or c[gx][gy] == '#':
                    continue
                can.append((sx, sy, gx, gy))

for sx, sy, gx, gy in can:
    if bfs() == INF:
        continue
    ans = max(ans, bfs())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# BFS queue
import queue
import copy

import time
sss = time.time()
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if ttt-sss >= 1.8:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import deque
def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    count = 0
    while queue:
        #ここでforループを回している
        for _ in range(len(queue)):
            coord = queue.popleft()
            visited[coord[0]][coord[1]] = 1
            if coord == [gy, gx]:
                return count
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                next_coord = [coord[0]+j, coord[1]+k]
                if next_coord[0] < 0 or next_coord[0] > H-1 or next_coord[1] < 0 or next_coord[1] > W-1:
                    continue
                if maze[next_coord[0]][next_coord[1]] == "." and \
                   visited[next_coord[0]][next_coord[1]] != 1:
                    queue.append(next_coord)
        count += 1


import sys
sys.setrecursionlimit(10**8)
H, W = map(int, input().split())
maze = []
for i in range(H):
    tmp = list(input())
    # tmp = input()
    maze.append(tmp[:])
# print(*maze, sep="\n")
# exit()
ans = -1
for sx in range(H):
    for sy in range(W):
        for ex in range(H):
            for ey in range(W):
                if maze[sx][sy] == "#" or maze[ex][ey] == "#":
                    continue
                if sx == ex and sy == ey:
                    continue
                # maze[ex][ey] = "g"
                top = [-1]
                visited = [[-1 for _ in range(W)] for _ in range(H)]
                # dfs(sx, sy, 0)
                tmp = bfs(maze, visited, sx, sy, ex, ey)
                ans = max(ans, tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
maze = []
pad = ' ' * (W+2)
maze.append(pad)
for i in range(H):
  m = input()
  maze.append(' ' + m + ' ')
maze.append(pad)
  
def bfs(maze, x,y, score):
    queue = [(x,y,0)]
    visited = {}
    while queue:
      x,y,s = queue.pop(0)
      if maze[x][y] != '.':
        continue
      visited[(x,y)] = s
      if (x+1,y) not in visited:
        queue.append((x+1,y,s+1))
      if (x-1,y) not in visited:
        queue.append((x-1,y,s+1))
      if (x,y+1) not in visited:
        queue.append((x,y+1,s+1))
      if (x,y-1) not in visited:
        queue.append((x,y-1,s+1))
    return max(visited.values())
  
ans = -1
for h in range(1,H+1):
  for w in range(1,W+1):
    now = maze[h][w]
    if now == '#':
      continue
    if maze[h-1][w] == maze[h+1][w] == maze[h][w-1] == maze[h][w+1] == '.':
      continue
    a = bfs(maze,h,w,0)
    if a > ans:
      ans = a
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]


    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
Min = []
miti = []
for i1 in range(n):
    for i2 in range(m):
        if maze[i1][i2] == ".":
            miti.append([i1,i2])
for t in range(0,len(miti)-1):
    for y in range(t+1,len(miti)):
        Min.append(bfs(miti[t][0],miti[t][1],miti[y][0],miti[y][1]))
print(max(Min))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
from collections import deque
N,M = map(int,input().split())
maze = []
for i in range(N):
    maze.append(list(input()))
INF = -1
cost = [[INF]*M for _ in range(N)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
sx,sy = 0,0
gx,gy = 0,0
ls = []
for i in range(N):
    for j in range(M):
        if maze[i][j] != "#":
            ls.append([i,j])
def bfs():
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < N and 0 <= ny < M and maze[nx][ny] != "#" and cost[nx][ny] == INF:
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost[gx][gy]
comb = list(combinations(list(range(len(ls))),2))
ans = 0
for i in range(len(comb)):
    cost = [[INF]*M for _ in range(N)]
    sx,sy = ls[comb[i][0]][0],ls[comb[i][0]][1]
    gx,gy = ls[comb[i][1]][0],ls[comb[i][1]][1]
    res = bfs()
    if res > ans:
        ans = res
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = []
for _ in range(h):
    maze.append(list(input()))

def clear_maze(sx, sy, gx, gy, maze):
    INF = float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    def bfs():
        queue = deque([])
        queue.append((sx, sy))
        distance[sx][sy] = 0
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        while queue:
            x, y = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(0, 4):
                nx, ny = x + dx[i], y + dy[i]
                if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                    if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                        queue.appendleft((nx, ny))
                        distance[nx][ny] = distance[x][y] + 1
        return distance[gx][gy]
    return bfs()


pairs = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            pairs.append([i, j])

MAX = 0
s = set()
for i in range(len(pairs)):
    sx, sy = pairs[i]
    for j in range(len(pairs)):
        gx, gy = pairs[j]
        if i == j:
            continue
        elif (sx, sy, gx, gy) in s or (gx, gy, sx, sy) in s:
            continue
        s.add((sx, sy, gx, gy))
        s.add((gx, gy, sx, sy))
        r = clear_maze(sx, sy, gx, gy, maze)
        if r == float('infinity'):
            continue
        MAX = max(MAX, r)
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = [input() for i in range(h)]
graph = {}

for i, s_i in enumerate(maze):
  for j, s_ij in enumerate(s_i):
    if s_ij == ".":
      graph[i * w + j] = []
      if i > 0 and maze[i - 1][j] == ".":
        graph[i * w + j].append((i - 1) * w + j)
      if j > 0 and maze[i][j - 1] == ".":
        graph[i * w + j].append(i * w + j - 1)
      if j < w - 1 and maze[i][j + 1] == ".":
        graph[i * w + j].append(i * w + j + 1)
      if i < h - 1 and maze[i + 1][j] == ".":
        graph[i * w + j].append((i + 1) * w + j)

ans = 0
for start in graph.keys():
  dist = {}
  c = 0
  dist[start] = c
  hoge = {start}
  for _ in graph.keys():
    c += 1
    fuga = set()
    for h in hoge:
      fuga |= set(graph[h])
    fuga -= set(dist.keys())
    for f in fuga:
      dist[f] = c  
    hoge = fuga
  ans = max(ans, max(dist.values()))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# BFS queue
import queue
import copy
H, W = map(int,input().split())
b = [list(input()) for _ in range(H)]
dist = [[10**9 for _ in range(W)] for _ in range(H)]
start = (-1,-1)
qq = queue.Queue()
# start把握
for i in range(H):
    for j in range(W):
        if b[i][j] == '.':
            qq.put((i,j))
far = 0
move = [(-1,0), (0,-1), (1,0), (0,1)]
def BFS(start, bb):
    dist = [[10**9 for _ in range(W)] for _ in range(H)]
    far = 0
    q = queue.Queue()
    q.put(start)
    dist[start[0]][start[1]] = 0
    # BFS
    while 1:
        now = q.get()
        x = now[0]
        y = now[1]
        bb[x][y] == '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            if x+dx>=0 and x+dx<= H-1 and y+dy>=0 and y+dy<=W-1 and abs(dx-dy)==1:
                if bb[x+dx][y+dy] != '#':
                    if dist[x+dx][y+dy] > dist[x][y]:
                        dist[x+dx][y+dy] = dist[x][y] + 1
                        if dist[x+dx][y+dy] > far:
                            far = dist[x+dx][y+dy]
                        q.put((x+dx,y+dy))
        if q.empty():
            break
    return far
res = 0
while 1:
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.ndimage.filters import minimum_filter, maximum_filter
import copy


def calcstep(maze, s, g):
    h, w = len(maze), len(maze[0])
    maze[s[0]] = maze[s[0]][:s[1]] + 's' + maze[s[0]][s[1]+1:]
    maze[g[0]] = maze[g[0]][:g[1]] + 'g' + maze[g[0]][g[1]+1:]
    
    cost = np.zeros((h, w), dtype=int) + 999
    done = np.zeros((h, w), dtype=bool)
    barrier = np.zeros((h, w), dtype=bool)

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

    for i in range(h):
        maze[i] = list(maze[i])
        for j in range(w):
            if maze[i][j] == 's':
                start = (i, j)
                cost[i, j] = 0
                done[i, j] = True
            if maze[i][j] == 'g':
                goal = (i, j)
            if maze[i][j] == '#':
                barrier[i, j] = True

    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:
            break
    return i



h, w = map(int, input().split())
maze = [input() for _ in range(h)]


res = -1
for i in range(h):
    for j in range(w):
        if(maze[i][j] == '#'): continue
        
        for k in range(h):
            for l in range(w):
                if(maze[k][l] == '#'): continue
                if(i==k and j==l): continue
                tmpmaze = copy.deepcopy(maze)
                steps = calcstep(tmpmaze, [i, j], [k, l])
                if(steps > res):
                    res = steps
print(res)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import sys

input = sys.stdin.readline

INF = float('inf')

def floyd_warshall(V, E):
    dist = {u: {v: INF for v in V} for u in V}
    for v in V:
        dist[v][v] = 0
        for (i, j) in E[v]: dist[v][(i, j)] = 1
    for k in V:
        for i, j in product(V, repeat=2):
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
    for v in V:
        if dist[v][v] < 0: return None
    return dist

H, W = map(int, input().split())
maze = [input() for _ in range(H)]
V = []
E = {}
for i, j in product(range(H), range(W)):
    if maze[i][j] == '#': continue
    V += [(i, j)]
    check = [(i+dx, j+dy) for dx, dy in [(1, 0), (0, 1)] if i+dx <= H-1 and j+dy <= W-1]
    for x, y in check:
        if maze[x][y] == '.':
            E.setdefault((i, j), [])
            E.setdefault((x, y), [])
            E[(i, j)].append((x, y))
            E[(x, y)].append((i, j))
dist = floyd_warshall(V, E)
ans = 0
for D in dist.values():
    ans = max(ans, max(D.values()))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = [input() for i in range(h)]
graph = {}

for i, s_i in enumerate(maze):
  for j, s_ij in enumerate(s_i):
    if s_ij == ".":
      graph[i * w + j] = []
      if i > 0 and maze[i - 1][j] == ".":
        graph[i * w + j].append((i - 1) * w + j)
      if j > 0 and maze[i][j - 1] == ".":
        graph[i * w + j].append(i * w + j - 1)
      if j < w - 1 and maze[i][j + 1] == ".":
        graph[i * w + j].append(i * w + j + 1)
      if i < h - 1 and maze[i + 1][j] == ".":
        graph[i * w + j].append((i + 1) * w + j)


def solve_dist(d, s, c):
  new_place = [n for n in graph[s] if n not in d.keys()]
  for n in new_place :
    d[n] = c + 1
  for n in new_place :
    solve_dist(d, n, d[n])


ans = 0
for start in graph.keys():
  dist = {}
  c = 0
  dist[start] = c
  hoge = {start}
  for _ in graph.keys():
    c += 1
    fuga = set()
    for h in hoge:
      fuga |= set(graph[h])
    fuga -= set(dist.keys())
    for f in fuga:
      dist[f] = c  
    hoge = fuga
    solve_dist(dist, start, 0)
  ans = max(ans, max(dist.values()))
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
sys.setrecursionlimit(10**9)
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i: divisors.append(n//i)
    return divisors
def is_prime(n):
    if n == 1: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0: return False 
    return True
def primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n + 1, i): is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]
def sieve_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime
def run_length_encode(s):
    count = 1
    code = []
    target = s[0]
    for i in range(1, len(s)):
        if target == s[i]: count += 1
        else:
            code.append((target, count))
            target = s[i]
            count = 1
    code.append((target, count))
    return code

H,W = imn()
S = [input() for _ in range(H)]
an = 10**10
def m(a, b, c, d, cnt, done):
    if a < 0 or a >= H or b < 0 or b >= W: return False
    if S[a][b] == '#': return False 
    do = copy.deepcopy(done)
    global an
    if a == c and b == d:
        an = min(an, cnt)
        return True
    else:
        if an <= cnt: return
        do[a][b] = True
        cnt += 1
        if a-1 >= 0 and not done[a-1][b]: m(a-1,b,c,d,cnt,do)
        if b-1 >= 0 and not done[a][b-1]: m(a,b-1,c,d,cnt,do)
        if b+1 < W  and not done[a][b+1]: m(a,b+1,c,d,cnt,do)
        if a+1 < H  and not done[a+1][b]: m(a+1,b,c,d,cnt,do)
        return 
ans = -1
for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if i == k and j == l: continue
                done = [[False for _ in range(W)]for _ in range(H)]
                m(i,j,k,l,0, copy.deepcopy(done))
                if an != 10**10:
                    ans = max(ans, an)
                an = 10**10 
print(ans)