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: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque
import re
import math
import functools
import itertools
import fractions

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29


def mk1d(n, val=INF):
    return [val for i in range(n)]

def mk2d(h, w, val=INF):
    return [[val for i in range(w)]for i in range(h)]

DIV = 998244353

def gcd(a, b):
    if(b == 0):
        return a
    return gcd(b, a % b)

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm(*numbers):
    return functools.reduce(lcm_base, numbers, 1)


def floyd_warshall(costs):
    N = len(costs)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                costs[i][j] = min(costs[i][j], costs[i][k]+costs[k][j])
    return costs

def lcm_list(numbers):
    return functools.reduce(lcm_base, numbers, 1)

def main():
    H,W = isRaw()
    SS = [sRaw() for _ in range(H)]
    costs = mk2d(H*W, H*W, INF)
    E = []
    for h in range(H):
        for w in range(W):
            cur = h*W+w
            if h<H-1 and SS[h][w]=="." and SS[h+1][w]==".":
                costs[cur][cur+W] = 1
                costs[cur+W][cur] = 1
            if w < W-1 and SS[h][w] == "." and SS[h][w+1] == ".":
                costs[cur][cur+1] = 1
                costs[cur+1][cur] = 1                
    costs = floyd_warshall(costs)
    maxCost = 0
    for cur in range(H*W):
        for nxt in range(H*W):
            if(costs[cur][nxt]!=INF):
                maxCost = max(maxCost,costs[cur][nxt])
    return maxCost

if __name__ == "__main__":
    print(main())

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

H,W=map(int,input().split())
S=[input().strip() for i in range(H)]
from collections import deque

def bfs(x,y):
    

    Q=deque()
    Q.append((x,y))
    count=[[0]*W for i in range(H)]

    while Q:
        x,y=Q.pop()
        for z,w in [(x+1,y),(x-1,y),(x,y-1),(x,y+1)]:
            if 0<=z<H and 0<=w<W and count[z][w]==0 and S[z][w]==".":
                count[z][w]=count[x][y]+1
                Q.appendleft((z,w))

    return max([max(c) for c in count])

ANS=0

for i in range(H):
    for j in range(W):
        ANS=max(ANS,bfs(i,j))

print(ANS)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque
from operator import itemgetter
from heapq import heappop, heappush
#input = sys.stdin.readline
def inpl(): return list(map(int, input().split()))
H, W = inpl()
G = [[1]*(W+2)]
for _ in range(H):
    G.append([1] + [int(s=="#") for s in input()] + [1])
G.append([1]*(W+2))

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        dist = [[-1]*(W+2) for _ in range(H+2)]
        dist[h][w] = 0
        Q = deque()
        Q.append([h, w])
        while Q:
            ph, pw = Q.popleft()
            for dh, dw in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
                qh, qw = ph+dh, pw + dw
                if G[qh][qw]:
                    continue
                if dist[qh][qw] == -1:
                    dist[qh][qw] = dist[ph][pw] + 1
                    Q.append([qh, qw])
                
        for y in range(1, H+1):
            for x in range(1, W+1):
                ans = max(ans, dist[y][x])
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    from collections import deque

    h, w = map(int, input().split())

    s = []
    sr, sc = -1, -1
    for r in range(h):
        _s = input()
        s.append(_s)

        if sr == -1:
            col = _s.find('.')
            if col >= 0:
                sr = r
                sc = col

    drdc = (1, 0), (-1, 0), (0, 1), (0, -1)

    q = deque()
    q.append((sr, sc, 0))

    dist = [[-1] * w for _ in range(h)]
    dist[sr][sc] = 0

    while q:
        r, c, d = q.popleft()
        for dr, dc in drdc:
            nr = r + dr
            if nr < 0 or h <= nr:
                continue
            nc = c + dc
            if nc < 0 or w <= nc:
                continue
            if s[nr][nc] == '#':
                continue
            if dist[nr][nc] != -1:
                continue
            dist[nr][nc] = d + 1
            q.append((nr, nc, d + 1))

    sr, sc = r, c

    q = deque()
    q.append((sr, sc, 0))

    dist = [[-1] * w for _ in range(h)]
    dist[sr][sc] = 0

    while q:
        r, c, d = q.popleft()
        for dr, dc in drdc:
            nr = r + dr
            if nr < 0 or h <= nr:
                continue
            nc = c + dc
            if nc < 0 or w <= nc:
                continue
            if s[nr][nc] == '#':
                continue
            if dist[nr][nc] != -1:
                continue
            dist[nr][nc] = d + 1
            q.append((nr, nc, d + 1))

    print(d)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#h,w = map(int,input().split())
#s = [input() for _ in range(h)]

h = 20
w = 20
s = ['.' * 20 for _ in range(20)]
ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            dis = [[-1] * w for _ in range(h)]
            dis[i][j] = 0
            q = [(i,j)]
            while q:
                l0,l1 = q.pop(0)
                if l0 > 0:
                    if s[l0-1][l1] == '.':
                        if dis[l0-1][l1] > dis[l0][l1] + 1 or dis[l0-1][l1] == -1:
                            dis[l0-1][l1] = dis[l0][l1] + 1
                            q.append((l0-1,l1))
                if l0 < h - 1:
                    if s[l0+1][l1] == '.':
                        if dis[l0+1][l1] > dis[l0][l1] + 1 or dis[l0+1][l1] == -1:
                            dis[l0+1][l1] = dis[l0][l1] + 1
                            q.append((l0+1,l1))
                if l1 > 0:
                    if s[l0][l1-1] == '.':
                        if dis[l0][l1-1] > dis[l0][l1] + 1 or dis[l0][l1-1] == -1:
                            dis[l0][l1-1] = dis[l0][l1] + 1
                            q.append((l0,l1-1))
                if l1 < w - 1:
                    if s[l0][l1+1] == '.':
                        if dis[l0][l1+1] > dis[l0][l1] + 1 or dis[l0][l1+1] == -1:
                            dis[l0][l1+1] = dis[l0][l1] + 1
                            q.append((l0,l1+1))
        dis_max = 0
        for k in dis:
            dis_max = max(max(k), dis_max)
        ans = max(dis_max,ans)

print(ans)

Submission status: Wrong Answer

Solution code:
#D
from collections import deque
H,W = map(int,input().split())
S = [list(str(input())) for i in range(H)]

MAX = 0
for i in range(H):
    for j in range(W):
        s = [i,j]
        dist = [[-1 for a in range(W)] for b in range(H)]
        
        dist[i][j] = 0
        de = deque([s])
        while de:
            d = de.popleft()
            h,w = d
            di = dist[h][w]
            if h > 0:
                if S[h-1][w] == "." and dist[h-1][w] < 0:
                    dist[h-1][w] = di+1
                    de.append([h-1,w])
            if h < H-1:
                if S[h+1][w] == "." and dist[h+1][w] < 0:
                    dist[h+1][w] = di+1
                    de.append([h+1,w])
            if w > 0:
                if S[h][w-1] == "." and dist[h][w-1] < 0:
                    dist[h][w-1] = di+1
                    de.append([h,w-1])
            if w < W-1:
                if S[h][w+1] == "." and dist[h][w+1] < 0:
                    dist[h][w+1] = di+1
                    de.append([h,w+1])
                    
        for h in range(H):
            for w in range(W):
                MAX = max(MAX,dist[h][w])
                
print(MAX)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
maze = [list(input())[: -1] for _ in range(H)]
#print(maze)
res = 0
d = [-1, 0, 1, 0]
for s in range(H * W):
  sy = s // W
  sx = s % W
  Q = dq([])
  Q.append(s)
  dist = [float("inf")] * (H * W)
  dist[s] = 0
  while len(Q):
    p = Q.popleft()
    py = p // W
    px = p % W
    for k in range(4):
      qy = py + d[k]
      qx = px + d[-1 - k]
      if 0 <= qy < H and (0 <= qx < W):
        if maze[qy][qx] == "#": continue
        if dist[qy * W + qx] > dist[p] + 1:
          Q.append(qy * W + qx)
          dist[qy * W + qx] = dist[p] + 1
  for x in dist:
    if x != float("inf"): res = max(res, x)
print(res)

Submission status: Wrong Answer

Solution code:
def main():

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

    ans = 0
    mv = [[1,0], [-1,0], [0, 1], [0,-1]]
    for i in range(H):
        for j in range(W):
            if S[i][j] == ".":
                cnt = 0
                cur = [[i, j]]
                visited = set([i, j])
                while cur:
                    temp = []
                    for k, l in cur:
                        for dk, dl in mv:
                            k1, l1 = k+dk, l+dl
                            if 0<=k1<H and 0<=l1<W and S[k1][l1] == "." and (k1,l1) not in visited:
                                visited.add((k1,l1))
                                temp.append([k1, l1])
                    cur = temp
                    if len(cur) > 0: cnt += 1
                ans = max(ans, cnt)
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
maze = [list(input()) for _ in range(h)]

dx,dy = [0,1,0,-1],[1,0,-1,0]
ans = 0
for i in range(h):
    for j in range(w):
        que = deque()
        que.append((j,i))
        f = [[True]*w for _ in range(h)]
        d = [[0]*w for _ in range(h)]
        f[i][j] = False
        while que:
            x,y = que.popleft()
            for k in range(4):
                nx,ny = x + dx[k], y + dy[k]
                if 0 <= nx < w and 0 <= ny < h:
                    if f[ny][nx] and maze[ny][nx] == '.':
                        que.append((nx,ny))
                        d[ny][nx] = d[y][x] + 1
                        f[ny][nx] = False
        for k in range(h):
            ans = max(ans,max(d[k]))
print(ans)

Submission status: Wrong Answer

Solution code:
def examA():
    C = SI()
    ans = chr(ord(C)+1)
    print(ans)
    return

def examB():
    N,K,M = LI()
    A = LI()
    ans = N*M-sum(A)
    if ans>K:
        ans = -1
    elif ans<0:
        ans = 0
    print(ans)
    return

def examC():
    N, M = LI()
    ansT = 0; ansP = 0
    d = defaultdict(bool)
    WA = [0]*(N+1)
    for i in range(M):
        S, P = LSI()
        S = int(S)
        if P=="WA":
            WA[S] +=1
        elif P=="AC":
            if d[S]:
                continue
            else:
                d[S] = True
                ansT +=1
                ansP +=WA[S]
    print(ansT,ansP)
    return


def bfs_grid(h,w,s,maze):
    distance = [[-1]*w for _ in range(h)]
    def bfsg():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#'):
                    if distance[ny][nx]<=distance[y][x]+1 and distance[ny][nx]!=-1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfsg()
def examD():
    H,W = LI()
    S = [SI() for _ in range(H)]
    ans = 0
    for i in range(H):
        for j in range(W):
            D = bfs_grid(H, W, [i, j], S)
#            print(D)
            cur = 0
            for d in D:
                cur = max(cur,max(d))
            ans = max(ans,cur)
    print(ans)
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examD()

Submission status: Wrong Answer

Solution code:
H,W = map(int,input().split())
S = [input() for i in range(H)]
from collections import deque

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque([(0,0)])
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[0][0] = 1
mxx = mxy = -1
mxd = 0
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        if dist[ny][nx] > mxd:
            mxd = dist[ny][nx]
            mxx = nx
            mxy = ny
        q.append((nx,ny))

q = deque([(mxx,mxy)])
dist = [[0]*W for i in range(H)]
visited = [[0]*W for i in range(H)]
visited[mxy][mxx] = 1
mxd = 0
while q:
    x,y = q.popleft()
    for dx,dy in dxy:
        nx,ny = x+dx,y+dy
        if not 0 <= nx < W: continue
        if not 0 <= ny < H: continue
        if visited[ny][nx]: continue
        if S[ny][nx] == '#': continue
        visited[ny][nx] = 1
        dist[ny][nx] = dist[y][x] + 1
        if dist[ny][nx] > mxd:
            mxd = dist[ny][nx]
        q.append((nx,ny))

print(max(max(row) for row in dist))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
maze = [list(input())[: -1] for _ in range(H)]
#print(maze)
res = 0
d = [-1, 0, 1, 0]
for s in range(H * W):
  sy = s // W
  sx = s % W
  for g in range(H * W):
    gy = g // W
    gx = g % W
    Q = dq([])
    Q.append(s)
    dist = [float("inf")] * (H * W)
    dist[s] = 0
    while len(Q):
      p = Q.popleft()
      py = p // W
      px = p % W
      for k in range(4):
        qy = py + d[k]
        qx = px + d[-1 - k]
        if 0 <= qy < H and (0 <= qx < W):
          if maze[qy][qx] == "#": continue
          if dist[qy * W + qx] > dist[p] + 1:
            Q.append(qy * W + qx)
            dist[qy * W + qx] = dist[p] + 1
    if dist[g] != float("inf"): res = max(res, dist[g])
print(res)

Submission status: Wrong Answer

Solution code:
from collections import deque
H,W = map(int,input().split())
S = list(list(input())for _ in range(H))
ans = 0
for sh in range(H):
    for sw in range(W):
        queue = deque([[sh,sw]])
        cost = [[10000]*W for i in range(H)]
        cost[sh][sw] = 0
        while queue:
            h,w = queue.popleft()
            for nh,nw in [[h-1,w],[h,w-1],[h+1,w],[h,w+1]]:
                if not (0 <= nh < H and 0 <= nw < W):
                    continue
                if S[nh][nw] == '.' and cost[nh][nw] > cost[h][w]+1:
                    cost[nh][nw] = cost[h][w]+1
                    queue.append([nh,nw])
                    ans = max(ans,cost[nh][nw])
print(ans)

Submission status: Wrong Answer

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W=MI()
    def is_inside(hw):
        h,w = hw
        return 0<=h<H and 0<=w<W
    grid=[[s for s in ST()] for _ in range(H)]
    ans = 0
    dxdy = [(1,0),(0,1),(-1,0),(0,-1)]
    for i in range(H*W):
        h = i//W
        w = i%W
        visited = set()
        q = [(h,w)]
        for cost in range(H*W+1):
            tmp = []
            if not q:
                ans = max(ans,cost-1)
                break
            while q:
                from_ = q.pop()
                if from_ in visited:
                    continue
                visited.add(from_)
                for dh,dw in dxdy:
                    to = (from_[0]+dh, from_[1]+dw)
                    if is_inside(to) and to not in visited and grid[to[0]][to[1]]==".":
                        tmp.append(to)
            q = tmp
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
S = ['#'*(W+2)]
white_num = 0
for _ in range(H):
    s = input()
    white_num += s.count('.')
    S.append('#'+s+'#')
S.append('#'*(W+2))

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        C = [[-1]*(W+2) for _ in range(H+2)]
        C[h][w] = 0
        q = deque()
        q.append((h, w))
        xlist = [0, 0, 1, -1]
        ylist = [1, -1, 0, 0]
        while len(q) > 0:
            x, y = q.popleft()
            for i in range(4):
                mx = x + xlist[i]
                my = y + ylist[i]
                if S[mx][my] == '#' or C[mx][my] >= 0:
                    continue
                C[mx][my] = C[x][y] + 1
                q.append((mx, my))
        max_num = 0
        for i in C:
            max_num = max(max_num, max(i))
        ans = max(ans, max_num)
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque


def dfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]

    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '#':
                continue
            if dist[ni][nj] != -1:
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j


h, w = map(int, input().split())
field = [input() for _ in range(h)]
i, j = 0, 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            break

d, i, j = dfs(field, (i, j))
d, i, j = dfs(field, (i, j))
print(d)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

def solve(sh, sw):
    visited = [[-1]*w for i in range(h)]
    visited[sh][sw] = 0
    q = deque([(sh, sw)])
    max_ = 0
    while q:
        i, j = q.popleft()
        for ni, nj in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if not(0 <= ni < h and 0 <= nj < w):
                continue
            if s[ni][nj] == "#":
                continue
            if visited[ni][nj] >= 0:
                continue
            visited[ni][nj] = visited[i][j] + 1
            max_ = max(max_, visited[ni][nj])
            q.append((ni, nj))
    return max_

ans = 0
for sh in range(h):
    for sw in range(w):
        ans = max(ans, solve(sh, sw))
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    h, w = LI()
    s = SR(h)
    q = deque()
    for i in range(h):
        for j in range(w):
            if s[i][j]==".":
                q.append((i, j))
                break
    dist = defaultdict(int)
    dist[q[0]] = 1
    while q:
        p = q.popleft()
        dp = dist[p]
        for mx, my in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            my += p[0]
            mx += p[1]
            if 0 <= mx < w and 0 <= my < h:
                if dist[(my, mx)] or s[my][mx] == "#":
                    continue
                dist[(my, mx)] = dp + 1
                q.append((my,mx))
    dist = list(dist.items())
    dist.sort(key=lambda x: x[1], reverse=True)
    q = deque()
    q.append(dist[0][0])
    dist = defaultdict(int)
    dist[q[0]] = 1
    while q:
        p = q.popleft()
        dp = dist[p]
        for mx, my in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            my += p[0]
            mx += p[1]
            if 0 <= mx < w and 0 <= my < h:
                if dist[(my, mx)] or s[my][mx] == "#":
                    continue
                dist[(my, mx)] = dp + 1
                q.append((my,mx))
    print(max(dist.values())-1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
b=[[1]*(w+2)]
for i in range(h):
  bb=[1]
  s=input()
  for j in range(w):
    if s[j]=="#":bb.append(1)
    else:bb.append(0)
  bb.append(1)
  b.append(bb)
b.append([1]*(w+2))

ans=0
d=[[-1,0],[1,0],[0,-1],[0,1]]
for si in range(1,h+1):
  for sj in range(1,w+1):
    visited={(si,sj)}
    Q=[(si,sj)]
    count=-1
    while Q:
      P=[]
      for i,j in Q:
        for di,dj in d:
          if b[i+di][j+dj]:continue
          if (i+di,j+dj)in visited:continue
          visited.add((i+di,j+dj))
          P.append((i+di,j+dj))
      Q=P
      count+=1
    ans=max(ans,count)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
def main():
    from collections import deque
    from itertools import product

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

    h_indexes = [x for x in range(H)]
    w_indexes = [x for x in range(W)]
    move = ((0, 1), (0, -1), (1, 0), (-1, 0))
    ans = 0
    for sh, gh in product(h_indexes, repeat=2):
        for sw, gw in product(w_indexes, repeat=2):
            if S[sh][sw] == '#' or S[gh][gw] == '#':
                continue
            queue = deque([(sh, sw)])
            distance = [[0] * W for _ in range(H)]
            while queue:
                h, w = queue.popleft()
                if h == gh and w == gw:
                    break
                for dh, dw in move:
                    nh = h + dh
                    nw = w + dw
                    if (1
                            and 0 <= nh < H
                            and 0 <= nw < W
                            and S[nh][nw] == '.'
                            and distance[nh][nw] == 0):
                        distance[nh][nw] = distance[h][w] + 1
                        queue.append((nh, nw))
            if ans < distance[gh][gw]:
                ans = distance[gh][gw]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def find_shortest():
  d = [[-1] * w for i in range(h)]
  dx = [1, 0, -1, 0]
  dy = [0, 1, 0, -1]

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

  while que:
    p = que.popleft()
    if p[0] == gy and p[1] == gx:
      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 maze[nx][ny] != "#" and d[nx][ny] == -1:
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gy][gx]

route = []

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

ans = -1
for sy,sx in sg:
  for gy,gx in sg:
    ans = max(ans,find_shortest())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

  while que:
    p = que.popleft()
    if p[0] == gy and p[1] == gx:
      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 maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gy][gx]

route = []

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

ans = -1
for sy,sx in sg:
  for gy,gx in sg:
    if find_shortest() != float("inf"):
      ans = max(ans,find_shortest())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

  while que:
    p = que.popleft()
    if p[0] == gy and p[1] == gx:
      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 maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gy][gx]

route = []

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

for sy,sx in sg:
  for gy,gx in sg:
    if find_shortest() != float("inf"):
      route.append(find_shortest())

ans = max(route)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

  while que:
    p = que.popleft()
    if p[0] == gy and p[1] == gx:
      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 maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
        que.append((nx, ny))
        d[nx][ny] = d[p[0]][p[1]] + 1
  return d[gy][gx]

route = []

for sy in range(h):
  for sx in range(w):
    for gy in range(h):
      for gx in range(w):
        if find_shortest() != float("inf"):
          route.append(find_shortest())

ans = max(route)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math , sys

H,W = list(map( int, input().split() ))
maze = []
for i in range(H):
    maze.append(input())
if H==1:
    print(W-1)
    sys.exit()
if W ==1:
    print(H-1)
    sys.exit()
    
di = [(-1,0),(1,0),(0,1),(0,-1)]
def sol(s,g):
    h = s[0] ; w = s[1]
    gh,gw = g
    d = [[math.inf for _ in range(W)] for _ in range(H)]
    cand = []
    dis = 0
    while True:
        for each in di:
            dh , dw = each
            if h + dh>=0 and h + dh<H and w + dw>=0 and w + dw<W and maze[h+dh][w+dw]=="." and d[h+dh][w+dw]>dis+1:
                if h+dh ==gh and w+dw ==gw:
                    return dis+1
                cand.append((h+dh, w+dw))
                d[h+dh][w+dw] = dis +1
        if len(cand)==0:
            break
        h , w =cand.pop(0)
        dis = d[h][w]
    return d[g[0]][g[1]]

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]=="#" or maze[gh][gw]=="#":
                    continue
                ans = max(ans, sol((sh,sw),(gh,gw)))
print(ans)