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

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


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



if __name__ == '__main__':
    solve()

Solution (Python):
H,W = map(int,input().split())
S = [input() for i in range(H)]

dxy = [(0,1),(1,0),(0,-1),(-1,0)]
from collections import deque
ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[y][x] = 1
        q = deque([(x,y)])
        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):
from collections import deque
import numpy as np
h, w = map(int, input().split())
S = [input() for _ in range(h)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]
def search(sy, sx):
  if S[sy][sx] == "
    return -1
  dist = [[-1]*w for _ in range(h)]
  dist[sy][sx] = 0
  dq = deque()
  dq.append((sy, sx))
  while dq:
    y, x = dq.popleft()
    for i in range(4):
      ny = y+dy[i]
      nx = x+dx[i]
      if 0<=ny<h and 0<=nx<w:
        if S[ny][nx] == "
          continue
        if dist[ny][nx] != -1:
          continue
        dist[ny][nx] = dist[y][x] + 1
        dq.append((ny, nx))
  A = np.array(dist)
  return A.max()
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans, search(i, j))
print(ans)

Solution (Python):
n, m = map(int, input().split())
grid = [input() for i in range(n)]

res = 0
dirs = [(0,1),(1,0),(0,-1),(-1,0)]

for a in range(n):
  for b in range(m):
    if grid[a][b] != '.':
      continue
    vis = set([(a,b)])
    q = [(a,b,0)]
    qi = 0
    while qi < len(q):
      i, j, c = q[qi]
      res = max(res, c)
      qi += 1
      for di, dj in dirs:
        ni, nj = i + di, j + dj
        if (ni, nj) in vis or ni < 0 or ni >= n or nj < 0 or nj >= m or grid[ni][nj] != '.':
          continue
        vis.add((ni, nj))
        q.append((ni, nj, c+1))
print(res)

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


def bfs(start):
    one_steps = ((1, 0), (-1, 0), (0, 1), (0, -1))
    seen = set()
    todo = deque()
    todo.append(start)
    dis = {start: 0}
    a = 0
    while len(todo) > 0:
        a += 1
        x, y = todo.popleft()
        if (x, y) in seen:
            continue
        seen.add((x, y))
        for dx, dy in one_steps:
            nx, ny = x + dx, y + dy
            if not (0 <= nx < H) or not (0 <= ny < W):
                continue
            if (nx, ny) in seen:
                continue
            elif graph[nx][ny] == "." and (nx, ny) != start:
                dis[(nx, ny)] = dis[(x, y)] + 1
                todo.append((nx, ny))

    return max(dis.values())


ans = -1
for x_ in range(H):
    for y_ in range(W):
        if graph[x_][y_] == ".":
            ans = max(ans, bfs((x_, y_)))
print(ans)

Solution (Python):
H,W = map(int,input().split())
S = [input() for _ in range(H)]
from scipy.sparse.csgraph import floyd_warshall as fw

edge = [[float('inf')]*(H*W) for _ in range(H*W)]
def encode(i,j):
    return i*W+j

for i in range(H):
    for j in range(W):
        if S[i][j]=='
            continue
        for (dx,dy) in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=i+dx<=H-1 and 0<=j+dy<=W-1:
                if (dx,dy)==(0,0):
                    continue
                if S[i+dx][j+dy]=='.':
                    edge[encode(i,j)][encode(i+dx,j+dy)] = 1

cost = fw(edge)
ans = 0
for i in range(H*W):
    for j in range(H*W):
        if cost[i][j]==float('inf'):
            continue
        ans = max(ans,cost[i][j])
ans = int(ans)
print(ans)

Solution (Python):
from queue import Queue
H, W  = list(map(int, input().split()))

Ss = []
for i in range(H):
    Ss.append(input())


def bfs(Ss, startX, startY):
    dir = [(1,0), (0, 1), (-1, 0), (0, -1)]

    currentX = startX
    currentY = startY
    queue = Queue()
    visited = set()
    queue.put((currentX, currentY, 0))
    maxDist = 0
    while not queue.empty():
        nextX, nextY, dist = queue.get()
        visited.add((nextX, nextY))
        maxDist = max(maxDist, dist)
        for (dx, dy) in dir:
            y_dy = nextY + dy
            x_dx = nextX + dx
            if y_dy >= 0 and y_dy < len(Ss) and x_dx >= 0 and x_dx < len(Ss[0]):
                if Ss[y_dy][x_dx] != '
                    if (x_dx, y_dy) not in visited:
                        queue.put((x_dx, y_dy, dist + 1))
                    visited.add((x_dx, y_dy))
    return maxDist

maxDist = 0
for y in range(H):
    for x in range(W):
        if Ss[y][x] != '
            dist = bfs(Ss, x, y)
            maxDist = max(dist, maxDist)
print(maxDist)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

h,w=map(int,input().split())
S=[list(input()) for i in range(h)]
dydx４=((-1,0),(0,-1),(0,1),(1,0))
for i in range(h):
    for j in range(w):
        if S[i][j]=="
        color=[[-1]*w for i in range(h)]
        color[i][j]=0
        que=collections.deque()
        que.append((i,j,0))
        while que:
            pi,pj,now = que.popleft()
            for di,dj in dydx４:
                ni=pi+di; nj=pj+dj
                if 0<=ni<h and 0<=nj<w:
                    if color[ni][nj]==-1 and S[ni][nj]==".":
                        que.append((ni,nj,now+1))
                        color[ni][nj]=now+1
        tmp=0
        for ci in color:
            tmp=max(tmp,max(ci))
        ans=max(ans,tmp)
        
        
        
print(ans)

Solution (Python):
from collections import  deque

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

S = []

for i in range(H):

    s = list(input())
    S.append(s)



ans = 0

for a in range(H):
    for b in range(W):

        if S[a][b] == "
            continue
        
        q = deque([])
        q.append([a,b])
        d = [[float("inf")] * W for i in range(H)]
        d[a][b] = 0

        while len(q) > 0:

            now = q.popleft()
            x = now[0]
            y = now[1]

            if x > 0 and S[x-1][y] == ".":
                if d[x-1][y] > d[x][y] + 1:
                    d[x-1][y] = d[x][y] + 1
                    q.append([x-1,y])
            if x < H-1 and S[x+1][y] == ".":
                if d[x+1][y] > d[x][y] + 1:
                    d[x+1][y] = d[x][y] + 1
                    q.append([x+1,y])

            if y > 0 and S[x][y-1] == ".":
                if d[x][y-1] > d[x][y] + 1:
                    d[x][y-1] = d[x][y] + 1
                    q.append([x,y-1])

            if y < W-1 and S[x][y+1] == ".":
                if d[x][y+1] > d[x][y] + 1:
                    d[x][y+1] = d[x][y] + 1
                    q.append([x,y+1])

        
        for i in range(H):
            for j in range(W):
                if d[i][j] != float("inf"):
                    ans = max(ans,d[i][j])

        

print (ans)

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


def main():
    h, w = map(int, input().split())
    area = [input().strip() for _ in range(h)]
    index = [[0, 1], [0, -1], [1, 0], [-1, 0]]
    maxc = 0
    for x in range(h):
        for y in range(w):
            if area[x][y] == '
                continue
            area_flag = [[False for j in range(w)] for i in range(h)]
            search_list = deque([[x, y, 0], ])
            area_flag[x][y] = True
            while len(search_list) > 0:
                nowx, nowy, nowc = search_list.pop()
                maxc = max(maxc, nowc)
                for ix, iy in index:
                    if 0 <= nowx+ix < h and 0 <= nowy+iy < w:
                        if area_flag[nowx+ix][nowy+iy] or area[nowx+ix][nowy+iy] == '
                            continue
                        else:
                            area_flag[nowx+ix][nowy+iy] = True
                            search_list.appendleft([nowx+ix, nowy+iy, nowc+1])
    print(maxc)
    

if __name__ == '__main__':
    main()

Solution (Python):
import collections
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
q = collections.deque()
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            continue
        q.append((i, j))
        tmp = [[-1]*W for i in range(H)]
        tmp[i][j] = 0
        while(q):
            y, x = q.popleft()
            if y > 0 and tmp[y-1][x] < 0 and S[y-1][x] != "
                q.append((y-1, x))
                tmp[y-1][x] = tmp[y][x] + 1
                ans = max(ans, tmp[y-1][x])
            if y < H-1 and tmp[y+1][x] < 0 and S[y+1][x] != "
                q.append((y+1, x))
                tmp[y+1][x] = tmp[y][x] + 1
                ans = max(ans, tmp[y+1][x])
            if x > 0 and tmp[y][x-1] < 0 and S[y][x-1] != "
                q.append((y, x-1))
                tmp[y][x-1] = tmp[y][x] + 1
                ans = max(ans, tmp[y][x-1])
            if x < W - 1 and tmp[y][x+1] < 0 and S[y][x+1] != "
                q.append((y, x+1))
                tmp[y][x+1] = tmp[y][x] + 1
                ans = max(ans, tmp[y][x+1])
print(ans)

Solution (Python):

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

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

Solution (Python):
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy


from itertools import permutations, combinations
from heapq import heappop, heappush

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 [list(map(int, input().split())) for _ in range(n)]


def main():
    h,w = inpm()
    maze = []
    for _ in range(h):
        s = list(input())
        maze.append(s)
    ans = 0
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    key = 0
    for sx in range(h):
        for sy in range(w):
            if maze[sx][sy] == '
                continue
            else:
                d = [[-1 for _ in range(w)] for _ in range(h)]
                que = []
                d[sx][sy] = 0
                que.append([sx,sy])
                M = 0
                while que:
                    [qx,qy]=que[0]
                    que.pop(0)
                    for i in range(4):
                        nx=qx+dx[i]
                        ny=qy+dy[i]
                        if nx>=0 and h>nx and ny>=0 and w>ny and maze[nx][ny]=="." and d[nx][ny]==-1:
                            d[nx][ny]=d[qx][qy]+1
                            if d[qx][qy]+1>M:
                                M= d[qx][qy]+1
                            que.append([nx,ny])
                ans = max(ans,M)
    print(ans)
 

if __name__ == "__main__":
    main()

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


h,w = [int(i) for i in readline().split()]
b = [input() for _ in range(h)]

dx4=[0, 1, 0,-1]
dy4=[1, 0,-1, 0]

from collections import deque


ans = 0
for sx in range(h):
    for sy in range(w):
        if b[sx][sy] == "
        
        c = 0    
        memo = [[-1]*w for _ in range(h)]
        q = deque()
        q.append((sx,sy)) 
        memo[sx][sy] = 0 
        while q: 
            x,y = q.popleft() 
            
            for i in range(4):
                nx = x + dx4[i]
                ny = y + dy4[i]
                
                if nx < 0 or nx>=h or ny <0 or ny>=w: continue
                
                if b[nx][ny] == "
                
                if memo[nx][ny] >= 0: continue
                
                memo[nx][ny] = memo[x][y]+1
                c = memo[x][y]+1
                q.append((nx,ny))

        if ans < c: ans = c

print(ans)

Solution (Python):




from __future__ import print_function, division, unicode_literals

__metaclass__ = type

try:
    input = raw_input
    range = xrange
except NameError:
    pass


import sys












import itertools as it
from collections import deque


def main():
    H, W = map(int, input().split())
    S = [[x == '
    ans = 0
    for s in it.product(range(H), range(W)):
        if S[s[0]][s[1]]:
            continue
        D = {s: 0}
        Q = deque([s])
        while Q:
            u = Q.popleft()
            for dr, dc in [(0, +1), (-1, 0), (0, -1), (+1, 0)]:
                v = (u[0] + dr, u[1] + dc)
                if not (0 <= v[0] < H and 0 <= v[1] < W) or S[v[0]][v[1]] or v in D:
                    continue
                D[v] = D[u] + 1
                ans = max(ans, D[v])
                Q.append(v)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
INF = 10**18

H,W = map(int,input().split())
S = [input() for _ in range(H)]
N = H*W
cost = [[INF]*N for _ in range(N)]
for k in range(N):
    cost[k][k] = 0

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

for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        k = i*W+j
        for d in range(4):
            if not(0<=i+dx[d]<H and 0<=j+dy[d]<W):
                continue
            if S[i+dx[d]][j+dy[d]] == '.':
                cost[k][(i+dx[d])*W+(j+dy[d])] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if cost[i][k]!=INF and cost[k][j]!=INF:
                cost[i][j] = min(cost[i][j],cost[i][k]+cost[k][j])

ans = 0

for i in range(N):
    for j in range(N):
        if cost[i][j]!=INF:
            ans = max(ans,cost[i][j])

print(ans)

Solution (Python):
def main():
    h, w = map(int, input().split())
    grid = [input() for _ in [0]*h]
    ans_list = []
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                ans_list.append((i, j))
    m = 0
    for i, j in ans_list:
        q = [(i, j)]
        dist = [[-1]*w for _ in [0]*h]
        cnt = 0
        dist[i][j] = 0
        while q:
            qq = []
            cnt += 1
            while q:
                x, y = q.pop()
                if x > 0:
                    if dist[x-1][y] == -1:
                        if grid[x-1][y] == ".":
                            dist[x-1][y] = cnt
                            qq.append((x-1, y))
                if x < h-1:
                    if dist[x+1][y] == -1:
                        if grid[x+1][y] == ".":
                            dist[x+1][y] = cnt
                            qq.append((x+1, y))
                if y > 0:
                    if dist[x][y-1] == -1:
                        if grid[x][y-1] == ".":
                            dist[x][y-1] = cnt
                            qq.append((x, y-1))
                if y < w-1:
                    if dist[x][y+1] == -1:
                        if grid[x][y+1] == ".":
                            dist[x][y+1] = cnt
                            qq.append((x, y+1))
            q = qq
        m = max(m, max([max([l for l in k]) for k in dist]))
    print(m)


main()

Solution (Python):
H, W = map(int, input().split())
M = [list('
M += [['
M += [list('

n = 0
ans = 0
for y in range(1, H+1):
    for x in range(1, W+1):
        if M[y][x] == '
            continue
        n += 1
        M[y][x] = n
        q = set([(y, x)])
        count = -1
        while q:
            count += 1
            nq = set()
            for w, z in q:
                M[w][z] = n
                if M[w-1][z] != '
                    nq.add((w-1, z))
                if M[w+1][z] != '
                    nq.add((w+1, z))
                if M[w][z-1] != '
                    nq.add((w, z-1))
                if M[w][z+1] != '
                    nq.add((w, z+1))
            q = nq
        ans = ans if ans > count else count
print(ans)

Solution (Python):
h,w = map(int,input().split())
S = [input() for i in range(h)]

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

m = h*w

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

for i in range(m):
    N[i][i] = 0

for i in range(h):
    for j in range(w):
        t=w*i+j
        if S[i][j] != "
            for dt in [[-1,0],[1,0],[0,1],[0,-1]]:
                di = dt[0]
                dj=dt[1]
                ni = i+di
                nj = j+dj
                if 0 <= ni < h and 0 <= nj < w and S[ni][nj] == ".":
                    N[t][w*ni+nj] = 1








N = floyd_warshall(N)


for i in range(m):
    for j in range(m):
        if N[i][j] == float("inf"):
            N[i][j] = -1
ans = 0

for i in range(m):
    ans = max(ans, max(N[i]))
print(int(ans))

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

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

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

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


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

            cur = 0
            for d in D:
                cur = max(cur,max(d))
            ans = max(ans,cur)
    print(ans)
    return

def examE():
    N, K = LI()
    A = LI()

    return

def examF():
    return

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

if __name__ == '__main__':
    examD()

Solution (Python):
from collections import deque

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

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

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
maze = [list(input())[: -1] for _ in range(H)]

res = 0
d = [-1, 0, 1, 0]
for s in range(H * W):
  sy = s // W
  sx = s % W
  if maze[sy][sx] == "
  Q = dq([])
  Q.append(s)
  dist = [float("inf")] * (H * W)
  dist[s] = 0
  while len(Q):
    p = Q.popleft()
    py = p // W
    px = p % W
    for k in range(4):
      qy = py + d[k]
      qx = px + d[-1 - k]
      if 0 <= qy < H and (0 <= qx < W):
        if maze[qy][qx] == "
        if dist[qy * W + qx] > dist[p] + 1:
          Q.append(qy * W + qx)
          dist[qy * W + qx] = dist[p] + 1
  for x in dist:
    if x != float("inf"): res = max(res, x)
print(res)

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    H,W=map(int,input().split())
    S=[[] for _ in range(H+2)]
    S[0]=S[H+1]=['
    l=[]
    for i in range(1,H+1):
        S[i]=['
        for j,x in enumerate(S[i]):
            if x=='.':
                l.append([i,j])
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    ans=0
    for start in l:
        d=[[INF]*(W+2) for _ in range(H+2)]
        queue=deque()
        queue.append(start)
        d[start[0]][start[1]]=0
        longest=0
        while queue:
            cell=queue.popleft()
            for k in range(4):
                if S[cell[0]+dy[k]][cell[1]+dx[k]]=='.' and d[cell[0]+dy[k]][cell[1]+dx[k]]==INF:
                    queue.append([cell[0]+dy[k],cell[1]+dx[k]])
                    d[cell[0]+dy[k]][cell[1]+dx[k]]=d[cell[0]][cell[1]]+1
                    longest=max(longest,d[cell[0]+dy[k]][cell[1]+dx[k]])
        ans=max(ans,longest)
    print(ans)
        

if __name__ == '__main__':
    main()

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

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

ret = 0
for sy in range(H) :
  for sx in range(W) :
    if S[sy][sx] == '
      continue
      
    cost = [[float('inf')] * W for _ in range(H)]
    cost[sy][sx] = 0
    
    q = deque([(sy, sx, 0)])
    while q :
      cy, cx, co = q.popleft()
      for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)) :
        ny, nx = cy + dy, cx + dx
        if 0 <= ny < H and 0 <= nx < W and S[ny][nx] != '
          q.append((ny, nx, co + 1))
          cost[ny][nx] = co + 1
          ret = max(ret, co + 1)
        
print(ret)

Solution (Python):
h, w = map(int, raw_input().split())
maze = [list(raw_input()) for i in xrange(h)]

INF = 10 ** 10
my = [-1, 0, 1, 0]
mx = [0, -1, 0, 1]
def bfs(sy, sx):
    q = [(sy, sx)]
    dp = [ [INF for j in xrange(w)] for i in xrange(h) ]
    dp[sy][sx] = 0
    while q:
        (y, x) = q.pop(0)
        for (dy, dx) in zip(my, mx):
            ny = y + dy
            nx = x + dx
            if ny < 0 or nx < 0 or ny >= h or nx >= w:
                continue
            if maze[ny][nx] == '
                continue
            if dp[ny][nx] != INF:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.append((ny, nx))
    res = 0
    for i in xrange(h):
        for j in xrange(w):
            if maze[i][j] != '
                res = max(res, dp[i][j])
    return res

res = 0
for sy in xrange(h):
    for sx in xrange(w):
        if maze[sy][sx] == '
            continue
        res = max(res, bfs(sy, sx))
print res

Solution (Python):











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

Solution (Python):
h,w=map(int,input().split())
g=[input() for _ in range(h)]
def search(y,x):
	q=[(y,x)]
	vis=[[-1]*w for _ in range(h)]
	vis[y][x]=0
	while q:
		cy,cx=q.pop(0)
		for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
			ny,nx=cy+dy,cx+dx
			if 0<=ny<h and 0<=nx<w and g[ny][nx]=="." and vis[ny][nx]==-1:
				vis[ny][nx]=vis[cy][cx]+1
				q.append((ny,nx))
	return max(max(l) for l in vis)
ans=0
for i in range(h):
	for j in range(w):
		if g[i][j]==".":
			ans=max(search(i,j),ans)
print(ans)

Solution (Python):
from collections import deque
h,w = map(int, input().split())
l = [list(input()) for _ in range(h)]
ans = 0
def bfs(y,x,m):
  g = [[None if l[i][j] == '.' else -1 for j in range(w)] for i in range(h)]
  g[y][x] = 0
  q = deque()
  q.append((y,x))
  while q:
    i,j = q.popleft()
    for di,dj in ((0,1),(1,0),(-1,0),(0,-1)):
      ni = i+di; nj = j+dj
      if 0 <= ni < h and 0 <= nj < w and g[ni][nj] is None:
        g[ni][nj] = g[i][j] + 1
        q.append((ni,nj))
  return max(max(r) for r in g)

for i in range(h):
  for j in range(w):
    if l[i][j] == '.':
      d = bfs(i,j,l)
      if ans < d:
        ans = d
print(ans)