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 array import array

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

g = []

for i in range(w * h):
    g.append(array('l', [10000000] * (w * h)))

for i in range(w * h):
    g[i][i] = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            continue
        if maze[i][j] == '.':
            if i > 0 and maze[i-1][j] != '#':
                g[i * w + j][(i-1) * w + j] = 1
                g[(i-1) * w + j][i * w + j] = 1
            if i < h-1 and maze[i+1][j] != '#':
                g[i * w + j][(i+1) * w + j] = 1
                g[(i+1) * w + j][i * w + j] = 1
            if j > 0 and maze[i][j-1] != '#':
                g[i * w + j][i * w + j-1] = 1
                g[i * w + j-1][i * w + j] = 1
            if j < w-1 and maze[i][j+1] != '#':
                g[i * w + j][i * w + j+1] = 1
                g[i * w + j+1][i * w + j] = 1

def floyed(g, h, w):
    for k in range(h*w):
        for i in range(h*w):
            if g[i][k] == 10000000:
                continue
            for j in range(h*w):
                if g[k][j] == 10000000:
                    continue
                if i == j or i == k or k == j:
                    continue
                if g[i][j] > g[i][k] + g[k][j]:
                    g[i][j] = g[i][k] + g[k][j]

floyed(g,h,w)
result = 0

for i in range(w*h):
    for j in range(w*h):
        if g[i][j] < 10000000:
            if g[i][j] > result:
                result = g[i][j]

print(result)

Submission status: Time Limit Exceeded

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

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

ans = 0

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


def bfs(x, y):
    m = []
    for _ in range(H):
        m.append([-1] * W)

    q = deque()
    q.append([y, x, 0])
    maximus = 0

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if maximus < v+1:
                    maximus = v+1

    return maximus


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
# h, w = map(int,input().split())
# maze = [list(input()) for i in range(h)]
# seen = [[-1]*w for _ in range(h)]
# move = [[1,0],[-1,0],[0,1],[0,-1]]
# # start = [0,0]
# start = [2,2]
# g = [4,5]
# que = [start]
# seen[start[0]][start[1]] = 0
# que.append(start)
# while que:
#     y,x = que.pop(0)
#     if (y == g[0]) and (x == g[1]):
#         break
#     for i in range(len(move)):
#         ny,nx = y+move[i][0], x+move[i][1]
#         if (0 <= ny < h) and (0 <= nx < w):
#             if maze[ny][nx] == '.':
#                 if seen[ny][nx] == -1:
#                     seen[ny][nx] = seen[y][x]+1
#                     que.append([ny,nx])

# print(seen[])

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if (0<=new_y<len(maze)) and (0<=new_x<len(maze[0])):
                if maze[new_y][new_x] == "." and \
                    visited[new_y][new_x] == -1:
                    
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

h, w = map(int, input().split())
maze = [input() for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                if (maze[i][j] == '.') and (maze[k][l] == '.') and ([i,j] != [k,l]):
                    sy,sx = i,j
                    gy,gx = k,l
                    visited = [[-1]*w for j in range(h)]
                    a = bfs(maze,visited,sy,sx,gy,gx)
                    ans = max(ans, a)
# sy,sx = 0,0
# gy,gx = 2,2
# visited = [[-1]*w for j in range(h)]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
C = [['#' for j in range(W + 2)] for i in range(H + 2)]

for i in range(H):
    s = input()
    for j in range(W):
        C[i + 1][j + 1] = s[j]
ans = 0
for sy in range(1, H + 1):
    for sx in range(1, W + 1):
        for gy in range(1, H + 1):
            for gx in range(1, W + 1):
                q = deque()
                q.append((sy, sx, 0))
                S = set([])
                r = 0
                while len(q) > 0:
                    t = q.popleft()
                    y, x, d = t[0], t[1], t[2]
                    if C[y][x] == '#':
                        continue
                    if (y, x) in S:
                        continue
                    else:
                        S.add((y, x))

                    if (y, x) == (gy, gx):
                        r = d
                        break
                    q.append((y + 1, x , d + 1))
                    q.append((y - 1, x, d + 1))
                    q.append((y, x + 1, d + 1))
                    q.append((y, x - 1, d + 1))

                ans = max(ans, r)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
h,w = map(int, input().split())
s = [input() for _ in range(h)]

if h==1 and w==1:
    print(0)
    exit()

def solve(sh,sw,gh,gw):
    if s[sh][sw]=="#" or s[gh][gw]=="#":
        return -1

    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[sh][sw] = True
    q = deque([(sh,sw,0)])
    while len(q)>0:
        hi,wi,r = q.popleft()
        for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
            if hi+dh>=0 and hi+dh<h and wi+dw>=0 and wi+dw<w and s[hi+dh][wi+dw]==".":
                if hi+dh==gh and wi+dw==gw:
                    return r+1
                elif not visited[hi+dh][wi+dw]:
                    visited[hi+dh][wi+dw] = True
                    q.append((hi+dh,wi+dw,r+1))

    return -1

res = -1
for shi in range(h):
    for swi in range(w):
        if s[shi][swi]=="#":
            continue
        for ghi in range(h-1,-1,-1):
            for gwi in range(w-1,-1,-1):
                if shi>=ghi and swi>=gwi:
                    break
                r = solve(shi,swi,ghi,gwi)
                res = max(res, r)

print(res)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import numpy as np
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]

li = [["#" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        li[i][j] = s[j]

def all_pairs_shortest_paths(W):
    # 頂点の数
    n = len(W)
    # 結果を格納する行列を用意する
    res = [[0] * n for i in range(n)]
    # 用意した行列を初期化する
    for i in range(n):
        for j in range(i, n):
            if i == j:
                val = 0
            elif W[i][j]:
                val = W[i][j]
            else:
                val = inf
            res[i][j] = res[j][i] = val
    # 動的計画法ですべての超点間の最短距離を求める
    for k in range(n):
        for u in range(n):
            for v in range(n):
                res[u][v] = min(res[u][v], res[u][k] + res[k][v])
    return res

a = np.arange(h*w)
a = a.reshape([h,w])
a = a.tolist()

lin = [[0 for i in range(h*w)]for j in range(h*w)]

for i in range(h):
    for j in range(w-1):
        if li[i][j] == "." and li[i][j+1] == ".":
            lin[a[i][j]][a[i][j+1]] = 1
            lin[a[i][j+1]][a[i][j]] = 1

for i in range(h-1):
    for j in range(w):
        if li[i][j] == "." and li[i+1][j] == ".":
            lin[a[i][j]][a[i+1][j]] = 1
            lin[a[i][j]][a[i+1][j]] = 1

lis = all_pairs_shortest_paths(lin)

ma = 0
for i in range(h*w):
    for j in range(h*w):
        if lis[i][j] != 10**10:
            ma = max(lis[i][j],ma)

print(ma)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [[None for i in range(W)] for i in range(H)]

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

from collections import deque

def dfs(i, j):
  colors = [[["white"] for i in range(W)] for j in range(H)]
  queue = deque()
  queue.append((i, j))
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  result = -1
  while queue:
    i, j = map(int, queue.popleft())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] != "black":
        d = min(distance[i][j] + 1, distance[x][y])
        distance[x][y] = d
        result = max(result, d)
        queue.append((x, y))
  
  return result


import itertools
ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "#": 
      continue

    ans = max(ans, dfs(i, j))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def search(h, w, pre_h, pre_w):
    can = []
    if h > 0:
        can.append((h-1, w))
    if h < H-1:
        can.append((h+1, w))
    if w > 0:
        can.append((h, w-1))
    if w < W-1:
        can.append((h, w+1))
    res = []
    for h, w in can:
        if S[h][w]=='.' and (h, w) != (pre_h, pre_w):
            res.append((h, w))
    return res

def bfs(h, w):
    d = [[float('inf') for _ in range(W)] for _ in range(H)]
    d[h][w] = 0
    pre_h, pre_w = h, w
    adj_list = search(h, w, pre_h, pre_w)
    open_list = deque([])
    closed_list = []
    for adj in adj_list:
        open_list.append((adj[0], adj[1], pre_h, pre_w))
    cnt = 0
    while True:
        cnt += 1
        if len(open_list) == 0:
            break
        h, w, pre_h, pre_w = open_list.popleft()
        closed_list.append((h, w, pre_h, pre_w))
        d[h][w] = min(d[h][w], d[pre_h][pre_w] + 1)
        adj_list = search(h, w, pre_h, pre_w)
        for adj in adj_list:
            if (adj[0], adj[1], h, w) in closed_list:
                continue
            open_list.append((adj[0], adj[1], h, w))

    res = 0
    for h in range(H):
        for w in range(W):
            if not d[h][w] == float('inf'):
                res = max(res, d[h][w])
    return res

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

if __name__ == "__main__":
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            maxd = bfs(h, w)
            ans = max(maxd, ans)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs():
    d = [[float("inf")]* m for i in range(n)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    sx = a1
    sy = a2
    gx = a3
    gy = a4
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    while que:
        p = que.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 d[nx][ny] == float("inf"):
                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)]
ans = 0
for a1 in range(n):
    for a2 in range(m):
        if maze[a1][a2] == ".":
            maze[a1][a2]  = "S"
            for a3 in range(n):
                for a4 in range(m):
                     if maze[a3][a4] == ".":
                        maze[a3][a4]  = "G"
                        ans = max(bfs(),ans)
                        maze[a3][a4]  = "."
            maze[a1][a2]  = "."
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def solve(maze, start, end):
  memo = deque()
  q = deque()
  q.append([start,[]])
  ans = 0
  while q:
    cur, path = q.popleft()
    if cur == end:
      ans = path
      break
    elif cur in memo:
      continue
    else:
      memo.append(cur)
      for y, x in zip((0,0,1,-1),(1,-1,0,0)):
        if maze[cur[0]+y][cur[1]+x] == ".":
          q.append([[cur[0]+y,cur[1]+x],copy.deepcopy(path)+[cur]])
  return ans


H, W = map(int, input().split())
Maze = [["#"]*(W+2)]+[["#"]+list(input())+["#"] for _ in range(H)] + [["#"]*(W+2)]
Ans = 0
for sy in range(1, H+1):
  for sx in range(1, W+1):
    if Maze[sy][sx] == "#":
      continue
    memo = [[False]*(W+2) for _ in range(H+2)]
    for ey in range(sy, H+1):
      for ex in range(1, W+1):
        if Maze[ey][ex] == "#" or memo[ey][ex]:
          continue
        P = solve(Maze, [sy, sx], [ey,ex])
        Ans = max(Ans, len(P))
        for p in P:
          memo[p[0]][p[1]] = True
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from collections import deque

def bfs(sx,sy,gx,gy):
    d = [[float("inf")] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.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 < h and 0 <= ny < w and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

h,w=map(int,input().split())
s = [list(input()) for i in range(h)]
ans=0
memo=[[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            for k in range(i,h):
                for l in range(w):
                    if i==k and j==l:
                        continue
                    elif s[k][l]=='.':
                        ans = max(ans,bfs(i,j,k,l))
                        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy
H,W = map(int,input().split())

Map = []
Map.append(list('@'*(W+2)))
for i in range(H):
  s = list('@'+input()+'@')
  Map.append(s)
Map.append(list('@'*(W+2)))
  
#400*400 = 160000 = 1.6*10**5
#スタートとゴール用
select = []
for i in range(H+2):
 if((i != 0)and(i != H+1)):
  for j in range(W+2):
   if((j != 0)and(j != W+1)):
    for k in range(H+2):
     if((k != 0)and(k != H+1)):
      for l in range(W+2):
       if((l != 0)and(l != W+1)):
         select.append([i,j,k,l])

          
#print(len(select))          
#幅優先探索
def bfs(sy,sx,gy,gx,Map):
  qy,qx = queue.Queue(),queue.Queue()
  qy.put(sy),qx.put(sx)
  ans = 0
  while(1):
    if(qx.empty() == True): return ans
    #座標の取り出し
    y,x = qy.get(),qx.get()
    if((y == gy)and(x == gx)): #ゴールなら終了
      ans = Map[y][x]
      #for i in range(H+2):
      #   print(Map[i])
      #print('______________')
      return ans
    
    #次に進むところ
    vec_y = [0,0,1,-1]
    vec_x = [1,-1,0,0]
    for i in range(4):
      if(Map[y+vec_y[i]][x+vec_x[i]] == '.'):
        Map[y+vec_y[i]][x+vec_x[i]] = Map[y][x] + 1
        qy.put(y+vec_y[i]),qx.put(x+vec_x[i])
           
ans = 0 
for s in range(len(select)):
  sy,sx = select[s][0], select[s][1] 
  gy,gx = select[s][2], select[s][3]
  Map2 = copy.deepcopy(Map)

  #スタートとゴールの設置
  if((Map2[sy][sx] == '.')and(Map2[gy][gx] == '.')):
   Map2[sy][sx] = 0
   #幅優先探索
   tmp_ans = bfs(sy,sx,gy,gx,Map2)
   #print(sy,sx,gy,gx)
   #print(tmp_ans)
   ans = max(ans,tmp_ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H, W = map(int, input().split())
edges = [[None for i in range(W)] for i in range(H)]

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

from collections import deque

def dfs(i, j):
  colors = [[["white"] for i in range(W)] for j in range(H)]
  queue = deque()
  queue.append((i, j))
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  while queue:
    i, j = map(int, queue.popleft())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] != "black":
        distance[x][y] = min(distance[i][j] + 1, distance[x][y])
        queue.append((x, y))
  
  return distance


import itertools
ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "#": 
      continue

    L = list(itertools.chain.from_iterable(dfs(i, j)))
    m = max(list(filter(lambda x: x != inf, L)))
    ans = max(ans, m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def bfs():
    d = [[float("inf")]* m for i in range(n)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    for i in range(n):
        for j in range(m):
            if maze[i][j] == "S":
                sx = i
                sy = j
            if maze[i][j] == "G":
                gx = i
                gy = j
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    while que:
        p = que.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 d[nx][ny] == float("inf"):
                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)]
ans = 0
for a1 in range(n):
    for a2 in range(m):
        if maze[a1][a2] == ".":
            maze[a1][a2]  = "S"
            for a3 in range(n):
                for a4 in range(m):
                     if maze[a3][a4] == ".":
                        maze[a3][a4]  = "G"
                        ans = max(bfs(),ans)
                        maze[a3][a4]  = "."
            maze[a1][a2]  = "."
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

    # 移動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 < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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

d = [[False] * w for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            d[sx][sy] = True
            for gx in range(h):
                for gy in range(w):
                    if maze[gx][gy] == ".":
                        if d[gx][gy]:
                            continue
                        ans = max(ans, bfs())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def clear_maze(sx, sy, gx, gy, maze):

    INF = float("inf")

    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)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length:
                    try:
                        if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                            queue.insert(0, (nx, ny))
                            distance[nx][ny] = distance[x][y] + 1
                    except Exception as e:
                        print(nx, ny)
                        print(maze)
                        print(maze[nx][ny])
                        print(distance)
                        exit()

        return distance[gx][gy]

    return bfs()


H, W = map(int, input().split())
maze = []
for w in range(H):
    maze.append([x for x in input()])
ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            sx, sy = h, w
            for g in range(H):
                for l in range(w, W):
                    if maze[g][l] == ".":
                        gx, gy = g, l
                        ans = max(clear_maze(sx,sy,gx,gy, maze),ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def warshall_floyd(V, E):
    INF = 10 ** 9
    d = [[0 for _ in range(V + 1)]] + [[0] + [INF for j in range(V)] for i in range(V)]
    for i in range(V + 1):
        d[i][i] = 0
    for i, j in E:
        d[i][j] = 1
        d[j][i] = 1
    for k in range(1, V + 1):
        for i in range(1, V):
            for j in range(i, V + 1):
                dk = d[i][k] + d[k][j]
                if d[i][j] > dk:
                    d[i][j] = dk
                    d[j][i] = dk
    return d


h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
n = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            n += 1
            s[i][j] = n
        else:
            s[i][j] = 0


E = []
for i in range(h):
    for j in range(w):
        p = s[i][j]
        if p > 0:
            if j < w - 1:
                p1 = s[i][j + 1]
                if p1 > 0:
                    E.append([p, p1])
            if i < h - 1:
                p2 = s[i + 1][j]
                if p2 > 0:
                    E.append([p, p2])

ans = 0
INF = 10 ** 9
D = warshall_floyd(n, E)
ans = max(list(map(max, D)))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
meiro = [list(input()) for i in range(h)]
max_d = 0
from collections import deque



def bfs(sx,sy,t_i,t_j):
    que = deque([(sx,sy)])
    INF= float('inf')
    d = [[INF]*w for i in range(h)]
    d[sx][sy] = 0
    while que:
        x,y =que.popleft()
        for dx,dy in [(0,1),(1,0),(-1,0),(0,-1)]:
            nx,ny = x+dx,y+dy
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == INF and meiro[nx][ny] =='.':
                d[nx][ny] = d[x][y] +1
                que.append((nx,ny))
    return d[t_i][t_j] if d[t_i][t_j] != float('inf') else 0

for s_i in range(h):
    for s_j in range(w):
        for t_i in range(h):
            for t_j in range(w):
                if not (s_i == t_i and s_j == t_j):
                    # visited = [[0 for i in range(w)] for i in range(h)]
                    max_d = max(bfs(s_i,s_j,t_i,t_j), max_d)
print(max_d)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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

    # 移動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 < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == 10 ** 12:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]


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

d = [[False] * w for i in range(h)]
ans = 0
for sx in range(h):
    for sy in range(w):
        if maze[sx][sy] == ".":
            for gx in range(h):
                for gy in range(w):
                    if maze[gx][gy] == ".":
                        if d[gx][gy]:
                            continue
                        ans = max(ans, bfs())
            d[sx][sy] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
from collections import deque

def bfs(sx,sy,gx,gy):
    d = [[float("inf")] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.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 < h and 0 <= ny < w and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

h,w=map(int,input().split())
s = [list(input()) for i in range(h)]
ans=0
memo=[[0] * w for i in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            for k in range(i,h):
                for l in range(w):
                    if s[k][l]=='.':
                        ans = max(ans,bfs(i,j,k,l))
                        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
cost = [[600] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0


def bfs(sx, sy, gx, gy):
    q = deque([(sx, sy)])
    cost[sy][sx] = 0

    while q != deque([]):
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < w and 0 <= ny and ny < h and s[ny][nx] == "." and cost[ny][nx] == 600:
                q.append((nx, ny))
                cost[ny][nx] = cost[y][x] + 1
                if nx == gx and ny == gy:
                    return cost[gy][gx]


ans = 0
for i in range(h):
    for j in range(w):
        for k in range(h):
            for l in range(w):
                cost = [[600] * w for _ in range(h)]
                tmp = bfs(j, i, l, k)
                if tmp != None:
                    ans = max(tmp, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

H, W = map(int, readline().split())
S = tuple(read().split())


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    while queue:
        x, y = queue.popleft()
        visited[x][y] = True

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)