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):
INF = float('inf')

H, W = map(int, input().split())
Sss = ['

def convGrid2Graph(Sss):
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]
    sizeX, sizeY = len(Sss)-2, len(Sss[0])-2

    numV = sizeX * sizeY
    adjL = [[] for _ in range(numV)]
    for x in range(1, sizeX+1):
        for y in range(1, sizeY+1):
            if Sss[x][y] != '.': continue
            z = (x-1)*sizeY + (y-1)
            for dx, dy in dxys:
                x2, y2 = x+dx, y+dy
                if Sss[x2][y2] != '.': continue
                z2 = (x2-1)*sizeY + (y2-1)
                adjL[z].append(z2)
    return adjL

def WarshallFloyd(adjList, INF):
    numV = len(adjList)
    D = [[INF]*numV for _ in range(numV)]
    for u, adj in enumerate(adjList):
        for v in adj:
            D[u][v] = 1
        D[u][u] = 0
    for k in range(numV):
        Dk = D[k]
        for i in range(numV):
            Di = D[i]
            Dik = Di[k]
            for j in range(numV):
                D2 = Dik + Dk[j]
                if D2 < Di[j]:
                    D[i][j] = D2
    return D

adjL = convGrid2Graph(Sss)

distss = WarshallFloyd(adjL, INF)

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if distss[i][j] != INF:
            ans = max(ans, distss[i][j])

print(ans)

Solution (Python):
from collections import deque
H, W =  map(int, input().split())
S=[]
for _ in range(H):
    S.append(input())
vx = [1, 0, -1, 0]
vy = [0, 1, 0, -1]
ans = 0

def func(si, sj):
    queue = deque([si, sj])  
    seen = [[-1]*W for _ in range(H)]
    seen[si][sj] = 0
    while queue:
        x = queue.popleft()
        y = queue.popleft()
        
        for i in range(4):
            nx = x + vx[i]
            ny = y + vy[i]
            if nx<0 or nx>=H or ny<0 or ny>=W:
                continue
            if S[nx][ny]=="
                continue
            seen[nx][ny]=seen[x][y]+1
            queue.append(nx)
            queue.append(ny)
    return seen[x][y]
    
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            ans = max(ans, func(i, j))
print(ans)

Solution (Python):
H,W = map(int,input().split())
maze = [["
from copy import deepcopy
grid = deepcopy(maze)
ans = 0

from collections import deque
for sh in range(H+2):
    for sw in range(W+2):
        
        if grid[sh][sw] == '.':
            
            grid[sh][sw] = 0
            depth = 0
            que = deque()
            que.append([sh,sw])
            dxs = [-1,1,0,0]
            dys = [0,0,-1,1]
            while que:
                h,w = que.popleft()
                for i in range(4):
                    dx = dxs[i]
                    dy = dys[i]

                    if grid[h+dx][w+dy] == '.':
                        grid[h+dx][w+dy] = grid[h][w] + 1
                        que.append([h+dx,w+dy])
                        depth = max(depth,grid[h+dx][w+dy])
            ans = max(ans,depth)
        grid = deepcopy(maze)
        
print(ans)

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

H,W = map(int,readline().split())
S = [None] * H
for i in range(H):
  S[i] = readline().rstrip()

ans = 0
from collections import deque
cases = ((1,0),(-1,0),(0,1),(0,-1))
for i in range(H):
  for j in range(W):
    q = deque([[i,j,0]])
    seen = set()
    while q:
      y,x,d = q.popleft()
      if S[y][x] == "
        continue
      if (y,x) in seen:
        continue
      seen.add((y,x))
      if d > ans:
        ans = d
      for c in cases:
        if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
          q.append([y + c[0], x + c[1], d + 1])

print(ans)

Solution (Python):



from collections import deque






def solve(H, W, Ss):
    Ss = ['
    Ss = ['
    
    
    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if Ss[i][j] == '
                continue
            visited = [[-1] * (W + 2) for _ in range(H + 2)]
            now = 0
            visited[i][j] = now
            q = deque([(i, j, now)])
            while q:
                x, y, n = q.popleft()
                
                
                
                for x1, y1 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                    if Ss[x1][y1] == '.' \
                            and visited[x1][y1] < 0:
                        q.append((x1, y1, n + 1))
                        visited[x1][y1] = n + 1
            ans = max(ans, max([max(v) for v in visited]))

    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ss = [input() for _ in range(H)]
    solve(H, W, Ss)

Solution (Python):



from collections import deque




def solve(H, W, Ss):
    Ss = ['
    Ss = ['
    
    
    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if Ss[i][j] == '
                continue
            visited = [[-1] * (W + 2) for _ in range(H + 2)]
            now = 0
            visited[i][j] = now
            q = deque([(i, j, now)])
            while q:
                x, y, n = q.popleft()
                
                
                
                if Ss[x + 1][y] == '.' \
                        and visited[x + 1][y] < 0:
                    q.append((x + 1, y, n + 1))
                    visited[x + 1][y] = n + 1
                if Ss[x - 1][y] == '.' \
                        and visited[x - 1][y] < 0:
                    q.append((x - 1, y, n + 1))
                    visited[x - 1][y] = n + 1
                if Ss[x][y + 1] == '.' \
                        and visited[x][y + 1] < 0:
                    q.append((x, y + 1, n + 1))
                    visited[x][y + 1] = n + 1
                if Ss[x][y - 1] == '.' \
                        and visited[x][y - 1] < 0:
                    q.append((x, y - 1, n + 1))
                    visited[x][y - 1] = n + 1
            ans = max(ans, max([max(v) for v in visited]))
    print(ans)


if __name__ == '__main__':
    H, W = map(int, input().split())
    Ss = [input() for _ in range(H)]
    solve(H, W, Ss)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


def lcm(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)


def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True



def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


h, w = map(int, input().split())
s = [[j for j in input()] for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        queue = deque([[i, j, 0]])
        visited = [[0 for _ in range(w)] for _ in range(h)]
        while queue:
            y, x, cnt = queue.popleft()
            if not (0 <= y < h and 0 <= x < w) or visited[y][x] == 1 or s[y][x] == "
                continue
            ans = max(ans, cnt)
            visited[y][x] = 1
            for p in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
                y2 = y + p[0]
                x2 = x + p[1]
                queue.append([y2, x2, cnt + 1])

print(ans)

Solution (Python):
import collections, copy

h, w = map(int, input().split())
maze = []
maze.append("
for i in range(h):
    maze.append("
maze.append("
dis = []
for i in range(h + 2):
    temp = [-1] * (w + 2)
    dis.append(temp)

def search(x, y):
    dis2 = copy.deepcopy(dis)
    move = [[-1, 0], [1, 0], [0, 1], [0, -1]]
    queue = collections.deque([[x, y]])
    dis2[x][y] = 0
    while queue:
        test = queue.popleft()
        for i in move:
            place = [test[0] + i[0], test[1] + i[1]]
            if maze[place[0]][place[1]] == ".":
                if dis2[place[0]][place[1]] == -1:
                    dis2[place[0]][place[1]] = dis2[test[0]][test[1]] + 1
                    queue.append(place)
    return max([max([dis2[i][j] for j in range(w + 2)]) for i in range(h + 2)])

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i + 1][j + 1] == ".":
            dist = search(i + 1, j + 1)
            ans = max(ans, dist)
print(ans)

Solution (Python):
from collections import deque
def bfs(sy,sx):
  q=deque([[sy,sx]])
  visited[sy][sx]=0
  while q:
    y,x=q.popleft()
    for dy,dx in ([1,0],[-1,0],[0,1],[0,-1]):
      ny,nx=y+dy,x+dx
      if ny<0 or ny>h-1 or nx<0 or nx>w-1 or path[ny][nx]=="
      if path[ny][nx]=="." and visited[ny][nx]==-1:
        visited[ny][nx]=visited[y][x]+1
        q.append([ny,nx])
  res=-1
  for i in range(h):
    for j in range(w):
      res=max(visited[i][j],res)
  return res

h,w=map(int,input().split())
path=[input() for i in range(h)]
visited=[[-1]*w for i in range(h)]
sy,sx=0,0
gy,gx=0,0
ans=0
for i in range(h):
  for j in range(w):
    if path[i][j]=="
    sy=i
    sx=j
    visited=[[-1]*w for _ in range(h)]
    t=bfs(sy,sx)
    ans=max(t,ans)
print(ans)

Solution (Python):
from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Sss = ['

def bfsGridGraph(Sss, xS, yS, INF):
    dxys = [(-1,0), (1,0), (0,-1), (0,1)]
    distss = [[(INF if S != '
    distss[xS][yS] = 0
    Q = deque([(xS, yS)])
    while Q:
        x, y = Q.popleft()
        dist = distss[x][y]
        for dx, dy in dxys:
            x2, y2 = x+dx, y+dy
            if distss[x2][y2] == INF:
                distss[x2][y2] = dist + 1
                Q.append((x2, y2))
    return distss

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if Sss[i][j] == '
        distss = bfsGridGraph(Sss, i, j, INF)
        maxDist = max(map(max, distss))
        ans = max(ans, maxDist)

print(ans)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[i][j] = 0
        que = deque([[i,j]])
        while que:
            h,w = que.pop()
            for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
                nh = h+dh
                nw = w+dw
                if nh < 0 or nw < 0 or nh >= H or nw >= W:
                    continue
                if maze[nh][nw] == '
                    continue
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w]+1
                    que.appendleft([nh,nw])
        ans = max(ans,max([max(d) for d in dist]))
print(ans)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10**9)
mod = 10**9+7

H,W = I()
maze = [list(s()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[i][j] = 0
        que = deque([[i,j]])
        while que:
            h,w = que.pop()
            for dh,dw in [[1,0],[0,1],[-1,0],[0,-1]]:
                nh = h+dh
                nw = w+dw
                if nh < 0 or nw < 0 or nh >= H or nw >= W:
                    continue
                if maze[nh][nw] == '
                    continue
                if dist[nh][nw] == -1:
                    dist[nh][nw] = dist[h][w]+1
                    que.appendleft([nh,nw])
        ans = max(ans,max([max(d) for d in dist]))
print(ans)

Solution (Python):
from collections import deque
m=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=map(int,input().split())
l=list()
l.append('
for i in range(h):
    j=input()
    l.append('
l.append('
def bfs(a,b):
  s=[[-1 for j in i] for i in l]
  s[a][b]=0
  q=deque([[a,b]])
  while len(q)>0:
    x,y=q.popleft()
    for i,j in m:
      if l[x+i][y+j]=='.' and s[x+i][y+j]==-1:
        q.append([x+i,y+j])
        s[x+i][y+j]=s[x][y]+1
        num = s[x+i][y+j]
  return num
ans = []
for i in range(h+2):
  for j in range(w+2):
    if l[i][j] == '.':
      ans.append(bfs(i,j))
print(max(ans))

Solution (Python):
from collections import deque

H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
XY = [(-1, 0), (1, 0), (0, 1), (0, -1)]

t_max = 0
for i in range(H):
    for j in range(W):
        step = [[0]*W for _ in range(H)]
        visited = [[False]*W for _ in range(H)]
        queue = deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            if maze[x][y] == "
                continue
            if visited[x][y]:
                continue
            for dx, dy in XY:
                nx = x + dx
                ny = y + dy
                if 0 <= nx <= H-1 and 0 <= ny <= W-1:
                    step[nx][ny] = step[x][y] + 1
                    queue.append((nx, ny))
                    t_max = max(t_max, step[nx][ny])
            visited[x][y] = True

print(t_max-1)

Solution (Python):

import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)

H, W = (None, None)
S = None


def bfs(h, w):
    if S[h][w] == '
        return 0
    q = queue.Queue()
    q.put((w, h))
    steps = [[-1 for _ in range(W)]for _ in range(H)]
    steps[h][w] = 0
    while not q.empty():
        p = q.get()
        DIR = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for d in DIR:
            n = (p[0] + d[0], p[1] + d[1])
            if not (0 <= n[0] < W and 0 <= n[1] < H):
                continue
            if steps[n[1]][n[0]] != -1:
                continue
            if S[n[1]][n[0]] == '
                continue
            steps[n[1]][n[0]] = steps[p[1]][p[0]] + 1
            q.put(n)
    res = 0
    for s in steps:
        res = max(res, max(s))
    return res


def solve():
    global H, W, S
    H, W = Scanner.map_int()
    S = Scanner.string_list(H)
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, bfs(h, w))
    print(ans)


def main():
    
    
    
    
    
    solve()


if __name__ == "__main__":
    main()

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

def dfs(h, w):
    Step = [[0]*W for _ in range(H)]
    Step[h][w] = 0
    stack = deque([(h, w)])
    visited =[[False]*W for _ in range(H)]
    while stack:
        i, j = stack.popleft()
        visited[i][j] = True
        for dx, dy in XY:
            x = i + dx
            y = j + dy
            if 0 <= x <= H-1 and 0 <= y <= W-1:
                if x == h and y == w:
                    continue
                if Step[x][y]:
                    continue
                if S[x][y] == '
                    continue
                stack.append((x, y))
                Step[x][y] = Step[i][j] + 1
    ans = 0
    for step in Step:
        ans = max(ans, max(step))
    return ans

for h in range(H):
    for w in range(W):
        if S[h][w] != '
            ans = max(ans, dfs(h, w))

print(ans)

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

from collections import deque

S = [input() for i in range(H)]
directions = [[0,1],[1,0],[-1,0],[0,-1]]


counter = 0


for x in range(H):
    for y in range(W):
        if S[x][y]=="
            continue
         
        que =  deque([[x,y]])
        memory = [[-1]*W for _ in range(H)]
        memory[x][y]=0
       
        while True:
            if len(que)==0:
               break
            h,w = que.popleft()

            for i,k in directions:
                x_new,y_new = h+i,w+k

                if not(0<=x_new<=H-1) or not(0<=y_new<=W-1) :
                    continue
                
                elif not memory[x_new][y_new]==-1 or S[x_new][y_new]=="
                    continue

                memory[x_new][y_new] = memory[h][w]+1
                que.append([x_new,y_new]) 
        counter = max(counter,max(max(i) for i in memory))

print(counter)

Solution (Python):
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

from collections import deque

h,w = nm()

s = []

for y in range(h):
  s.append([_ for _ in input()])



def bfs(sx,sy,visited):
  xx=[1,-1,0,0]
  yy=[0,0,1,-1]
  
  q=deque([(sx,sy)])
  visited[sy][sx] = 0

  while q:
    _ = q.popleft()
    x=_[0]
    y=_[1]

    for i in range(4):
      nx = x + xx[i]
      ny = y + yy[i]
      
      if 0 <= nx < w and 0 <= ny < h:
        if s[ny][nx] == '.' and visited[ny][nx]==-1:
          visited[ny][nx] = visited[y][x]+1
          q.append((nx,ny))
  mx=0
  for y in range(h):
    for x in range(w):
      mx = max(mx,visited[y][x])
  return mx

MX = 0

for sx in range(w):
  for sy in range(h):
    if s[sy][sx] == '.':
      b = bfs(sx,sy,[[-1]*w for _ in range(h)])
      MX = max(MX,b)

print(MX)

Solution (Python):
from collections import deque

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



def bfs(a, b):  
    mx_dist = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dist = [[-1] * w for i in range(h)]
    dist[a][b] = 0
    que = deque([])
    que.append((a, b))
    while que:
        y, x = que.popleft()
        D = dist[y][x]
        for i in range(4):
            X = x + dx[i]
            Y = y + dy[i]
            if 0 <= Y and Y <= h - 1 and X <= w - 1 and 0 <= X:
                if meiro[Y][X] == ".":
                    if dist[Y][X] == -1:
                        dist[Y][X] = D + 1
                        que.append((Y, X))
                        mx_dist = max(mx_dist, D + 1)

    return mx_dist


saidai = 0
for i in range(h):
    for j in range(w):
        if meiro[i][j] == ".":
            saidai = max(saidai, bfs(i, j))
print(saidai)

Solution (Python):
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7

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

dd = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(h):
    for j in range(w):
        if ini_grid[i][j] == '.':
            temp_grid = [row[:] for row in ini_grid]
            dis_grid = [[-1]*w for i in range(h)]
            dis_grid[i][j] = 0
            dq = deque([(i, j, 0)])
            temp_grid[i][j] = '
            while dq:
                curr = dq.popleft()
                for di, dj in dd:
                    ni = curr[0] + di
                    nj = curr[1] + dj 
                    if (0 <= ni <= h-1) and (0 <= nj <= w-1) and temp_grid[ni][nj] == '.':
                        temp_grid[ni][nj] = '
                        dis_grid[ni][nj] = curr[2] + 1
                        dq.append((ni, nj, curr[2] + 1))
                        if curr[2] + 1 > ans:
                            ans = curr[2] + 1

print(ans)

Solution (Python):
import networkx as nx

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

G = nx.Graph()

for h in range(H):
    for w in range(W - 1):
        if maze[h][w] == maze[h][w + 1] == '.':
            G.add_edge((h, w), (h, w + 1))
for h in range(H - 1):
    for w in range(W):
        if maze[h][w] == maze[h + 1][w] == '.':
            G.add_edge((h, w), (h + 1, w))


def bfs(sy, sx):
    d = dict()
    d[(sy, sx)] = 0
    for coordinate_from, coordinate_to in nx.bfs_edges(G, (sy, sx)):
        d[coordinate_to] = d[coordinate_from] + 1
    return max(d.values())


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            ans = max(ans, bfs(y, x))
print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]

    res = []
    for sh in range(H):
        for sw in range(W):
            if grid[sh][sw] == "
                continue
            maze = [[f_inf] * W for _ in range(H)]
            maze[sh][sw] = 0
            que = deque([[sh, sw]])
            while que:
                h, w = que.popleft()
                for dh, dw in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    next_h, next_w = h + dh, w + dw
                    if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W or grid[next_h][
                        next_w] == "
                        continue
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
                        res.append(maze[next_h][next_w])
    print(max(res))


if __name__ == '__main__':
    resolve()

Solution (Python):
import networkx as nx

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

G = nx.grid_2d_graph(H, W)
for h in range(H):
    for w in range(W):
        
        if maze[h][w] == '
            for dh, dw in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                if ((h - dh, w - dw), (h, w)) in G.edges():
                    G.remove_edge((h - dh, w - dw), (h, w))


def bfs(sy, sx):
    d = dict()
    d[(sy, sx)] = 0
    for coordinate_from, coordinate_to in nx.bfs_edges(G, (sy, sx)):
        d[coordinate_to] = d[coordinate_from] + 1
    return max(d.values())


ans = 0
for y in range(H):
    for x in range(W):
        if maze[y][x] == '.':
            ans = max(ans, bfs(y, x))
print(ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    start = []
    for h in range(H):
        for w in range(W):
            if S[h][w] != "
                start.append([h, w])

    res = 0
    for sh, sw in start:
        maze = [[f_inf] * W for _ in range(H)]
        maze[sh][sw] = 0
        que = deque([[sh, sw]])
        while que:
            h, w = que.popleft()
            for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                elif S[next_h][next_w] == "
                    continue
                else:
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
        ma = 0
        for h in range(H):
            for w in range(W):
                if S[h][w] != "
                    ma = max(ma, maze[h][w])
        res = max(res, ma)
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    start = []
    for h in range(H):
        for w in range(W):
            if S[h][w] != "
                start.append([h, w])

    res = 0
    for sh, sw in start:
        maze = [[f_inf] * W for _ in range(H)]
        maze[sh][sw] = 0
        que = deque([[sh, sw]])
        while que:
            h, w = que.popleft()
            for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                next_h, next_w = h + dh, w + dw
                if next_h < 0 or next_h >= H or next_w < 0 or next_w >= W:
                    continue
                elif S[next_h][next_w] == "
                    continue
                else:
                    if maze[next_h][next_w] > maze[h][w] + 1:
                        maze[next_h][next_w] = maze[h][w] + 1
                        que.append([next_h, next_w])
        ma = 0
        for h in range(H):
            for w in range(W):
                if S[h][w] != "
                    ma = max(ma, maze[h][w])
        res = max(res, ma)
    print(res)


if __name__ == '__main__':
    resolve()