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):
dr = [0, -1, 0, 1]
dc = [1, 0, -1, 0]

def get_child(M, i, j, h, w, vis):
    child = []
    for k in range(4):
        x = i + dr[k]
        y = j + dc[k]
        if 0<= x< h and 0 <= y < w and (x, y) not in vis and M[x][y]!='
            child.append((x, y))

    return child

def bfs(M, i, j, h, w):
    vis = {(i, j): True}
    li = [(i, j, 0)]
    mx = 0
    while li:
        tp = li.pop(0)
        mx = max(mx, tp[2])
        ch = get_child(M, tp[0], tp[1], h, w, vis)
        vis.update( {}.fromkeys(ch, True) )
        
        ch = [(t[0], t[1], tp[2]+1) for t in ch]
        li.extend(ch)

    return mx
        
        
def solve(M, h, w):
    ans = 0
    for r in range(h):
        for c in range(w):
            if M[r][c]=='.':
                
                depth = bfs(M, r, c, h, w)
                ans = max(ans, depth)
    print(ans)
h, w = map(int, input().split())
Mat = []
for row in range(h):
    Mat.append(input())


solve(Mat, h, w)

Solution (Python):
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''



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

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    '''
                    if 0<= x < H and 0<= y < W and dist[x][y]<=0:
                    '''
                    if 0<= x < H and 0<= y < W and M[x][y] == "." and dist[x][y]==-1:
                        dist[x][y]=dist[cx][cy]+1
                        Ma = max(Ma,dist[x][y])
                        q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))

Solution (Python):
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''



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

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    if 0<= x < H and 0<= y < W:

                        if M[x][y] == "." and dist[x][y] == -1:
                            dist[x][y]=dist[cx][cy]+1
                            Ma = max(Ma,dist[x][y])
                            q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))

Solution (Python):
from collections import deque
''' 
INF = float('inf')
MOD = 10 ** 9 + 7
'''



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

    
H,W=map(int,input().split())
M = []
Max_list = []
for i  in range(H):
    t = input()
    M.append(t)
dist = [[-1]*W for _ in range(H)]
q = deque()
for i in range(H):
    for j in range(W):
        dist = [[-1]*W for _ in range(H)]
        if M[i][j] == '.':
            Ma = 0
            q.append((i, j))
            dist[i][j] = 0
            while q:
                cx,cy = q.popleft()
                for nx,ny in d:
                    x ,y= cx+nx,cy+ny
                    ''' ここの処理がをnotにしてわかりやすく
                    if x<0 or y<0 or x>=H or y>=W or dist[x][y]>0:
                        continue
                    '''
                    if 0<= x < H and 0<= y < W and dist[x][y]<=0:

                        if M[x][y] == "." and dist[x][y] == -1:
                            dist[x][y]=dist[cx][cy]+1
                            Ma = max(Ma,dist[x][y])
                            q.append((x,y))
            Max_list.append(Ma)

print(max(Max_list))

Solution (Python):
import queue

H, W = map(int, input().split())
S = [input() for i in range(H)]
q = queue.Queue()
longest_path = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            g = [[0 if S[k][l] == '.' else -1 for l in range(W)] for k in range(H)]
            q.put((i,j))
            g[i][j] = 0
            while not(q.empty()):
                x, y = q.get()
                for nx, ny in [(x+1, y),(x-1, y),(x, y+1),(x, y-1)]:
                    if nx < 0 or nx > H-1 or ny < 0 or ny > W-1: continue
                    if g[nx][ny] != 0: continue
                    if nx == i and ny == j: continue
                    g[nx][ny] = g[x][y] + 1
                    q.put((nx,ny))
            longest_path = max(longest_path, max(map(max, g)))
print(longest_path)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = ['

ans = 0
INF = 111111

for i in range(h+1):
  for j in range(w+1):
    if s[i][j] == '
      continue
    visited = [[0] * (w+2) for _ in range(h+2)]
    visited[i][j] = 1
    max_s = 0
    dq = deque([(i, j, 0)])

    while dq:
      ci, cj, step = dq.popleft()
      if step > max_s:
        max_s = step
      step += 1

      for di, dj in ((ci+1, cj), (ci, cj+1), (ci-1, cj), (ci, cj-1)):
        if s[di][dj] == '
          continue
        visited[di][dj] = 1
        dq.append((di, dj, step))
    ans = max(max_s, ans)

print(ans)

Solution (Python):
import queue

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

ddx = [1,-1,0,0]
ddy = [0,0,1,-1]

INF = 1<<30
ans = 0
for sx in range(W):
    for sy in range(H):       
        if S[sy][sx] == '
        d = 0
        q = queue.Queue()
        dist = [[INF]*W for _ in range(H)]
        dist[sy][sx] = 0
        q.put([sx,sy])
        while not q.empty():
            x,y = q.get()
            for i in range(4):
                dx = ddx[i]
                dy = ddy[i]
                if y+dy<0 or y+dy>=H or x+dx<0 or x+dx>=W:
                    continue
                if S[y+dy][x+dx] == '.' and dist[y+dy][x+dx] == INF:
                    dist[y+dy][x+dx] = dist[y][x] + 1
                    q.put([x+dx,y+dy])
        
        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    d = max(d,dist[i][j])
            
        ans = max(ans,d)
        
print(ans)

Solution (Python):
def bfs(x):
  from collections import deque
  dist = [INF] * (H * W)
  dist[x] = 0
  stack = deque([(0, x)]) 
  while stack:
    v, s = stack.popleft() 
    for w, g in graph[s]:
      if dist[g] > v + w:
        dist[g] = v + w
        stack.append((dist[g], g)) 
  return dist

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

INF = 10**15
graph = [[] for _ in range(H * W)]
 
for i in range(H):
  for j in range(W):
    for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
      if 0 <= ni < H and 0 <= nj < W and S[ni][nj] != "
        graph[W * i + j].append((1, W * ni + nj))

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "
      continue
    else:
      dist = bfs(i * W + j)
      for ii in range(H * W):
        if dist[ii] != INF:
          answer = max(answer, dist[ii])
      
print(answer)

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

INF = 10**15
graph = [[] for _ in range(H * W)]
 
for i in range(H):
  for j in range(W):
    for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
      if 0 <= ni < H and 0 <= nj < W and S[ni][nj] != "
        graph[W * i + j].append((W * ni + nj, 1))

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "
      continue
    else:
      dist = [INF for _ in range(H * W)]
      dist[W * i + j] = 0
      stack = deque([W * i + j])
      while stack:
        s = stack.popleft()
        for g, w in graph[s]:
          if dist[g] > dist[s] + w:
            dist[g] = dist[s] + w
            stack.append(g)
      for ii in range(H * W):
        if dist[ii] != INF:
          answer = max(answer, dist[ii])
      
print(answer)

Solution (Python):
import copy
import queue

input_int_list = list(map(int, input().split()))

H = input_int_list[0]
W = input_int_list[1]

MAX_DIST = 100000


master_maze_list = [[-1 for i in range(H+2)] for j in range(W+2)]
for vertical_i in range(H):
	input_str_H = input()
	for holizontal_i in range(W):
		if input_str_H[holizontal_i] == '
			master_maze_list[holizontal_i+1][vertical_i+1] = -1
		elif input_str_H[holizontal_i] == '.':
			master_maze_list[holizontal_i+1][vertical_i+1] = MAX_DIST





distance_max = 0

for vertical_i in range(H):
	for holizontal_i in range(W):
		search_target_maze = copy.deepcopy(master_maze_list)
		root_h = holizontal_i+1
		root_v = vertical_i+1
		if search_target_maze[root_h][root_v] == -1:
			continue
		next_place_queue = queue.Queue()
		next_place_queue.put(root_h)
		next_place_queue.put(root_v)
		search_target_maze[root_h][root_v] = 0
		
		while next_place_queue.empty() != True:
			now_h = next_place_queue.get()
			now_v = next_place_queue.get()
			now_place_val = search_target_maze[now_h][now_v]

			if now_place_val == -1:
				pass
			else:
				if search_target_maze[now_h+1][now_v] > now_place_val+1:
					search_target_maze[now_h+1][now_v] = now_place_val+1
					next_place_queue.put(now_h+1)
					next_place_queue.put(now_v)

				if search_target_maze[now_h][now_v+1] > now_place_val+1:
					search_target_maze[now_h][now_v+1] = now_place_val+1
					next_place_queue.put(now_h)
					next_place_queue.put(now_v+1)

				if search_target_maze[now_h-1][now_v] > now_place_val+1:
					search_target_maze[now_h-1][now_v] = now_place_val+1
					next_place_queue.put(now_h-1)
					next_place_queue.put(now_v)

				if search_target_maze[now_h][now_v-1] > now_place_val+1:
					search_target_maze[now_h][now_v-1] = now_place_val+1
					next_place_queue.put(now_h)
					next_place_queue.put(now_v-1)
		distance_max = max(distance_max, now_place_val)


print(distance_max)

Solution (Python):

h,w=map(int,input().split())
s=[input() for i in range(h)]
ans=0
from collections import deque
for i in range(h):
    for j in range(w):
        q=deque()
        q.append([i,j,0])
        seen=[[False for j in range(w)] for i in range(h)]
        while q:
            node=q.popleft() 
            y=node[0]
            x=node[1]
            dist=node[2]
            if s[y][x]=='
                continue
            if seen[y][x]:
                continue
            seen[y][x]=True
            if dist>ans:
                ans=dist
            dif=((0,1),(0,-1),(1,0),(-1,0))
            for d in dif:
                if 0<=y+d[0]<h and 0<=x+d[1]<w:
                    q.append([y+d[0],x+d[1],dist+1])
print(ans)

Solution (Python):
from queue import Queue

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

ans = 0
for i in range(h):
    for j in range(w):
        start = s[i][j]
        if start == "
            continue
        else:
            visited = [[False for _ in range(w)] for _ in range(h)]
            visited[i][j] = True
            queue = Queue()
            queue.put((i, j, 0))

            while 0 < queue.qsize():
                now = queue.get()
                ans = max(ans, now[2])

                if (now[0] <= (h - 2)) and (s[now[0] + 1][now[1]] == ".") and not visited[now[0] + 1][now[1]]:
                    queue.put(((now[0] + 1), now[1], (now[2] + 1)))
                    visited[now[0] + 1][now[1]] = True
                if (now[1] <= (w - 2)) and (s[now[0]][now[1] + 1] == ".") and not visited[now[0]][now[1] + 1]:
                    queue.put((now[0], (now[1] + 1), (now[2] + 1)))
                    visited[now[0]][now[1] + 1] = True
                if (1 <= now[0]) and (s[now[0] - 1][now[1]] == ".") and not visited[now[0] - 1][now[1]]:
                    queue.put(((now[0] - 1), now[1], (now[2] + 1)))
                    visited[now[0] - 1][now[1]] = True
                if (1 <= now[1]) and (s[now[0]][now[1] - 1] == ".") and not visited[now[0]][now[1] - 1]:
                    queue.put((now[0], (now[1] - 1), (now[2] + 1)))
                    visited[now[0]][now[1] - 1] = True

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline


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

MAZE = ["
for _ in range(h):
    s = "
    MAZE.append(s)
MAZE.append("

I = [-1, 0, 0, 1]
J = [0, -1, 1, 0]
def bfs(r, c):
    DISTANCES = {}
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            DISTANCES[(i, j)] = -1
    DISTANCES[(r, c)] = 0
    Q = [(r, c)]
    while Q:
        i, j = Q.pop(0)
        for k in range(4):
            if MAZE[i + I[k]][j + J[k]] == "." and DISTANCES[(i + I[k], j + J[k])] == -1:
                DISTANCES[(i + I[k], j + J[k])] = DISTANCES[(i, j)] + 1
                Q.append((i + I[k], j + J[k]))
    return max(DISTANCES.values())

BFS = []
for r in range(1, h + 1):
    for c in range(1, w + 1):
        if MAZE[r][c] == ".":
            BFS.append(bfs(r, c))

print(max(BFS))

Solution (Python):
from collections import deque

def simulate(h, w, s, sx, sy):
    dist = [[-1 for x in range(w)] for y in range(h)]
    dist[sy][sx] = 0
    que = deque([(sx, sy)])
    res = 0
    while que:
        cx, cy = que.popleft()
        for dx, dy in [(0,1),(1,0),(0,-1),(-1,0)]:
            nx, ny = cx+dx, cy+dy
            if (0 <= nx < w) and (0 <= ny < h) and (s[ny][nx] == ".") and (dist[ny][nx] == -1):
                que.append((nx, ny))
                dist[ny][nx] = dist[cy][cx] + 1
                res = max(res, dist[ny][nx])
    return res

def solve(h, w, s):
    best = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == ".":
                best = max(best, simulate(h, w, s, x, y))
    return best

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

Solution (Python):

length, width = map(int, input().split())
Maze = [list(input()) for _ in range(length)]

def bfs(i, j):
    t = [[-1] * width for _ in range(length)]
    t[i][j] = 0
    stack = [(i, j)]
    while(stack):
        x, y = stack.pop(0)
        if x - 1 >= 0 and Maze[x - 1][y] != '
            t[x-1][y] = t[x][y] + 1
            stack.append((x-1, y))
        if x + 1 < length and Maze[x + 1][y] != '
            t[x + 1][y] = t[x][y] + 1
            stack.append((x+1, y))
        if y - 1 >= 0 and Maze[x][y-1] != '
            t[x][y-1] = t[x][y] + 1
            stack.append((x, y-1))
        if y + 1 < width and Maze[x][y+1] != '
            t[x][y+1] = t[x][y] + 1
            stack.append((x, y+1))
    return max(max(answer) for answer in t)
answer = 0

for i in range(length):
    for j in range(width):
        if Maze[i][j] != '
            answer = max(answer, bfs(i,j))

print(answer)

Solution (Python):
H,W = map(int,input().split())
grid = [input() for i in range(H)]
INF = 10**18
ans = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == '
            continue
        q = [(i,j)]
        dis = [[INF]*W for i in range(H)]
        dis[i][j] = 0
        d = 1
        while q:
            qq = []
            for y,x in q:
                for dy, dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                    yy,xx = dy+y,dx+x
                    if not(0<= yy < H and 0 <= xx < W):
                        continue
                    if dis[yy][xx] != INF:
                        continue
                    if grid[yy][xx] == '
                        continue
                    dis[yy][xx] = d
                    qq.append((yy,xx))
            q = qq
            d += 1
        for k in range(H):
            for l in range(W):
                if dis[k][l] != INF:
                    ans = max(ans,dis[k][l])
print(ans)

Solution (Python):
H,W=map(int,input().split())
maze=[]
maze.append(['
for i in range(H):
    tmp=['
    if '.' in tmp:
        a,b=i,tmp.index('.')
    maze.append(tmp)
maze.append(['
infty=10**5

def far(a,b):
    cost[a][b]=0
    point[0].append((a,b))
    stocks=1
    highscore=0
    tops=[]
    while stocks>0:
        stocks-=1
        for i in range(infty):
            if point[i]==[]:
                continue
            else:
                a,b=point[i].pop(0)
                break
        if i==highscore:
            tops.append((a,b))
        elif i>highscore:
            highscore,tops=i,[(a,b)]
        if maze[a][b+1]=='.' and cost[a][b+1]==infty:
            cost[a][b+1]=i+1
            point[i+1].append((a,b+1))
            stocks+=1
        if maze[a][b-1]=='.' and cost[a][b-1]==infty:
            cost[a][b-1]=i+1
            point[i+1].append((a,b-1))
            stocks+=1
        if maze[a-1][b]=='.' and cost[a-1][b]==infty:
            cost[a-1][b]=i+1
            point[i+1].append((a-1,b))
            stocks+=1
        if maze[a+1][b]=='.' and cost[a+1][b]==infty:
            cost[a+1][b]=i+1
            point[i+1].append((a+1,b))
            stocks+=1
    return tops,i


cost=[[infty]*(W+2) for i in range(H+2)]
point=[[] for i in range(infty)]

a,b=far(a,b)[0][0]

cost=[[infty]*(W+2) for i in range(H+2)]
point=[[] for i in range(infty)]

tops=far(a,b)[0]
res=0


for i,j in tops:
    cost=[[infty]*(W+2) for tmp in range(H+2)]
    point=[[] for i in range(infty)]
    tmp=far(i,j)[1]
    if res<tmp:res=tmp

print(res)

Solution (Python):
import copy

h, w = map(int, input().split())
maze = []
maze.append([-1 for i in range(w+2)])
for i in range(h):
    si = input()
    s_lst = [-1]
    for j in range(w):
        if si[j] == '.':
            s_lst.append(0)
        else:
            s_lst.append(-1)
    s_lst.append(-1)
    maze.append(s_lst)
maze.append([-1 for i in range(w+2)])

def solve_maze(maze, s):
    queue = [s]
    maze[s[0]][s[1]] = -2
    cnt = 0
    while queue != []:
        cnt += 1
        next_queue = []
        for ten in queue:
            i, j = ten[0], ten[1]
            if maze[i-1][j] == 0:
                maze[i-1][j] = cnt
                next_queue.append([i-1, j])
            if maze[i+1][j] == 0:
                maze[i+1][j] = cnt
                next_queue.append([i+1, j])
            if maze[i][j-1] == 0:
                maze[i][j-1] = cnt
                next_queue.append([i, j-1])
            if maze[i][j+1] == 0:
                maze[i][j+1] = cnt
                next_queue.append([i, j+1])
        queue = next_queue.copy()
    return cnt-1

ans = 0
for i in range(h+2):
    for j in range(w+2):
        if maze[i][j] == 0:
            copied_maze = copy.deepcopy(maze)
            ans = max(ans, solve_maze(copied_maze, [i, j]))

print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '
A = []
A.append(grid)
for i in range(h):
    tmp = "
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j ))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "
                continue
            if dist[hh+k][ww+l] <= dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

anss = 0
for i in range(h+2):
    for j in range(w+2):
        if A[i][j] == "
            continue
        anss = max(anss,bfs(i,j))
print(anss)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from collections import deque
'''
d = deque([1,2,3])
d.append(1)であれば右(末尾)
d.appendleft(1)であれば左(先頭)
d.pop()であれば3、つまり末尾
d.popleft()であれば1、つまり先頭
'''
h,w = map(int,readline().split())
grid = '
A = []
A.append(grid)
for i in range(h):
    tmp = "
    A.append(tmp)
A.append(grid)

def bfs(i,j ):
    inf = 10 ** 9
    dist = [[inf]*(w+2) for i in range(h+2)]
    dist[i][j] = 0
    q = deque()
    q.append((i,j ))
    ans = 0
    while q:
        hh, ww = q.popleft()
        dv = dist[hh][ww]
        for k,l in [(1,0),(0,1),(-1,0),(0,-1)]:
            if A[hh+k][ww+l] == "
                continue
            if dist[hh+k][ww+l] <= dv +1:
                continue
            dist[hh+k][ww+l] = dv +1
            ans = dv + 1
            q.append((hh+k,ww+l))

    return ans

anss = 0
for i in range(h+2):
    for j in range(w+2):
        if A[i][j] == "
            continue
        anss = max(anss,bfs(i,j))
print(anss)

Solution (Python):
H,W=map(int,input().split())
s=[input() for _  in range(H)]
G=[["

for i in range(H):
    for j in range(W):
        G[i+1][j+1]=s[i][j]

def search(y,x):
    q=[(y,x)]
    d=[[-1]*(W+2) for _ in range(H+2)]
    d[y][x]=0
    while q:
        y1,x1=q.pop(0)
        for y2,x2 in ((y1+1,x1),(y1,x1+1),(y1-1,x1),(y1,x1-1)):
            if G[y2][x2]=="." and d[y2][x2]==-1:
                d[y2][x2]=d[y1][x1]+1
                q.append((y2,x2))
    return max(max(_) for _ in d)

ans=0
for i in range(H):
    for j in range(W):
        if G[i+1][j+1]==".":
            ans=max(search(i+1,j+1),ans)

print(ans)

Solution (Python):












from collections import deque

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

adj = {(i, j): [] for i in range(H) for j in range(W)}
for i in range(H):
    for j in range(W):
        for m in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            row, col = m[0], m[1]
            if 0 <= row <= H - 1 and 0 <= col <= W - 1 and d[row][col] != '
                adj[i, j].append(m)


def bfs(g, s):
    if d[s[0]][s[1]] == "
        return 0
    visited = {}
    distance = {}
    q = deque()
    q.append(s)
    visited[s] = True
    distance[s] = 0
    while q:
        u = q.popleft()
        for i in g[u]:
            if i not in visited:
                q.append(i)
                visited[i] = True
                distance[i] = distance[u] + 1

    return max(distance.values())


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, bfs(adj, (i, j)))

print(ans)

Solution (Python):
from collections import deque
import copy


def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc + dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] = "
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr, nc]
    return goal, distance


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    _, res = bfs(goal, s)
    print(res)


if __name__ == '__main__':
    main()

Solution (Python):
import copy
import numpy as np
from collections import deque
m,n = list(map(int, input().split()))
o2 = []
dist_mat = []
for i in range(m):
    o1 = list(str(input()))
    o2.append(o1)
    dist_mat.append(np.zeros(len(o1)))

in_mat = np.array(o2)

dist_mat = []
for i in in_mat:
    dist_mat.append(np.zeros(len(i)))
dist_mat = np.array(dist_mat)
rows,cols = dist_mat.shape

qu = deque()

for r in range(rows):
    for c in range(cols):
        if in_mat[r][c] == ".":
            qu.appendleft((r,c))

dist_mat_base = copy.deepcopy(dist_mat)

ans = []
lenqu = len(qu)
for i in range(lenqu):
    strt = qu.pop()
    qu2 = deque()
    qu2.appendleft(strt)
    dist_mat = copy.deepcopy(dist_mat_base)

    while qu2:
        curr_r, curr_c = qu2.pop()
        dist = dist_mat[curr_r][curr_c]
        adj_cells = [(0,1), (1,0), (0,-1), (-1,0)]
        for r_adj, c_adj in adj_cells:
            adj_row = curr_r + r_adj
            adj_col = curr_c + c_adj
            if 0 <= adj_row < rows and 0 <= adj_col < cols:
                if dist_mat[adj_row][adj_col] == 0 and in_mat[adj_row][adj_col] == "." and not (adj_row, adj_col) == strt:
                    dist_mat[adj_row][adj_col] = dist + 1
                    qu2.appendleft((adj_row, adj_col))

    dist_vec = np.concatenate(dist_mat)
    ans.append(round(max(dist_vec)))

print(int(max(ans)))

Solution (Python):
H,W=map(int,input().split())
f=H*W
d=[[0]*f for _ in range(f)]


s=[input() for _  in range(H)]
    
for i in range(H):
    for j in range(W-1): 
        cnt=W*i+j
        d[cnt+1][cnt]=s[i][j]==s[i][j+1]=="."
        d[cnt][cnt+1]=s[i][j]==s[i][j+1]=="."
       
for i in range(H-1):
    for j in range(W): 
        cnt=W*i+j
        d[cnt][cnt+W]=s[i][j]==s[i+1][j]=="."
        d[cnt+W][cnt]=s[i][j]==s[i+1][j]=="."
        
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
csr=np.array(d)


ans=-1
k=shortest_path(csr)
for i in range(f):   
    for q in range(f):
            if k[i][q]>=f+1:k[i][q]=-1

    ans=max(ans,max(k[i]))

print(int(ans))

Solution (Python):
from collections import deque
 
H, W = map(int, input().split())
S = [list(input().split()[0]) for _ in range(H)]


def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "
            ans = max(ans, bfs(S, H, W, (j, i)))
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
 
H, W = map(int, input().split())
S = [list(input().split()[0]) for _ in range(H)]
 
def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))
 
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != "
            ans = max(ans, bfs(S, H, W, (j, i)))
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from collections import deque
 
H,W = map(int,readline().split())
H += 2; W += 2
grid = '
for _ in range(H-2):
    grid += '
grid += '
 
def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1,1,W,-W):
            w = v + move
            if grid[w] == '
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)
    return max(x for x in dist if x < INF)
 
answer = max(bfs(v) for v in range(H*W) if grid[v] != '
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

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

def bfs(S, H, W, start):
    INF = -1
    stack=deque([start])
    distance = [[INF]*W for _ in range(H)]
    distance[start[1]][start[0]] = 0
    while stack:
        x, y = stack.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_x = x + i
            next_y = y + j
            if not(0 <= next_x < W and 0 <= next_y < H):
                continue
            if S[next_y][next_x] != '
                stack.append([next_x, next_y])
                distance[next_y][next_x] = distance[y][x] + 1
    return max(map(max, distance))

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