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.

Solution (Python):
import collections
INF = 10**9
    
def next(H,W,S,current):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    for i in range(4):
        neighbor = (current[0]+dx[i],current[1]+dy[i])
        if 0 <= neighbor[0] < H and 0 <= neighbor[1] < W and S[neighbor[0]][neighbor[1]] == '.':
            yield neighbor

def bfs(start,H,W,S):
    q = collections.deque([start])
    v = 0
    visited = []
    layer = [[INF for i in range(W)] for j in range(H)]
    layer[start[0]][start[1]] = 0
    while q:
        c = q.popleft()
        if c in visited:
            continue
        visited.append(c)
        for neighbor in next(H,W,S,c):
            if neighbor not in visited:
                q.append(neighbor)
                layer[neighbor[0]][neighbor[1]] = layer[c[0]][c[1]]+1
                v = max(v,layer[neighbor[0]][neighbor[1]])
    
    return v

def main():
    H,W  = map(int, input().split())
    S = [[] for i in range(H)]
    route = 0
    for i in range(H):
        S[i]  = list(input())
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                start = (i,j)
                route = max(route,bfs(start,H,W,S))
    print(route)

if __name__ == '__main__':
    main()

Solution (Python):
import copy

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

def BFS(q):
	flg = copy.deepcopy(S)
	while q != []:
		cx,cy,cd = q.pop(0)
		if flg[cx][cy] == "
			continue
		else:
			flg[cx][cy] = "
		nps = [[cx+1,cy],[cx-1,cy],[cx,cy+1],[cx,cy-1]]
		for nx,ny in nps:
			if 0 <= nx < H and 0 <= ny < W:
				if flg[nx][ny] != "
					q.append([nx,ny,cd+1])

	return cd

ans = 0

for sx in range(H):
	for sy in range(W):
		if S[sx][sy] == "
			continue
		else:
			ans = max(ans,BFS([[sx,sy,0]]))

print(ans)

Solution (Python):
from collections import deque
h,w = map(int,input().split(" "))
s = [input() for _ in range(h)]
 
ans = 0
direcion = [(1,0),(0,1),(-1,0),(0,-1)]
for i in range(h):
    for j in range(w):
        if s[i][j] == "
            continue
        que = deque([(j,i)])
        dist = [[0]*w for _ in range(h)]
        visited = [[0]*w for _ in range(h)]
        visited[i][j] = 1
        while que:
            j, i = que.popleft()
            for x,y in direcion:
                n_x,n_y = j+x,i+y
                if not 0 <= n_x < w: continue
                if not 0 <= n_y < h: continue
                if visited[n_y][n_x]: continue
                if s[n_y][n_x] == "
                visited[n_y][n_x] = 1
                dist[n_y][n_x] = dist[i][j] + 1
                que.append((n_x,n_y))
        ans = max(ans,max(max(row) for row in dist))
print(ans)

Solution (Python):
from collections import deque
import numpy as np
def main():
    hw = list(map(int, input().split()))
    s = np.zeros((hw[0],hw[1]), dtype=int)
    validpoints = []
    for i in range(hw[0]):
        tmp = input()
        tm = [None]*hw[1]
        for j in range(hw[1]):
            if tmp[j] == '.':
                tm[j] = 0
                validpoints.append((i,j))
            elif tmp[j] == '
                tm[j] = 1
        s[i] = np.array(tm)

    ma = 0

    for i in validpoints:
        cost = breadth(s,i)
        if cost > ma:
            ma = cost
    print(ma)

def breadth(ss, start):
    q = deque()
    visited = np.array(ss)
    visited[start] = 1
    q.append({start})
    c = 0

    while not len(q) == 0:
        c += 1
        v = q.pop()
        tmpl = []
        for i in v:
            visited[i] = 1
            child = get_child_quad(ss, visited, i)
            tmpl.extend(child)
        tmps = set(tmpl)
        if len(tmps) > 0:
            for i in tmps:
                visited[i] = 1
            q.append(set(tmpl))

    return c-1

def get_child_quad(ss, visited, p):
    down = (p[0]+1,p[1])
    up = (p[0]-1,p[1])
    right = (p[0],p[1]+1)
    left = (p[0],p[1]-1)
    child = [down,up,right,left]
    return list(filter(lambda pp: 0 <= pp[0] < len(ss) and 0 <= pp[1] < len(ss[0]) and visited[pp[0],pp[1]] == 0, child))

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import numpy as np
def main():
    hw = list(map(int, input().split()))
    s = np.zeros((hw[0],hw[1]), dtype=int)
    validpoints = []
    for i in range(hw[0]):
        tmp = input()
        tm = [None]*hw[1]
        for j in range(hw[1]):
            if tmp[j] == '.':
                tm[j] = 0
                validpoints.append((i,j))
            elif tmp[j] == '
                tm[j] = 1
        s[i] = np.array(tm)

    ma = 0
    
    
    
    
    
    
    for i in validpoints:
        cost = breadth(s,i)
        if cost > ma:
            ma = cost
    print(ma)

    
    

def breadth(ss, start):
    q = deque()
    visited = np.array(ss)
    visited[start] = 1
    q.append({start})
    c = 0

    while not len(q) == 0:
        c += 1
        v = q.pop()
        tmpl = []
        for i in v:
            visited[i] = 1
            child = get_child_quad(ss, visited, i)
            tmpl.extend(child)
        tmps = set(tmpl)
        if len(tmps) > 0:
            for i in tmps:
                visited[i] = 1
            q.append(set(tmpl))

    return c-1

def get_child_quad(ss, visited, p):
    down = (p[0]+1,p[1])
    up = (p[0]-1,p[1])
    right = (p[0],p[1]+1)
    left = (p[0],p[1]-1)
    child = [down,up,right,left]
    return list(filter(lambda pp: 0 <= pp[0] < len(ss) and 0 <= pp[1] < len(ss[0]) and visited[pp[0],pp[1]] == 0, child))





















    























        


if __name__ == '__main__':
    main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        m[y][x] = 1
        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] == "." and m[yy][xx] == 0:
                        m[yy][xx] = 1
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == ".":
                ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()

Solution (Python):
from collections import deque
h,w=map(int,input().split())
S=[input() for _ in range(h)]

ans=0
dxy=[(0,1),(1,0),(0,-1),(-1,0)]
for y in range(h):
  for x in range(w):
    if S[y][x]=='
    q=deque([(x,y)])
    dist=[[0]*w for _ in range(h)]
    visited=[[0]*w for _ in range(h)]
    visited[y][x]=1
    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]=='
        visited[ny][nx]=1
        dist[ny][nx]=dist[y][x]+1
        q.append((nx,ny))
    ans = max(ans, max(max(row) for row in dist))
print(ans)

Solution (Python):


import numpy as np
import copy
from collections import deque

n, m = map(int, input().split())


d = []
mas = []
for i in range(n):
    mas.extend(list(map(list, input().split())))
    d.append([float("nan")] * m)


def tansaku(sx, sy, d):
    local_d = copy.deepcopy(d)
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    local_d[sx][sy] = 0
    while que:
        
        p = que.popleft()
        for i in range(4):
            
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and mas[nx][ny] != "
                and not local_d[nx][ny] == local_d[nx][ny]
            ):
                
                que.append((nx, ny))
                local_d[nx][ny] = local_d[p[0]][p[1]] + 1
    d_max = int(np.nanmax(np.array(local_d)))
    return d_max


dis = 0
for i in range(n):
    for j in range(m):
        if mas[i][j] != "
            dis_i = tansaku(i, j, d)
            if dis_i > dis:
                dis = copy.copy(dis_i)

print(dis)

Solution (Python):
Y,X=map(int,input().split())
info=[]
for i in range(Y):
    line=list(input())
    info.append(line)
ans=0
def bfs(y,x):
    global nex
    global ok
    global visited
    if not((0<=y<Y) and (0<=x<X)):
        return
    if visited[y][x]==1 or info[y][x]=="
        return
    visited[y][x]=1
    ok+=1
    nex.append([y,x])

for i in range(Y):
    for j in range(X):
        if info[i][j]=="
            continue
        visited=[[0 for a in range(X)] for b in range(Y)] 
        visited[i][j]=1
        nex=[[i,j]]
        farthest=0 
        num=1 
        while num>0:
            ok=0
            for k in range(num):
                bfs(nex[0][0]+1,nex[0][1])
                bfs(nex[0][0]-1,nex[0][1])
                bfs(nex[0][0],nex[0][1]+1)
                bfs(nex[0][0],nex[0][1]-1)
                del nex[0]
            if ok!=0:
                farthest+=1
            num=len(nex)
        if ans<farthest:
            ans=farthest
print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    
    
    
    
    
    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 [0]*w] for _ in [0]*h]
                que = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    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()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    
    
    
    
    
    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 = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    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()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    
    
    
    
    
    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 = deque()
                d[sx][sy] = 0
                que.append([sx,sy])
                M = 0
                while que:
                    [qx,qy] = que.popleft()
                    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()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h, w = map(int, input().split())
    maze = [tuple(input()) for _ in range(h)]
    
    
    
    
    
    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 = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    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()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy


from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): 
    return int(input())
def inpm(): 
    return map(int,input().split())
def inpl(): 
    return list(map(int, input().split()))
def inpls(): 
    return list(input().split())
def inplm(n): 
    return list(int(input()) for _ in range(n))
def inpll(n): 
    return sorted([list(map(int, input().split())) for _ in range(n)])
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a=inp()
        a-=1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w = inpm()
    maze = []
    for _ in range(h):
        s = tuple(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 = deque()
                d[sx][sy] = 0
                que.append((sx,sy))
                M = 0
                while que:
                    (qx,qy) = que.popleft()
                    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()

Solution (Python):
from collections import deque


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


def bfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = deque([])
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            todo.append([ny, nx, 1])

    while todo:
        y, x, d = todo.popleft()
        if meiro[y][x] == '
            continue
        if dist[y][x] != -1:
            continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                todo.append([ny, nx, d+1])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(bfs(y, x))

print(max(ans))

Solution (Python):
from collections import deque


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


def bfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '
        return 0
    dist[y][x] = 0

    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = deque([])
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            todo.append([ny, nx, 1])

    while todo:
        y, x, d = todo.popleft()
        if meiro[y][x] == '
            continue
        if dist[y][x] != -1:
            continue

        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1 and dist[ny][nx] == -1:
                todo.append([ny, nx, d+1])

    res = 0
    for line in dist:
        res = max(max(line), res)

    return res


ans = []
for y in range(h):
    for x in range(w):
        ans.append(bfs(y, x))

print(max(ans))

Solution (Python):
import collections
h, w = map(int, input().split())
s = [[""]*(w+2)]
starts = []
for i in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
    for j, __s in enumerate(_s):
        if __s == ".":
            starts.append([i+1, j])
s.append([""]*(w+2))

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

ans = 0
for _start in starts:
    dist = [[-1]*(w+2) for _ in range(h+2)]
    dist[_start[0]][_start[1]] = 0
    q = collections.deque([_start])

    
    while 0 < len(q):
        c = q.pop()
        for _dx, _dy in zip(dx, dy):
            x = c[0] + _dx
            y = c[1] + _dy
            if s[x][y] == "." and dist[x][y] == -1:
                dist[x][y] = dist[c[0]][c[1]] + 1
                q.appendleft([x, y])

    for _d in dist:
        ans = max(ans, max(_d))

print(ans)

Solution (Python):
import heapq
 
 
h, w = map(int, input().split())
meiro = []
for i in range(h):
    line = input()
    meiro.append(line)
 
 
def dfs(y, x):
    dist = [[-1]*w for _ in range(h)]
    if meiro[y][x] == '
        return 0
    dist[y][x] = 0
 
    pattern = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    todo = []
    for dy, dx in pattern:
        ny, nx = y + dy, x + dx
        if 0 <= ny <= h-1 and 0 <= nx <= w-1:
            if meiro[ny][nx] == '.':
                heapq.heappush(todo, [1, ny, nx])
 
    while todo:
        d, y, x = heapq.heappop(todo)
        if meiro[y][x] == '
            continue
        if dist[y][x] != -1:
                continue
 
        dist[y][x] = d
        for dy, dx in pattern:
            ny, nx = y + dy, x + dx
            if 0 <= ny <= h - 1 and 0 <= nx <= w - 1:
                if dist[ny][nx] == -1 and meiro[ny][nx] == '.':
                    heapq.heappush(todo, [d+1, ny, nx])
 
    res = 0
    for line in dist:
        res = max(max(line), res)
 
    return res
 
 
ans = []
for y in range(h):
    for x in range(w):
        ans.append(dfs(y, x))
 
print(max(ans))

Solution (Python):
from collections import deque


h, w = map(int, input().split())
graph = '
for _ in range(h):
    line = '
    graph = graph + line

graph = graph + '


def bfs(x):
    if graph[x] == '
        return 0
    seen = [-1] * ((h+2)*(w+2))
    seen[x] = 0
    pattern = [-(w+2), -1, 1, w+2]
    todo = deque([])
    for delta in pattern:
        if graph[x+delta] == '.':
            todo.append([x+delta, 1])

    while todo:
        node, dist = todo.popleft()
        if seen[node] != -1:
            continue
        seen[node] = dist
        for delta in pattern:
            if graph[node+delta] == '.' and seen[node+delta] == -1:
                todo.append([node+delta, dist+1])

    return max(seen)


ans = []
for i in range((h+1)*(w+1)):
    ans.append(bfs(i))

print(max(ans))

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]

INF = 1001001001
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

def update(i, j, x):
    global dist, s, q
    if(dist[i][j] != INF): return
    dist[i][j] = x
    q.append([i, j])

res = 0
for si in range(h):
    for sj in range(w):
        if(s[si][sj] == '
        
        dist = [[INF for _ in range(w)] for _ in range(h)]
        q = deque()
        update(si, sj, 0)
        
        while(q):
            i, j = q.popleft()
            
            for idir, jdir in zip(di, dj):
                ni = i + idir
                nj = j + jdir
                
                if(ni<0 or ni>=h or nj<0 or nj>=w): continue
                if(s[ni][nj] == '
                
                update(ni, nj, dist[i][j]+1)
        
        for i in range(h):
            for j in range(w):
                if(dist[i][j]==INF): continue
                res = max(res, dist[i][j])

print(res)

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
H, W = map(int, input().split())
grid = [[1 if i == "." else 0 for i in input()] for _ in range(H)]

inf = 10**5
wf = np.ones((H*W, H*W), dtype=int)*inf
DX = (0, 1, 0, -1)
DY = (1, 0, -1, 0)

for i in range(H):
    for j in range(W):
        if not grid[i][j]:
            continue
        for dx, dy in zip(DX, DY):
            x = i + dx
            y = j + dy
            if x < 0 or x >= H or y < 0 or y >= W:  
                continue
            if not grid[x][y]:  
                continue
            orig = W * i + j
            to = orig + dx * W + dy
            wf[orig][to] = 1
            wf[to][orig] = 1

wf = floyd_warshall(wf)
wf[wf >= inf] = 0.
ans = int(wf.max())
print(ans)

Solution (Python):
import queue

h,w = map(int,input().split())
maze = []

for i in range(h):
	mazeRow = list(input())
	maze.append(mazeRow)
	
maxRootCnt = 0

for roop_h in range(h):
	for roop_w in range(w):
		if maze[roop_h][roop_w] == '
			continue

		isSearched =  [[0] * w for i in range(h)]
		isLevel =  [[0] * w for i in range(h)]
		nowTansakuCnt = 0

		q = queue.Queue()
		q.put([roop_h,roop_w])

		
		isSearched[roop_h][roop_w] = 1
		isLevel[roop_h][roop_w] = 0
		while not q.empty():
			n= q.get()
			nowLevel = isLevel[n[0]][n[1]]
			if nowLevel > maxRootCnt:
				maxRootCnt = nowLevel
			
			if n[0] != 0:
				if maze[n[0] -1][n[1]] == '.' and isSearched[n[0] -1][n[1]] == 0:
					q.put([n[0]-1,n[1]])
					isSearched[n[0] -1][n[1]] = 1
					isLevel[n[0] -1][n[1]] = nowLevel + 1
			
			if n[0] != h-1:
				if maze[n[0] +1][n[1]] == '.' and isSearched[n[0]+1][n[1]] == 0:
					q.put([n[0]+1,n[1]])
					isSearched[n[0] +1][n[1]] = 1
					isLevel[n[0] +1][n[1]] = nowLevel + 1
				
			
			if n[1] != 0:
				if maze[n[0]][n[1]-1] == '.' and isSearched[n[0]][n[1]-1] == 0:
					q.put([n[0],n[1]-1])
					isSearched[n[0]][n[1]-1] = 1
					isLevel[n[0]][n[1]-1] = nowLevel + 1

			
			if n[1] != w-1:
				if maze[n[0]][n[1]+1] == '.' and isSearched[n[0]][n[1]+1] == 0:
					q.put([n[0],n[1]+1])
					isSearched[n[0]][n[1]+1] = 1
					isLevel[n[0]][n[1]+1] = nowLevel + 1
				                    
print(maxRootCnt)

Solution (Python):


from collections import deque

def bfs(sx,sy):
    cnt=0
    INF=100100100
    
    dist=[[INF]*(w+2) for _ in range(h+2)]
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]

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

    
    while que:
        q=que.popleft()

        for i in range(4):
            next_x=q[0]+dx[i]
            next_y=q[1]+dy[i]

            if maze[next_x][next_y]!="
                que.append((next_x,next_y))
                dist[next_x][next_y]=dist[q[0]][q[1]]+1
                cnt=dist[next_x][next_y]
                
    return cnt

h,w=map(int,input().split())
maze=[]
ans=0
x=""
for i in range(w+2):
    x+="
maze.append(x)
for i in range(h):
    s=input()
    s='
    maze.append(s)
maze.append(x)
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j]=="
            continue
        ans=max(ans,bfs(i,j))
print(ans)

Solution (Python):
import queue

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

dx=[0,0,-1,1]
dy=[-1,1,0,0]

for i in range(H):
    S[i]=input()

def bfs(i,j):
    max_d=0
    q=queue.Queue()
    q.put((i,j))
    d=[[0]*W for _ in range(H)]
    while not q.empty():
        loc=q.get()
        for k in range(len(dx)):
            x=loc[1]+dx[k]
            y=loc[0]+dy[k]
            if x>=0 and x<W and y>=0 and y<H:
                if S[y][x]==".":
                    if d[y][x]==0 and not(x==j and y==i):
                        q.put((y,x))
                        d[y][x]=d[loc[0]][loc[1]]+1
                        max_d=max(max_d,d[y][x])
    return max_d

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

Solution (Python):
from collections import deque
h,w = map(int,input().split())
s_list=[['
for i in range(h):
    s_list.append(['
s_list.append(['



def bfs(x, y):
    temp_maps =  [[None if s == '.' else -1 for s in s_row] for s_row in s_list]
    temp_maps[x][y] = 0
    que = deque()
    que.append((x,y))
    while que:
        i, j = que.popleft()
        for val_added_i, val_added_j in ((0,1),(0,-1),(1,0),(-1,0)):
            if temp_maps[i + val_added_i][j + val_added_j] is None:
                temp_maps[i + val_added_i][j + val_added_j] = temp_maps[i][j] + 1
                que.append((i + val_added_i, j + val_added_j))
    return max(max(maps_row)  for maps_row in temp_maps)


max_value = 0

for i in range(1, h+1):
    for j in range(1, w+1):
        if s_list[i][j] == '.':
            val = bfs(i, j)
            max_value = max(max_value, val)

print(max_value)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
Gd = [list(input()) for _ in range(H)]
INF = -1
direc = [[1,0],[-1,0],[0,1],[0,-1]]
def dfs(start):
  Dis = [[INF]*W for _ in range(H)]
  Dis[start[0]][start[1]]=0
  q = deque([])
  q.append(start)
  r = 0
  while len(q)!=0:
    h,w = q.popleft()
    
    for d in direc:
      hs, ws = h + d[0], w + d[1]
      if not (0<=hs<H and 0<=ws<W):
        continue
      if Gd[hs][ws]=='.' and Dis[hs][ws]==INF:
          q.append([hs,ws])
          Dis[hs][ws] = Dis[h][w] + 1
          r = max(Dis[hs][ws],r)
  return r
ans = INF
for h in range(H):
  for w in range(W):
    if Gd[h][w]=='.':
      ans = max(ans,dfs([h,w]))
print(ans)