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:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

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

    s = []
    for _ in range(h):
        s.append(list(input())[:-1])

    ans = 0

    from collections import deque
    import copy

    reach_queue = deque()
    next_queue = deque()

    not_visited = [[True]*w for _ in range(h)]

    for i in range(w):
        for j in range(h):
            if s[j][i] == '.':
                next_queue.append((i, j))
                not_visited = [[True]*w for _ in range(h)]
                not_visited[j][i] = False
                cnt = -1
                while True:
                    if len(next_queue) == 0:
                        ans = max([ans, cnt])
                        break
                    reach_queue = copy.deepcopy(next_queue)
                    next_queue = deque()
                    while True:
                        if len(reach_queue) == 0:
                            cnt += 1
                            break
                        new_i, new_j = reach_queue.popleft()
                        if new_i != 0:
                            if s[new_j][new_i-1] == '.' and not_visited[new_j][new_i-1]:
                                not_visited[new_j][new_i-1] = False
                                next_queue.append((new_i-1, new_j))
                        if new_j != 0:
                            if s[new_j-1][new_i] == '.' and not_visited[new_j-1][new_i]:
                                not_visited[new_j-1][new_i] = False
                                next_queue.append((new_i, new_j-1))
                        if new_i != w-1:
                            if s[new_j][new_i+1] == '.' and not_visited[new_j][new_i+1]:
                                not_visited[new_j][new_i+1] = False
                                next_queue.append((new_i+1, new_j))
                        if new_j != h-1:
                            if s[new_j+1][new_i] == '.' and not_visited[new_j+1][new_i]:
                                not_visited[new_j+1][new_i] = False
                                next_queue.append((new_i, new_j+1))

    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import queue

row, col = map(int, input().split(' '))
maze = [list(input()) for _ in range(row)]

                
def BPS(si, sj):
    done = [[0 for _ in range(col)] for _ in range(row)]
    q = queue.Queue()
    q.put((si, sj, 0))
    around = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    maxv = 0
    while not q.empty():
        i, j, cnt = q.get()
        done[i][j] = 1
        for ar in around:
            di, dj = ar[0], ar[1]
            i_n, j_n = i + di, j + dj
            if (i_n >= 0 and i_n < row and j_n >= 0 and j_n < col) == False:
                continue
            if maze[i_n][j_n] == '#':
                continue
            if done[i_n][j_n] == 1:
                continue
            if done[i_n][j_n] == 2:
                continue
            maxv = max(maxv, cnt + 1)
            q.put((i_n, j_n, cnt + 1))
            done[i_n][j_n] = 2
        
    return maxv
            
            
def main():        
    maxv = 0
    for i in range(row):
        for j in range(col):
            if maze[i][j] == '#':
                continue
            maxv = max(maxv, BPS(i,j))
    print(maxv)
                    
                
                    
    
main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(si, sj):
    q = deque()
    q.append([si, sj, 0])
    used = set()
    used.add((si,sj))
    ans = MAX_VALUE
    while len(q) > 0:
        prvi, prvj, d = q.popleft()
        for i, j in [[prvi-1, prvj], [prvi+1, prvj], [prvi, prvj-1], [prvi, prvj+1]]:
            if (i,j) in used:
                continue
            if grid[j][i] == '#':
                ans = min(ans, d)
                continue
            else:
                q.append([i,j,d+1])
                used.add((i,j))
    return d

H, W = map(int, input().split())
MAX_VALUE = (H+2) * (W+2) + 1
grid = ['#'*(W+2)] + [ '#' + input() + '#' for _ in range(H)] + ['#'*(W+2)]

ans = 1
for j in range(1, H + 1):
    for i in range(1, W + 1):
        if grid[j][i] == '#':
            continue
        res = bfs(i, j)
        if res != MAX_VALUE:
            ans = max(ans, res)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = "#"*(W+2)
for _ in range(H):
    s+="#"+input().strip()+"#"
s += "#"*(W+2)

#for i, c in enumerate(s):
#    print(i, c)
ff = (W+2)*(H+2)
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall
dp = [[-1]*ff for _ in range(ff)]
for i in range(1, H+1):
    for j in range(1, W+1):
        u = j+(W+2)*i
        v = j+(W+2)*(i-1)
        if s[u] == "." and s[u-1] == ".":
#            print(u,u-1)
            dp[u][u-1] = 1
        if s[u] == "." and s[v] == ".":
#            print(u,v)
            dp[u][v] = 1
#print(dp)
G = csgraph_from_dense(dp,  null_value=-1)
Q = floyd_warshall(G, directed=False)
r = -1
for q in Q:
    for x in q:
        if x < 10**9:
            r = max(r, int(x))
print(r)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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

ans=0

for hh in range(h):
 for ww in range(w):
  dist=[[-1]*(w+1) for i in range(h+1)]
  c=copy.deepcopy(ss)
  xx=c[hh][ww]
  if xx=='#':
   continue
  dist[hh][ww]=0
  dq=deque()
  dq.append((hh,ww))
  c[hh][ww]='#'
  while dq:
   y,x=dq.popleft()
   for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
    nx=x+dx
    ny=y+dy
    if 0<=nx<w and 0<=ny<h and c[ny][nx]!='#':
     dq.append((ny,nx))
     c[ny][nx]='#'
     dist[ny][nx]=dist[y][x]+1
  for i in dist:
   ans=max(ans,max(i))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

H, W = rl()
grid = [list(rs()) for _ in range(H)]
INF = 1000

def bfs(sx, sy):
    d = [[INF] * W for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque()
    que.append((sx, sy))
    d[sy][sx] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]                
            if 0 <= ny and ny <= H-1 and 0 <= nx and nx <= W-1 and \
                    grid[ny][nx] != '#' and d[ny][nx] == INF:
                d[ny][nx] = d[p[1]][p[0]] + 1
                que.append((nx, ny))
    dis = [[0 if x == INF else x for x in row] for row in d]
    return max([max(y) for y in dis])

answer = 0

for s in range(H):
    for t in range(W):
        if grid[s][t] == '#':
            continue
        distance = bfs(t, s)
        if distance > answer:
            answer = distance

print(answer)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=['#'*(w+2)]
s+=['#'+input()+'#' for _ in range(h)]
s.append('#'*(w+2))
h+=2
w+=2
p=[[1,0],[0,1],[-1,0],[0,-1]]
st=[]
cnt=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            st.append((i,j))
            cnt+=1
ans=0
for i in range(cnt):
    n=[st[i]]
    route={n[0]:0}
    c=1
    count=1
    while c<cnt:
        n2=[]
        for i in n:
            for j in p:
                np=(i[0]+j[0],i[1]+j[1])
                if s[np[0]][np[1]]=='.' and route.get(np,-1)==-1:
                    n2.append(np)
                    route[np]=count
                    c+=1
        n=n2
        count+=1
    ans=max(ans,count-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

mymap = []
for h in range(H):
    mylist = list(input())
    mymap += [mylist]
#print(myAC)
#print(myWA)
#print(mymap)

d = [ [0 for w in range(W)] for h in range(H) ]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
INF = -999

def bfs(a, b):
    mymax = 0
    #探索結果を示す配列dについて，すべての地点をINFで初期化
    for h in range(H):
        for w  in range(W):
            d[h][w] = INF
    #スタート地点の処理（ここでは x = 0, y = 0 の地点がスタート地点）
    #print(d)
    que = deque([[a,b]])
    d[a][b] = 0
    #queが空になるまで処理を行う
    while que:
        y, x = que.popleft() #左側から取り出す
        #4方向の探索
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0 <= ny and ny < H and 0 <= nx and nx < W and mymap[ny][nx] != '#' and d[ny][nx] == INF:
                que.append([ny,nx])
                d[ny][nx] = d[y][x] + 1
                if d[ny][nx] > mymax:
                    mymax = d[ny][nx]
    #print(d)
    return mymax

mymax = 0
for h in range(H):
    for w in range(W):
        if mymap[h][w] != '#':
            mine = bfs(h, w)
            #print(mine)
            if mymax < mine:
                mymax = mine

print(mymax)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True


def dijkstra(edge,st):
    # edge=[[(v_to,dist_to_v),...],[],...]
    # initialize: def: d=dist(st,i), prev=[previous vertex in minimum path], q[]
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    # calc
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return [i for i,j in d],prev

def cv(i,j):
    return i*w+j
def rcv(x):
    return x//w,x%w




ans=0

h,w=LI()

mp=[[1]*(w+2)]
for i in range(h):
    mp.append([1]+[1 if i=='#' else 0 for i in input()]+[1])
mp.append([1]*(w+2))
h+=2
w+=2

n=h*w

def bfs(sh,sw):
    g=[[-1]*w for i in range(h)]
    dd=[(0,1),(0,-1),(1,0),(-1,0)]#+[(1,1),(1,-1),(-1,-1),(-1,1)]
    
    q=deque()
    q.append((sh,sw))
    g[sh][sw]=0
    while q:
        ch,cw=q.popleft()
        
        for di,dj in dd:
            if mp[ch+di][cw+dj]==0 and g[ch+di][cw+dj]==-1:
                q.append((ch+di,cw+dj))
                g[ch+di][cw+dj]=g[ch][cw]+1
    MG=0
    for i in range(h):
        MG=max(MG,max(g[i]))
        
    
    return MG

ans=0
for i in range(1,h-1):
    for j in range(1,w-1):
        if mp[i][j]==1:continue
        ans=max(bfs(i,j),ans)

print(ans)

Submission status: Accepted

Solution code:
def Warshall_Floyd(edges,N):
    for k in range(N):
        for i in range(N):
            for j in range(N):
                edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
    return edges


def main():
    H,W = map(int,input().split())
    ls = [list(input()) for _ in range(H)]
    for i in range(H):
        ls[i].insert(0,"#")
        ls[i].append("#")
    ls.append(["#" for _ in range(W+2)])
    ls.insert(0,["#" for _ in range(W+2)])
    graph = [[float("inf") for _ in range(H*W)] for _ in range(H*W)]

    for i in range(1,H+1):
        for j in range(1,W+1):
            if ls[i][j]==".":
                # ue
                if ls[i-1][j]==".":
                    graph[(i-1)*W+(j-1)][(i-2)*W+(j-1)] = 1
                    graph[(i-2)*W+(j-1)][(i-1)*W+(j-1)] = 1
                # migi
                if ls[i][j+1]==".":
                    graph[(i-1)*W+(j-1)][(i-1)*W+j] = 1
                    graph[(i-1)*W+j][(i-1)*W+(j-1)] = 1
                # sita
                if ls[i+1][j]==".":
                    graph[(i-1)*W+(j-1)][i*W+(j-1)] = 1
                    graph[i*W+(j-1)][(i-1)*W+(j-1)] = 1
                # hidari
                if ls[i][j-1]==".":
                    graph[(i-1)*W+(j-1)][(i-1)*W+(j-2)] = 1
                    graph[(i-1)*W+(j-2)][(i-1)*W+(j-1)] = 1
                else:
                    pass

    a = Warshall_Floyd(graph,H*W)
    for i in range(H*W):
        for j in range(H*W):
            if a[i][j]==float("inf"):
                a[i][j]=0
    for i in range(H*W):
        a[i][i] = 0

    mx = 0
    for i in a:
        mx = max(mx,max(i))
    print(mx)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

x=[["a"]*W for i in range(H)]
y=[[set() for i in range(W)] for j in range(H)]

done=set()
for i in range(H):
  x[i]=input()

for i in range(H):
  for j in range(W):
    if x[i][j]==".":
      if i>0:
        if x[i-1][j]==".":
          y[i][j].add(W*(i-1)+j)
      if i<H-1:
        if x[i+1][j]==".":
          y[i][j].add(W*(i+1)+j)
      if j>0:
        if x[i][j-1]==".":
          y[i][j].add(W*(i)+j-1)
      if j<W-1:
        if x[i][j+1]==".":
          y[i][j].add(W*(i)+j+1)
maxleng=0          
for i in range(H):
  for j in range(W):
    done={W*i+j}
    leng=0
    nxt=[set() for k in range(H*W)]
    nxt[0]=set(y[i][j])
    for k in range(H*W):
      done|=nxt[k]
      while len(nxt[k])>0:
        a=nxt[k].pop()
        nxt[k+1]|=y[a//W][a%W]
      nxt[k+1]=set(nxt[k+1]&(nxt[k+1]^done))
      if len(nxt[k+1])==0:
        if maxleng<k:
          maxleng=k
        break
print(maxleng+1)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
ans = 0
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]
for h in range(H):
    for w in range(W):
        if maze[h][w] == '#':
            continue
        queue = deque()
        depth = [[-1] * W for i in range(H)]
        depth[h][w] = 0
        queue.append((h, w))
        while queue:
            i, j = queue.popleft()
            for di, dj in move:
                ni, nj = i+di, j+dj
                if 0 <= ni < H and 0 <= nj < W and maze[ni][nj] == '.' and depth[ni][nj] == -1:
                    queue.append((ni, nj))
                    depth[ni][nj] = depth[i][j] + 1
        ans = max(ans, max(max(d) for d in depth))
print(ans)

Submission status: Accepted

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

def main():
    h,w=map(int,input().split())
    MAP=[['#']*(w+2)]
    for _ in range(h):
        S=list(input().strip())
        S=['#']+S+['#']
        MAP.append(S)
    MAP.append(['#']*(w+2))
    #print(MAP)
    ans=0
    
    def Dist(k,l):
        delta=[[1,0],[0,1],[-1,0],[0,-1]]
        Dist=[[float('inf')]*(w+2) for _ in range(h+2)]
        Dist[k][l]=0
        Visited=[[False]*(w+2) for _ in range(h+2)]
        Visited[k][l]=True
        q=deque()
        q.append((k,l))
        while q:
            y,x=q.popleft()
            for dx,dy in delta:
                #print(y+dy,x+dx)
                if Dist[y+dy][x+dx]==float('inf') and MAP[y+dy][x+dx]=='.':
                    q.append((y+dy,x+dx))
                    Dist[y+dy][x+dx]=Dist[y][x]+1
        ret=0
        for i in range(h+2):
            for j in range(w+2):
                if Dist[i][j]==float('inf'):
                    continue
                ret=max(ret,Dist[i][j])
        return ret
        
    for i in range(1,h+1):
        for j in range(1,w+1):
            if MAP[i][j]=='#':
                continue
            dist=Dist(i,j)
            ans=max(ans,dist)
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
h, w = [int(v) for v in input().split()]
field = [list(input()) for i in range(h)]

def bfs(s, t):
    si, sj = s
    ti, tj = t
    if field[si][sj] == "." and field[ti][tj] == ".":

        search_field = [ [ -1 for i in range(w) ] for j in range(h) ]
        search_list = [s]
        turn = 0
        search_field[si][sj] = turn
        
        
        while search_list:
            turn += 1
            new_search_list = []
            for p in search_list:
                pi, pj = p
                
                for q in adjust_list:
                    qi, qj = q
                    if 0 <= pi+qi < h and 0 <= pj+qj < w:
                        if search_field[pi+qi][pj+qj] == -1 and field[pi+qi][pj+qj] == ".":
                            new_search_list.append((pi+qi,pj+qj))
                            search_field[pi+qi][pj+qj] = turn
            search_list = new_search_list
            if search_field[ti][tj] != -1:
                break
        return search_field[ti][tj]
    else:
        return -1
    

ans = 0
coodinate = [ (i, j) for i in range(h) for j in range(w) ]
k = h*w

for i in range(k-1):
    for j in range(i+1, k):
        ans = max(ans, bfs(coodinate[i], coodinate[j]))
print(ans)

Submission status: Accepted

Solution code:
import copy
height, width = map(int, input().split())
field = []
for i in range(height):
    e = list(input())
    field.append(e)

dir = ((0, 1), (1, 0), (-1, 0), (0, -1))

ans = 0

for start_y in range(height):
    for start_x in range(width):
        if field[start_y][start_x] == "#":
            pass
        else:
            new_field = copy.deepcopy(field)
            que1 = [(start_y, start_x)]
            cnt = 0
            new_field[start_y][start_x] = 0
            while True:
                que2 = []
                cnt += 1
                for y, x in que1:
                    for i, j in dir:
                        if y + i >= 0 and y + i < height and x + j >= 0 and x + j < width:
                            if new_field[y + i][x + j] == ".":
                                que2.append((y + i, x + j))
                                new_field[y + i][x + j] = cnt
                que1 = que2
                if len(que2) == 0:
                    ans = max(ans, cnt - 1)
                    break
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
a=['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
from collections import deque
ans=0
for p in range(h):
  for q in range(w):
    d=deque()
    m=0
    if a[p+1][q+1]=='.':
      d.append([p+1,q+1])
      c=[[10000]*w for _ in range(h)]
      c[p][q]=1
      di=[[0,1],[1,0],[-1,0],[0,-1]]
      while d:
        g=d.popleft()
        for i in di:
          x=g[0]+i[0]
          y=g[1]+i[1]
          if a[x][y]=='.':
            if c[x-1][y-1]==10000:
              d.append([x,y])
              c[x-1][y-1]=c[g[0]-1][g[1]-1]+1
      for i in range(h):
        for j in range(w):
          if c[i][j]!=10000:
            m=max(m,c[i][j])
    ans=max(ans,m)
print(ans-1)

Submission status: Accepted

Solution code:
import queue

def bfs(i,j,d):
    already[i][j] = d
    next = []
    for a,b in [[-1,0], [1,0],[0,1],[0,-1]]:
        if 0<=i+a<H and 0<=j+b<W and A[i+a][j+b]=='.' and already[i+a][j+b]==-1:
            if [i+a,j+b] not in next:
                next.append([i+a,j+b])
    for ni, nj in next:
        bfs(ni,nj,d+1)




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


ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j]!='.':
            continue
        q = queue.Queue()
        q.put((i,j))
        already = [[-1]*W for _ in range(H)]
        already[i][j] = 0
        while not q.empty():
            x,y = q.get()
            for a,b in [[-1,0], [1,0],[0,1],[0,-1]]:
                if 0<=x+a<H and 0<=y+b<W and A[x+a][y+b]=='.' and already[x+a][y+b]==-1:
                    q.put((x+a, y+b))
                    already[x+a][y+b] = already[x][y]+1
        t = 0
        for al in already:
            t = max(t, max(al))

        ans = max(ans, t)

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
# from datetime import date, timedelta
# from heapq import *
import heapq
import math
from collections import defaultdict, Counter, deque
from bisect import *
import itertools
import fractions
import sys
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
# input = sys.stdin.readline

def make_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)

    divisors.sort()
    return divisors





def main():
    
    # n, m = map(int, input().split())
    # ps = [list(input().split()) for i in range(m)]

    # c = 1
    # ac, wa = 0, 0
    # d = defaultdict(int)
    # for i in range(m):
    #     if ps[i][1] == "AC" and d[int(ps[i][0])] == 0:
    #         ac += 1
    #         d[int(ps[i][0])] = 1
    #     elif ps[i][1] == "WA" and d[int(ps[i][0])] == 0:
    #         wa += 1
    # print(ac,wa)
            
    
    h, w = map(int, input().split())
    s = [input() for i in range(h)]



    l = []
    for i in range(h):
        for j in range(w):
            l.append((i, j))

    maze = s
    def Dijkstra_search(sx, sy, c):
        H = h
        W = w
        visited = [[False for i in range(W)] for j in range(H)]
        d = [[float("inf") for i in range(W)] for j in range(H)]  # now cost
        d[sx][sy] = 0

        queue = []
        heapq.heappush(queue, (0, (sx, sy)))
        while len(queue):
            cost, (x, y) = heapq.heappop(queue)


            if visited[x][y]:
                continue
            visited[x][y] = True

            for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
                nx = x + dx
                ny = y + dy
                if nx >= 0 and ny >= 0 and nx < H and ny < W:
                    if visited[nx][ny] or maze[nx][ny] == "#":
                        continue

                    vd = 1 + cost
                    if d[nx][ny] > vd:
                        d[nx][ny] = vd
                        heapq.heappush(queue, (vd, (nx, ny)))

        ret = 0
        for i in range(h):
            for j in range(w):
                if s[i][j] == "#":
                    continue
                ret = max(d[i][j],ret)
        return ret
    
    # ans = 0
    # for ll in itertools.combinations(l, 2):
    #     d = deque()
    #     d.append(ll[0])
    #     visited = [[0 for i in range(w)] for j in range(h)]
    #     while len(d) != 0:
    #         x, y = d.pop()
    #         if x == ll[1][0] and y == ll[1][1]:
    #             break
    #         for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
    #             nx = x + i
    #             ny = y + j
    #             if nx < 0 or ny < 0 or nx > h - 1 or ny > w - 1:
    #                 continue
    #             if s[nx][ny] == "#":
    #                 continue
    #             if visited[nx][ny] != 0:
    #                 continue
    #             d.append((nx, ny))
    #             visited[nx][ny] =visited[x][y] + 1
        

    #     print(ll, visited, visited[ll[1][0]][ll[1][1]])
    #     ans = max(visited[ll[1][0]][ll[1][1]], ans)
    ans = 0
    for v in l:
        if s[v[0]][v[1]] == "#":
            continue
        #print(Dijkstra_search(v[0][0], v[0][1], v[1][0], v[1][1], 1))
        ans = max(ans , Dijkstra_search(v[0],v[1],1))
    print(ans)
                


                
        




    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    H,W = mis()
    S = tuple(input() for _ in range(H))
    reached = set()
    q = deque()
    ans = 0
    def check():
        nonlocal ans
        while q:
            x, y, d = q.popleft()
            for nx, ny in ((x-1, y),(x+1, y),(x, y-1),(x, y+1)):
                if 0 <= nx < W and 0 <= ny < H and S[ny][nx]=='.' and (nx, ny) not in reached:
                    q.append((nx, ny, d+1))
                    reached.add((nx, ny))
                    ans = max(ans, d+1)
    for x in range(W):
        for y in range(H):
            if S[y][x] == '#':
                continue
            q.append((x, y, 0))
            reached.add((x, y))
            check()
            reached.clear()
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
sheet = [[0]*(W+2) for i in range(H+2)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]=='.':
      sheet[i+1][j+1] = 1

ans = -1
for i in range(1, H+1):
  for j in range(1, W+1):
    m = -1
    if sheet[i][j]==0:
      continue
    stuck = deque([(j, i, 0)])
    log = [[10**5]*(W+2) for i in range(H+2)]
    log[i][j] = 0
    while stuck:
      x, y, c = stuck.popleft()
      if c>m:
        m = c
      for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
        if sheet[y+dy][x+dx]==1 and log[y+dy][x+dx]>c+1:
          log[y+dy][x+dx] = c+1
          stuck += [(x+dx, y+dy, c+1)]
    if ans<m:
      ans = m
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import *
from heapq import *
INF = 500000
mod = 10**9+7

def dijkstra(s):
    dist = defaultdict(lambda : INF)
    dist[s], h = 0, []
    heappush(h, (0, s))
    while (len(h)):
        dv, v = heappop(h)
        if dv > dist[v]:
            continue
        for u in es[v]:
            tmp = dv+1
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(h, (tmp, u))
    return dist

H, W = map(int, input().split())
f = [input() for i in range(H)]
V = []
for i in range(H):
    for j in range(W):
        if f[i][j] == '.':
            V.append((i, j))
es = defaultdict(list)
for i in range(H):
    for j in range(W-1):
        if f[i][j] == '.' and f[i][j+1] == '.':
            es[(i, j)].append((i, j+1))
            es[(i, j+1)].append((i, j))
for i in range(H-1):
    for j in range(W):
        if f[i][j] == '.' and f[i+1][j] == '.':
            es[(i, j)].append((i+1, j))
            es[(i+1, j)].append((i, j))
ans = 0
for v in V:
    ans = max(ans, max(dijkstra(v).values()))
print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  input = sys.stdin.readline
  
  H,W = map(int,input().split())
  S = [list(input()) for _ in range(H)]
  #print(S)
  idx = 0
  for i in range(H):
    for j in range(W):
      if S[i][j] == '.':
        S[i][j] = idx
        idx += 1
  #print(S)
  D = [[float('inf') for _ in range(idx)] for _ in range(idx)]
  for i in range(H):
    for j in range(W):
      if S[i][j] == '#':
        continue
      for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if 0 <= i+dy < H and 0 <= j+dx < W and S[i+dy][j+dx] != '#':
          D[S[i][j]][S[i+dy][j+dx]] = 1
          D[S[i+dy][j+dx]][S[i][j]] = 1
  for i in range(idx):
    D[i][i] = 0
  
  for k in range(idx):
    for i in range(idx):
      for j in range(idx):
        D[i][j] = min(D[i][k]+D[k][j],D[i][j])
  #print(D)
  ans = 0
  for d in D:
    ans = max(max(d),ans)
  print(ans)

if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense,floyd_warshall

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

d = [[10**9] * (w*h) for _ in range(w*h)]

for i in range(h):
    for j in range(w):
        if(s[i][j] == '.'):
            if(i != h-1):
                if(s[i+1][j] == '.'):
                    d[(i*w + j)][((i+1)*w + j)] = 1
                    d[((i+1)*w + j)][(i*w + j)] = 1
            if(j != w-1):
                if(s[i][j+1] == '.'):
                    d[(i*w + j)][(i*w + j + 1)] = 1
                    d[(i*w + j + 1)][(i*w + j)] = 1

G = csgraph_from_dense(d, null_value=10**9)
len = floyd_warshall(G)

ans = 0
for i in range(h*w):
    for j in range(h*w):
        if(len[i][j] < 1000000):
            ans = max(len[i][j], ans)

print(int(ans))