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: Accepted

Solution code:
# ABC151 D
si = lambda: input()
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))
from collections import deque
def bfs(sy,sx):
    q = deque([[sy,sx]])
    visited[sy][sx]=0
    while q:
        y,x = q.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            ny,nx = y+j,x+k
            if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="#":
                continue
            if path[ny][nx]=="." and visited[ny][nx]==-1:
                visited[ny][nx]=visited[y][x]+1
                q.append([ny,nx])
    ret=-1
    for i in range(h):
        for j in range(w):
            ret=max(visited[i][j],ret)
    return ret
h,w=nm()
path=[input() for i in range(h)]
visited = [[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
    for j in range(w):
        if path[i][j]=='#':
            continue
        sy,sx=i,j
        visited = [[-1]*w for i in range(h)]
        t=bfs(sy,sx)
        ans=max(t,ans)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: UTF-8 -*-
def sol():
    h,w=map(int,input().split())
    d=[]
    for i in range(h):
        s=input()
        d.append(s)
    x=h*w
    p=[[x+1]*x for i in range(x)]
    for i in range(x):
        for j in range(i+1):
            if i==j:
                p[i][j]=0
                p[j][i]=0
            ih,iw,jh,jw=i//w,i%w,j//w,j%w
            if d[ih][iw]==d[jh][jw]=="." and ih==jh and abs(iw-jw)==1:
                p[i][j]=1
                p[j][i]=1
            if d[ih][iw]==d[jh][jw]=="." and iw==jw and abs(ih-jh)==1:
                p[i][j]=1
                p[j][i]=1


    for i in range(x):
        ih,iw=i//w,i%w
        if d[ih][iw]!=".": continue
        for j in range(x):
            ih,iw=i//w,i%w
            jh,jw=j//w,j%w
            if d[jh][jw]!=".": continue
            for k in range(j+1):
                ih,iw=i//w,i%w
                jh,jw=j//w,j%w
                kh,kw=k//w,k%w
                if d[kh][kw]==".":
                    p[j][k]=min(p[j][k],p[j][i]+p[i][k])
                    p[k][j]=min(p[k][j],p[j][i]+p[i][k])
    ans=0
    for i in p:
        for j in i:
            if j<x+1:
                ans=max(ans,j)
    print(ans)

if __name__=="__main__":
    sol()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())

maze = [list(input()) for _ in range(h)]
#print(maze)
ans = 0
def solve(sx, sy):
    INF = 1000000
    reached = [[INF for _ in range(w)] for _ in range(h)]
    reached[sx][sy] = 0
    d = deque()
    d.append([sx, sy])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]    
    while d:
        x, y = d.popleft()
        for i in range(4):
            next_y = y + dy[i]
            next_x = x + dx[i]
            if next_x < 0 or next_x > h - 1 or next_y < 0 or next_y > w - 1:
                continue
            if maze[next_x][next_y] == "#":
                continue
            if reached[next_x][next_y] != INF:
                continue
            d.append([next_x, next_y])
            reached[next_x][next_y] = reached[x][y] + 1
    gl = 0
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                gl = max(gl, reached[i][j])
    return gl

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            res = solve(i, j)
            ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
def warshall_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d

H, W = map(int,input().split())
N = H * W

d = [[float("inf") for i in range(N)] for i in range(N)] 

M = [[1 for i in range(W+1)] for i in range(H+1)]
for i in range(H):
    m = input().strip()
    for j in range(W):
        if m[j] == '.':
            M[i][j] = 0

for i in range(H):
    for j in range(W):
        if M[i][j] == 0:
            d[W*i+j][W*i+j] = 0
            if M[i][j+1] == 0:
                d[W*i+j][W*i+j+1] = 1
                d[W*i+j+1][W*i+j] = 1
            if M[i+1][j] == 0:
                d[W*i+j][W*(i+1)+j] = 1
                d[W*(i+1)+j][W*i+j] = 1

o = warshall_floyd(d, N)
ans = 0
for i in range(N):
    for j in range(N):
        if o[i][j] != float('inf'):
            ans = max(ans, o[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 

 
H,W = map(int,readline().split())
grid = np.full((H+2,W+2),b'#',dtype='S1')
grid[1:-1,1:-1] = np.frombuffer(read(),'S1').reshape(H,-1)[:,:W]
INF = 400
def shortest(grid, start, cost=0):
    dist = np.array([[INF for _ in range(W+2)] for _ in range(H+2)])
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    st = [(cost, start)]
    dist[start[0]][start[1]]=0
    while(st):
        c, [sx, sy] = heappop(st)
        for a, b in zip(dx, dy):
            x = sx + a
            y = sy + b
            if grid[x][y]==b'#':
              continue
            dxy = dist[sx][sy] + 1
            if dist[x][y] <= dxy:
                continue
            dist[x][y] = dxy
            heappush(st, (dist[x][y], [x, y]))
    return np.max(dist[dist<INF])

m=0
for i in range(1,H+1):
  for j in range(1,W+1):
    if grid[i,j]==b'#':
      continue
    tm = shortest(grid, [i, j])
    if m < tm:
      m=tm
print(m)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
field=[]
field.append([True for i in range(w+2)])
start=[]
for i  in range(h):
    s=input()
    sub=[True]
    for j in range(w):
        if s[j]=="#":
            sub.append(True)
        else:
            sub.append(False)
            start.append((i+1,j+1))
    
    sub.append(True)
    field.append(sub)

            
        
    
field.append([True for i in range(w+2)])

from collections import deque
import copy
dis=[]
for i in range(len(start)):

        fields=copy.deepcopy(field)
        d=deque()
        e=deque()
        distance=0
        fields[start[i][0]][start[i][1]]=True

        d.append((start[i][0],start[i][1]))
        while d:
            for some in d:
                index1,index2=some[0],some[1]
                if fields[index1-1][index2]==False:
                    fields[index1-1][index2]=True
                    e.append((index1-1,index2))
                if fields[index1+1][index2]==False:
                    fields[index1+1][index2]=True
                    e.append((index1+1,index2))
                if fields[index1][index2+1]==False:
                    fields[index1][index2+1]=True
                    e.append((index1,index2+1))
                if  fields[index1][index2-1]==False:
                    fields[index1][index2-1]=True
                    e.append((index1,index2-1))
            distance+=1
            d=e
            e=deque()

        dis.append(distance)
    


print(max(dis)  -1)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = []
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
for _ in range(H):
  S.append(input())

ans = 0
for si in range(H):
  for sj in range(W):
    if S[si][sj] == "#":
      continue
    dist = [[-1 for _ in range(W)] for _ in range(H)]
    dist[si][sj] = 0
    queue = [[si, sj]]
    while len(queue) > 0:
      q = queue.pop(0)
      i = q[0]
      j = q[1]
      for dir in range(4):
        ni = i + di[dir]
        nj = j + dj[dir]
        if ni < 0 or ni >= H or nj < 0 or nj >= W:
          continue
        if S[ni][nj] == "#":
          continue
        if dist[ni][nj] == -1:
          dist[ni][nj] = dist[i][j] + 1
          queue.append([ni, nj])
    for i in range(H):
      for j in range(W):
        ans = max(ans, dist[i][j])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]
 
ans = 0
 
for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]
 
        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0
 
        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s="#"*W+"".join("#"+input()for _ in range(H))
f=-~W*-~H
d=[[0]*f for _ in range(f)]
for i in range(W,f-1):
 d[i][i-1]=s[i]==s[i-1]=="."
 d[i][i-W-1]=s[i]==s[i-W-1]=="."
from scipy.sparse.csgraph import csgraph_from_dense as C,floyd_warshall as F
import numpy as p
Q=F(C(d),directed=False)
print(int(max(Q[Q!=p.inf])))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict

H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]

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

def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: 0)    #距離

    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=L[(fro_x,fro_y)]+1
                    q.append((to_x,to_y))

    return max(L.values())

ans=0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans=max(ans,bfs((h,w)))

print ans

Submission status: Accepted

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

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    Visit[start]=1
    L=defaultdict(lambda: float("inf"))    #距離
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and (to_x,to_y) not in Visit:
                    Visit[to_x,to_y]=1
                    L[(to_x,to_y)]=min(L[(to_x,to_y)],L[(fro_x,fro_y)]+1)
                    q.append((to_x,to_y))
    if len(L.values())==0:
        return 0
    else:
        return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans=max(ans,bfs((h,w)))
 
print ans

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
s=[]
for i in range(h):
    for j in range(w):
        if l[i][j]=='.':
            s.append([i,j])
def solve(s):
    v=[[0 for i in range(w)] for j in range(h)]       
    v[s[0]][s[1]]=1
    mc=0
    q=[[s,0]]
    while len(q):
        p=q.pop(0)
        x=p[0][0]
        y=p[0][1]
        c=p[1]
        k=[[0,1],[0,-1],[1,0],[-1,0]]
        for j in k:
            nx=x+j[0]
            ny=y+j[1]
            if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
                v[nx][ny]=1
                q.append([[nx,ny],c+1])
                if mc<=c+1:
                    mc=c+1
                    # ms=[nx,ny]
    return mc 
ans=0
for i in s:
    ans=max(ans,solve(i))
print(ans)
exit()

v=[[0 for i in range(w)] for j in range(h)]       
v[ms[0]][ms[1]]=1
ans=0
q=[[ms,0]]
while len(q):
    p=q.pop(0)
    x=p[0][0]
    y=p[0][1]
    c=p[1]
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    for j in k:
        nx=x+j[0]
        ny=y+j[1]
        if 0<=nx<h and 0<=ny<w and l[nx][ny]=='.' and v[nx][ny]==0:
            v[nx][ny]=1
            q.append([[nx,ny],c+1])
            ans=max(ans,c+1)
                #ms=[nx,ny]
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
grid = []
inf = 400
for i in range(h):
    grid.append(list(input()))
graph = [[0 for i in range(h*w)] for j in range(h*w)]
for i in range(h):
    for j in range(1,w):
        u = i * w + j - 1
        v = i * w + j
        if grid[i][j-1] != '#' and grid[i][j] != '#':
            graph[u][v] = graph[v][u] = 1
for i in range(w):
    for j in range(1,h):
        u = (j - 1) * w + i
        v = j * w + i
        if grid[j-1][i] != '#' and grid[j][i] != '#':
            graph[u][v] = graph[v][u] = 1
distance = [[inf for i in range(h*w)] for j in range(h*w)]
for i in range(h*w):
    for j in range(w*h):
        if graph[i][j] == 1:
            distance[i][j] = 1
    distance[i][i] = 0
for k in range(h*w):
    for j in range(w*h):
        for i in range(w*h):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
ans = 0
for i in range(h*w):
    for j in range(h*w):
        if distance[i][j] != inf:
            ans = max(ans, distance[i][j])
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque
from collections import defaultdict
 
H,W=map(int, sys.stdin.readline().split())
S=[ sys.stdin.readline().strip() for _ in range(H) ]
 
D=[(1,0),(-1,0),(0,1),(0,-1)]
 
def bfs(start):
    Visit={}
    q=deque()
    q.append(start)
    L=defaultdict(lambda: float("inf")) 
    L[start]=0
 
    while q:
        fro_x,fro_y=q.popleft()
        for dx,dy in D:
            to_x=fro_x+dx
            to_y=fro_y+dy
            alt=L[(fro_x,fro_y)]+1
            if 0<=to_x<H and 0<=to_y<W:
                if S[to_x][to_y]=="." and alt<L[(to_x,to_y)]:
                    L[(to_x,to_y)]=alt
                    q.append((to_x,to_y))
    return max(L.values())
 
ans=0
for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans=max(ans,bfs((h,w)))
print ans

Submission status: Accepted

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

vec = [(-1,0),(1,0),(0,1),(0,-1)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":continue
        stack = [(i,j)]
        visited = [[0]*w for i in range(h)]
        a[i][j] = 0
        
        while stack:
            next = []
            for x,y in stack:
                
                if visited[x][y]:continue

                visited[x][y] = 1
                

                for tx,ty in vec:
                    nx = x+tx
                    ny = y+ty
                    if nx < 0 or ny <0 or nx >=h or ny >=w:continue
                    if field[nx][ny] == "#" :continue
                    if visited[nx][ny]:continue
                    next.append((nx,ny))
                    a[nx][ny] = a[x][y] + 1
                    
                    
            stack = next
   
        for k in range(h):
            ans = max(ans,max(a[k]))
            a[k] = [0]*w
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]
 
 
def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    
    ans = 0
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#': continue
    
            q = []
            q.append([i, j])
            dist = [[-1 for _ in range(w+5)] for _ in range(h + 5)]
            dist[i][j] = 0
            M = 0
            while q:
                x, y = q[0]
                q.pop(0)
                for p in range(4):
                    nx, ny = x + dx[p], y + dy[p]
                    if 0 <= nx < h and 0 <= ny < w:
                        if dist[nx][ny]==-1 and s[nx][ny] == '.':
                            q.append([nx, ny])
                            dist[nx][ny] = dist[x][y] + 1
                            if M<dist[nx][ny]:
                                M = dist[nx][ny]
            ans = max(ans,M)
    print(ans)
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    judge = [[False]*W for _ in range(H)]
    judge[i][j]=True
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if judge[h][w]:
          continue
        A[h][w]=c
        judge[h][w]=True
        q.append([h,w])
        
    A = [a for b in A for a in b if a!=inf]
    ans = max(ans,max(A))
    
print(ans)

Submission status: Accepted

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**2 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**2 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]
        olddist = dist[x][y]
        bb[x][y] = '#'
        for elem in move:
            dx = elem[0]
            dy = elem[1]
            xx = x+dx
            yy = y+dy
            if xx>=0 and xx<= H-1 and yy>=0 and yy<=W-1:
                if bb[xx][yy] != '#':
                    if dist[xx][yy] == 10**2:
                        dist[xx][yy] = olddist + 1
                        far = max([far,olddist+1])
                        q.put((xx,yy))
        if q.empty():
            break
    return far
res = 0
while 1:
    ttt = time.time()
    if sss-ttt >= 1.8:
        break
    now = qq.get()
    res = max([res, BFS(now, copy.deepcopy(b))])
    if qq.empty():
        break
print(res)

Submission status: Accepted

Solution code:
from collections import deque
import copy

def bfs(grid, start):
    H, W = len(grid), len(grid[0])
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()
 
        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 distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))

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
        tmpmaze = copy.deepcopy(maze)
        steps = bfs(tmpmaze, [i, j])
        if(steps > res):
            res = steps
print(res)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
maze = []
def mazecal(hs,ws):
    calmaze = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque([[hs,ws,0]])
    smax = 0
    while len(que)!=0:
        cur = que.popleft()
        calmaze[cur[0]][cur[1]] = cur[2]
        smax = max(smax,cur[2])
        if cur[0]>0   and maze[cur[0]-1][cur[1]]==0:
            if calmaze[cur[0]-1][cur[1]] ==-1 or calmaze[cur[0]-1][cur[1]] > cur[2]+1:
                calmaze[cur[0]-1][cur[1]] = cur[2]+1
                que.append([cur[0]-1,cur[1],  cur[2]+1])
        if cur[0]<h-1 and maze[cur[0]+1][cur[1]]==0:
            if calmaze[cur[0]+1][cur[1]] ==-1 or calmaze[cur[0]+1][cur[1]] > cur[2]+1:
                calmaze[cur[0]+1][cur[1]] = cur[2]+1
                que.append([cur[0]+1,cur[1],  cur[2]+1])
        if cur[1]>0   and maze[cur[0]][cur[1]-1]==0:
            if calmaze[cur[0]][cur[1]-1] ==-1 or calmaze[cur[0]][cur[1]-1] > cur[2]+1:
                calmaze[cur[0]][cur[1]-1] = cur[2]+1
                que.append([cur[0]  ,cur[1]-1,cur[2]+1])
        if cur[1]<w-1 and maze[cur[0]][cur[1]+1]==0:
            if calmaze[cur[0]][cur[1]+1] ==-1 or calmaze[cur[0]][cur[1]+1] > cur[2]+1:
                calmaze[cur[0]][cur[1]+1] = cur[2]+1
                que.append([cur[0]  ,cur[1]+1,cur[2]+1])
    return smax

for i in range(h):maze.append([0 if c=='.' else 1 for c in input()])
gmax = 0
for i in range(h):
    for j in range(w):
        if maze[i][j]==0:gmax = max(gmax,mazecal(i,j))
print(gmax)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s="#"*W+"".join("#"+input() for _ in range(H))
f=(W+1)*(H+1)
d=[[0]*f for _ in range(f)]
for i in range(W,f-1):
 d[i][i-1]=s[i]==s[i-1]=="."
 d[i][i-W-1]=s[i]==s[i-W-1]=="."
from scipy.sparse.csgraph import csgraph_from_dense as C,floyd_warshall as F
Q=F(C(d),directed=False)
r=-1
for q in Q:
 for x in q:
  if f>x:
   r=max(r,int(x))
print(r)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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


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

        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 distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
        if not queue:
            return distance[x][y]


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

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque

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

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


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

        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 distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
        if not queue:
            return distance[x][y]


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

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque
from itertools import product

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

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


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

        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 distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


answer = 0
for i, j in product(range(H), range(W)):
    if S[i][j] == '#':
        continue

    tmp = bfs(S, (i, j))
    if tmp > answer:
        answer = tmp

print(answer)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
 
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return [list(map(int, input().split())) for _ in range(n)]
 
 
def main():
    h,w = inpm()
    maze = []
    for _ in range(h):
        s = list(input())
        maze.append(s)
    ans = 0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '#':
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = []
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    [qx,qy]=que[0]
                    que.pop(0)
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append((nx,ny))
                ans = max(ans,M)
    print(ans)
 
 
if __name__ == "__main__":
    main()