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 deque
INF = 1001001001
di = (-1, 0, 1, 0)
dj = ( 0,-1, 0, 1)

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

ans = 0
for si in range(h):
    for sj in range(w):
        if s[si][sj] == '
        dist = [[INF] * w for _ in range(h)]
        dist[si][sj] = 0
        q = deque([(si,sj)])
        while q:
            i,j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if (ni<0 or ni>=h or nj<0 or nj>=w): continue
                if s[ni][nj] == '
                if dist[ni][nj] != INF: continue
                q.append((ni,nj))
                dist[ni][nj] = dist[i][j] + 1
        for i in range(h):
            for j in range(w):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
from collections import deque
from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
inf = float('inf')


def flatten(list_of_lists):
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for _ in range(W)] for _ in range(H)]
    queue = deque([(end, start)])
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '
                queue.appendleft((ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


m = 0
for i in range(W):
    for j in range(H):
        if M[j][i] != "

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)

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

ans = 0
for si in range(H):
    for sj in range(W):
        if S[si][sj] == '
        dist = [[INF]*W for _ in range(H)]
        dist[si][sj] = 0
        q = deque([(si, sj)])
        while q:
            i, j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if (ni<0 or ni>=H or nj<0 or nj>=W): continue
                if S[ni][nj] == '
                if dist[ni][nj] != INF: continue
                q.append([ni, nj])
                dist[ni][nj] = dist[i][j] + 1
        for i in range(H):
            for j in range(W):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
from collections import deque
from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
inf = float('inf')


def flatten(list_of_lists):
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = deque([(end, start)])
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '
                queue.appendleft((ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


m = 0
for i in range(W):
    for j in range(H):
        if M[j][i] != "

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)

Solution (Python):
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    m = []
    for _ in range(H):
        l = input()
        m.append(l)
    edge = []
    v = H * W
    for i in range(H):
        for j in range(W):
            t = i * W + j
            edge.append([10 ** 9] * v)
            if m[i][j] == '.':
                if i > 0 and m[i-1][j] == '.':
                    edge[t][(i-1) * W + j] = 1
                if j > 0 and m[i][j -1] == '.':
                    edge[t][i * W + j - 1] = 1
                if i < H-1 and m[i+1][j] == '.':
                    edge[t][(i + 1)*W + j] = 1
                if j < W - 1 and m[i][j+1] == '.':
                    edge[t][i * W + j + 1] = 1
    G = csgraph_from_dense(edge, null_value=10**9)
    d = floyd_warshall(G)
    m = 0
    for i in range(v):
        for j in range(v):
            if d[i][j] != float('inf') and d[i][j] > m:
                m = d[i][j]
    print(int(m))
main()

Solution (Python):
h,w=map(int,input().split())
s=[input() for _ in range(h)]
from collections import deque
di=[-1,0,1,0]
dj=[0,-1,0,1]
INF=1001001001
ans=0
for si in range(h):
    for sj in range(w):
        if s[si][sj]=='
        dist=[[INF]*w for _ in range(h)]
        dist[si][sj]=0
        q=deque([(si,sj)])
        while len(q)>0:
            i,j=q.popleft()
            for dir in range(4):
                ni=i+di[dir]
                nj=j+dj[dir]
                if(ni<0 or ni>=h or nj<0 or nj>=w): continue
                if(s[ni][nj]=='
                if(dist[ni][nj]!=INF): continue
                q.append((ni,nj))
                dist[ni][nj]=dist[i][j]+1
        for i in range(h):
            for j in range(w):
                if dist[i][j]==INF: continue
                ans=max(ans,dist[i][j])
print(ans)

Solution (Python):
import queue

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

for h in range(H):
    row = input()
    S.append(row)

INF = 100100100

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

ans = 0

for si in range(H):
    for sj in range(W):
        
        s = S[si][sj]
        if s == '
            continue

        dist = [[INF] * W for i in range(H)]
        q = queue.Queue()

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

        update(si, sj, 0)
        while not q.empty():
            p = q.get()
            i = p[0]
            j = p[1]
            for dn in range(4):
                ni = i + di[dn]
                nj = j + dj[dn]
                if ni < 0 or ni >= H or nj < 0 or nj >= W:
                    continue
                if S[ni][nj] == '
                    continue
                update(ni, nj, dist[i][j] + 1)

        for i in range(H):
            for j in range(W):
                if dist[i][j] == INF:
                    continue
                ans = max(ans, dist[i][j])

print(ans)

Solution (Python):
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, csgraph_from_dense, floyd_warshall
def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    m = [[0] * (W * H) for _ in range(W * H)]
    def loc(h, w):
        return h * W + w
    def con(h1, w1, h2, w2):
        m[loc(h1, w1)][loc(h2, w2)] = 1
        m[loc(h2, w2)][loc(h1, w1)] = 1

    for h in range(H):
        for w in range(W):
            if S[h][w] == '
                continue
            if h > 0:
                if S[h - 1][w] == '.':
                    con(h, w, h - 1, w)
            if h < H - 1:
                if S[h + 1][w] == '.':
                    con(h, w, h + 1, w)
            if w > 0:
                if S[h][w - 1] == '.':
                    con(h, w, h, w - 1)
            if w < W - 1 and S[h][w + 1] == '.':
                con(h, w, h, w + 1)
    g = csgraph_from_dense(m)
    EE = floyd_warshall(g)
    print(int(np.max(EE[~np.isinf(EE)])))


main()

Solution (Python):
H, W = map(int, input().split())
S = [0 for j in range(H)]
for i in range(H):
    S[i] = list(str(input()))
TF = [[False for i in range(W)] for j in range(H)]
first = [0,0]
for j in range(H):
    for i in range(W):
        if S[j][i] == '
            TF[j][i] = True
        else:
            first = [j,i]
distance = [[0 for i in range(W)] for j in range(H)]
def bfs(s):
    Q = []
    TF[s[0]][s[1]] = True
    Q.append(s)
    while Q:
        v = Q.pop(0)
        next = [[v[0], v[1]+1], [v[0], v[1]-1],[v[0]+1, v[1]], [v[0]-1,v[1]]]
        for u in next:
            if u[0] >= 0 and u[0] <= H-1 and u[1] >= 0 and u[1] <= W-1:
                if TF[u[0]][u[1]] == False:
                    distance[u[0]][u[1]] = distance[v[0]][v[1]] + 1
                    TF[u[0]][u[1]] = True
                    Q.append(u)

maxd = 0
for k in range(H):
    for l in range(W):
        if S[k][l] == '.':
            first = [k,l]
            TF = [[False for i in range(W)] for j in range(H)]
            for j in range(H):
                for i in range(W):
                    if S[j][i] == '
                        TF[j][i] = True
            distance = [[0 for i in range(W)] for j in range(H)]
            bfs(first)
            
            
            for j in range(H):
                for i in range(W):
                    maxd = max(maxd,distance[j][i])

print(maxd)

Solution (Python):
import unittest
import collections


class TestD(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think(['...', '...', '...']), 4)

    def test_2(self):
        self.assertEqual(think(['...


def solve():
    maze = read()
    result = think(maze)
    write(result)


def read():
    h, w = read_int(2)
    maze = []
    for _ in range(h):
        maze.append(read_line(n=w))
    return maze


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(maze):
    wall = '
    h, w = get_height_and_width_of(maze)
    longest_path_length = 0

    for y in range(h):
        for x in range(w):
            if maze[y][x] == wall:
                continue
            longest_path_length = max(longest_path_length, search(maze, x, y, wall))

    return longest_path_length


def write(result):
    print(result)


def get_height_and_width_of(maze):
    return len(maze), len(maze[0])


def search(maze, x, y, wall):
    h, w = get_height_and_width_of(maze)
    inf = h * w + 1

    dp = prepare_dp_table(h, w, inf)

    return bfs(maze, dp, w, h, x, y, wall)


def prepare_dp_table(h, w, inf):
    return [[inf for _ in range(w)] for _ in range(h)]


def bfs(maze, dp, w, h, x, y, wall):
    queue = collections.deque([])
    queue.append((x, y, 0))

    max_distance = 0

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

    while queue:
        xx, yy, distance = queue.popleft()
        if dp[yy][xx] <= distance:
            continue
        dp[yy][xx] = distance
        max_distance = max(max_distance, distance)

        for dx, dy in diff_xy:
            nx, ny = xx + dx, yy + dy
            if not in_range(w, h, nx, ny):
                continue
            if maze[ny][nx] == wall:
                continue
            if dp[ny][nx] <= distance + 1:
                continue
            queue.append((nx, ny, distance + 1))

    return max_distance


def in_range(w, h, x, y):
    return 0 <= x < w and 0 <= y < h


if __name__ == '__main__':
    
    solve()

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

def clear_maze(sx, sy, maze):
    INF = -float('infinity')
    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]

    queue = deque([(sx, sy)])
    distance[sx][sy] = 0
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    while queue:
        x, y = queue.pop()
        
        
        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if (0 <= nx < field_x_length) and (0 <= ny < field_y_length):
                if maze[nx][ny] != '
                    queue.appendleft((nx, ny))
                    distance[nx][ny] = distance[x][y] + 1
    MAX = 0
    for row in range(field_x_length):
        for col in range(field_y_length):
            MAX = max(MAX, distance[row][col])
    return MAX
    

pairs = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            pairs.append([i, j])

MAX = 0
for sx, sy in pairs:
    r = clear_maze(sx, sy, maze)
    MAX = max(MAX, r)
print(MAX)

Solution (Python):



def calc_dist(s, start_i, start_j, h, w):
    from collections import deque

    result = 0
    
    d = deque()
    
    d.append((start_i, start_j))
    
    dist = [[0 for _ in range(w)] for _ in range(h)]
    
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        
        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            
            if s[ny][nx] == '
                continue

            
            
            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))
            result = max(result, dist[ny][nx])

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = 0

    
    
    
    
    for start_i in range(h):
        for start_j in range(w):
            
            if s[start_i][start_j] == '
                continue

            ans = max(ans, calc_dist(s, start_i, start_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):



def calc_dist(s, start_i, start_j, h, w):
    from collections import deque

    result = 0
    
    d = deque()
    
    d.append((start_i, start_j))
    
    dist = [[0 for _ in range(w)] for _ in range(h)]
    
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        
        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            
            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            
            if s[ny][nx] == '
                continue

            
            
            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))
            result = max(result, dist[ny][nx])

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = 0

    
    
    
    
    for start_i in range(h):
        for start_j in range(w):
            
            if s[start_i][start_j] == '
                continue

            ans = max(ans, calc_dist(s, start_i, start_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
x,y=map(int,input().split())
lol=[]
for _ in range(x):
    lol.append(list(input()))
w=0
for i in range(x):
    for j in range(y):
        if lol[i][j]==".":
            yo=[]
            for k in lol:
                yo.append(k[:])
            
            s=[[i,j]]
            v=[0]
            while len(s)!=0:
                l=s.pop(0)
                k=v.pop(0)
                w=max(w,k)
                a=l[0]
                b=l[1]
                yo[a][b]="
                if 0<=a+1<x:
                    if yo[a+1][b]==".":
                        s.append([a+1,b])
                        v.append(k+1)
                        yo[a+1][b]="
                if 0<=a-1<x:
                    if yo[a-1][b]==".":
                        s.append([a-1,b])
                        v.append(k+1)
                        yo[a-1][b]="
                if 0<=b-1<y:
                    if yo[a][b-1]==".":
                        s.append([a,b-1])
                        v.append(k+1)
                        yo[a][b-1]="
                if 0<=b+1<y:
                    if yo[a][b+1]==".":
                        s.append([a,b+1])
                        v.append(k+1)
                        yo[a][b+1]="
print(w)

Solution (Python):
from collections import deque
INF = 1001001001
di = [-1, 0, 1, 0]
dj = [ 0,-1, 0, 1]

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


ans = 0
for si in range(H):
    for sj in range(W):
        if (S[si][sj] == '
        dist = [[INF]*W for _ in range(H)]
        dist[si][sj] = 0
        q = deque([(si, sj)])
        while len(q) > 0:
            i, j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if (ni<0 or ni>=H or nj<0 or nj>=W): continue
                if (S[ni][nj] == '
                if (dist[ni][nj] != INF): continue
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1
        for i in range(H):
            for j in range(W):
                if dist[i][j] == INF: continue
                ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
INF=10**9+7
H,W=map(int,input().split())
S=list()
q=list()

S.append(["
for i in range(H):
  S.append(["
S.append(["


m=0
for y in range(1,H+1):
  for x in range(1,W+1):
    if S[y][x]=="
      continue
    D=[[INF]*(W+2) for _ in range(H+2)]
    D[y][x]=0
    q.clear()
    q.append([x,y])
    while len(q)>0:
      c=list(q.pop(0))
      for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        ny,nx=c[1]+dy,c[0]+dx
        if S[ny][nx]=="." and D[ny][nx]==INF:
          D[ny][nx]=D[c[1]][c[0]]+1
          q.append([nx,ny])
          m=max(m,D[ny][nx])
print(m)

Solution (Python):



def calc_dist(s, start_i, start_j, h, w):
    from collections import deque

    result = 0
    d = deque()
    d.append((start_i, start_j))
    dist = [[0 for _ in range(w)] for _ in range(h)]
    visited = [[False for _ in range(w)] for _ in range(h)]
    visited[start_i][start_j] = True
    dxy = [(1, 0), (-1, 0), (0, -1), (0, 1)]

    while d:
        hd, wd = d.popleft()

        for dx, dy in dxy:
            nx = wd + dx
            ny = hd + dy

            if nx < 0 or nx >= w or ny < 0 or ny >= h:
                continue

            if s[ny][nx] == '
                continue

            if visited[ny][nx]:
                continue

            visited[ny][nx] = True
            dist[ny][nx] = dist[hd][wd] + 1
            d.append((ny, nx))
            result = max(result, dist[ny][nx])

    return result


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    ans = 0

    
    
    
    for start_i in range(h):
        for start_j in range(w):
            if s[start_i][start_j] == '
                continue

            ans = max(ans, calc_dist(s, start_i, start_j, h, w))

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

dX = [1, 0, -1, 0]
dY = [0, 1, 0, -1]

def bfs(m, c):
    q = []
    d = defaultdict(lambda: 0xffffffff)
    q.append(c)
    d[c] = 0
    while len(q) != 0:
        c = q.pop(0)
        for dx, dy in zip(dX, dY):
            nx = dx + c[0]
            ny = dy + c[1]
            if ny < 0 or ny >= len(m):
                continue
            if nx < 0 or nx >= len(m[0]):
                continue
            if m[ny][nx] == "
                continue
            if d[(nx, ny)] != 0xffffffff:
                continue
            d[(nx, ny)] = d[c] + 1
            q.append((nx, ny))
    return d

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

maxi = 0
for sx, sy in [(x, y) for x in range(0, W) for y in range(0, H)]:
    if S[sy][sx] == "
        continue
    d = bfs(S, (sx, sy))
    for x, y in [(x, y) for x in range(0, W) for y in range(0, H)]:
        if S[y][x] == "
            continue
        maxi = max(maxi, d[(x, y)])
print(maxi)

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

def is_kabe(v1, v2):
    if S[v1][v2] == '
        return True
    else:
        return False

def bfs(v1, v2):
    m = []
    for i in range(H):
        m.append([None]*W)

    m[v1][v2] = 0
    q = [[v1, v2]]
    while q:
        mass = q.pop(0)
        
        
        a = mass[0]
        b = mass[1]
        next_cost = m[a][b] + 1
        if a - 1 >= 0:
            up = m[a-1][b]
            if not is_kabe(a-1, b) and up is None:
                m[a-1][b] = next_cost
                q.append([a-1, b])
        if a + 1 < H:
            down = m[a+1][b]
            if not is_kabe(a+1, b) and down is None:
                m[a+1][b] = next_cost
                q.append([a+1, b])
        if b - 1 >= 0:
            left = m[a][b-1]
            if not is_kabe(a, b-1) and left is None:
                m[a][b-1] = next_cost
                q.append([a, b-1])
        if b + 1 < W:
            right = m[a][b+1]
            if not is_kabe(a, b+1) and right is None:
                m[a][b+1] = next_cost
                q.append([a, b+1])

    
    
    
    
    
    
    
    

    mx = 0
    for i in range(H):
        for j in range(W):
            cost = m[i][j]
            if cost is not None:
                mx = max(mx, cost)
    return mx


r = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        x = bfs(i, j)
        r = max(r, x)
print(r)

Solution (Python):
h,w=map(int,input().split())
inf=float("inf")
d=((-1,0),(1,0),(0,-1),(0,1))
S=[["
S.extend([["
S.append(["

def dist(a,b):
  if S[a][b]=="
    return 0
  else:
    D=[[inf]*(w+2) for _ in range(h+2)]
    D[a][b]=0
    Visit=[100*a+b]
    while Visit:
      v=Visit.pop()
      va,vb=v//100,v%100
      for dx,dy in d:
        if S[va+dx][vb+dy]=="
          continue
        elif D[va+dx][vb+dy]>D[va][vb]+1:
          Visit.append((va+dx)*100+(vb+dy))
          D[va+dx][vb+dy]=D[va][vb]+1
    ret=0
    for i in range(h):
      for j in range(w):
        if D[i+1][j+1]<inf:
          ret=max(ret,D[i+1][j+1])
    return ret
ans=0
for i in range(h):
  for j in range(w):
    ans=max(dist(i+1,j+1),ans)
print(ans)

Solution (Python):
import heapq
H,W = map(int,input().split())
S = [0 for i in range(H)]
s = [0,0]
g = [0,0]
for i in range(H):
    S[i] = ["
S = [["
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
'''
枠を壁としているので，1 <= i <= H+1, 1<= j <= W+1
dp
'''
def search(x,y):
    if S[x+1][y+1] == "
    else :
        dp = [[-float("inf") for _ in range(W)] for p in range(H)]
        dp[x][y] = 0
        heap = []
        heapq.heapify(heap)
        heapq.heappush(heap,(0,x,y))
        m = 0
        while True :
            if len(heap) == 0 :
                break
            else:
                cost,a,b = heapq.heappop(heap)
                for i in range(4):
                    x_ = a + dx[i]
                    y_ = b + dy[i]
                    if S[x_+1][y_+1] == "
                        continue
                    if dp[x_][y_] != -float("inf") :
                        continue
                    dp[x_][y_] = cost + 1
                    heapq.heappush(heap, (cost + 1, x_, y_))
                    if m < dp[x_][y_] : m = dp[x_][y_]
        return m
ans = 0
for i in range(H):
    for j in range(W):
        if ans < search(i,j):
            ans = search(i,j)
print(ans)

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

for y in range(H):
  for x in range(W):
    if S[y][x]=="
      continue
    D=[[400]*W for i in range(H)]
    D[y][x]=0
    q=[]
    q.append([x,y])
    while len(q)>0:
      c=list(q.pop(0))
      for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
        if c[1]+dy<0 or c[1]+dy>=H:
          continue
        if c[0]+dx<0 or c[0]+dx>=W:
          continue
        if S[c[1]+dy][c[0]+dx]==".":
          if D[c[1]+dy][c[0]+dx]>D[c[1]][c[0]]+1:
            D[c[1]+dy][c[0]+dx]=D[c[1]][c[0]]+1
            q.append([c[0]+dx,c[1]+dy])
    A=[[D[y][x] if D[y][x]!=400 else -1 for x in range(W)] for y in range(H)]
    for i in range(H):
      m=max(m,max(A[i]))
print(m)

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

ans = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == ".":
            q = [(i, j)]
            dist = [[-1]*w for _ in range(h)]
            dist[i][j] = 0
            while q:
                x, y = q.pop(0)
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x+dx, y+dy
                    if not (nx in range(h) and ny in range(w)):
                        continue
                    if grid[nx][ny] == "
                        continue
                    if dist[nx][ny] == -1:
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
            ans = max(ans, max([max([j for j in i]) for i in dist]))

print(ans)

Solution (Python):
h, w = map(int, input().split())
grid = [input() for _ in [0]*h]

ans = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == ".":
            q = [(i, j)]
            dist = [[-1]*w for _ in [0]*h]
            dist[i][j] = 0
            while q:
                x, y = q.pop(0)
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x+dx, y+dy
                    if not (nx in range(h) and ny in range(w)):
                        continue
                    if grid[nx][ny] == "
                        continue
                    if dist[nx][ny] == -1:
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
            ans = max(ans, max([max([j for j in i]) for i in dist]))

print(ans)

Solution (Python):
h, w = map(int, input().split())
lmap = [[0] * w for i in range(h)]
inf = 2**31-1
for i in range(h):
    s = input()
    for j in range(w):
        if s[j] == "
            lmap[i][j] = 1
        else:
            lmap[i][j] = 0


def bfs(i, j):
    que = []
    que.append([i, j])
    dmap = [[inf] * w for i in range(h)]
    dmap[i][j] = 0
    dmax = 0

    vec = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    while len(que) > 0:
        pt = que.pop(0)
        
        for v in vec:
            y = pt[0] + v[0]
            x = pt[1] + v[1]
            if x >= 0 and x < w and y >= 0 and y < h and lmap[y][x] == 0 and dmap[y][x] == inf:
                que.append([y, x])
                d = dmap[pt[0]][pt[1]] + 1
                dmax = max(dmax, d)
                dmap[y][x] = d

    
    return dmax


ans = 0
for i in range(h):
    for j in range(w):
        if lmap[i][j] == 0:
            r = bfs(i, j)
            
            ans = max(r, ans)

print(ans)

Solution (Python):
import collections

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


def bfs(i, j):
    global h, w, r
    f = [-1 for _ in range(h * w)]
    que = [[] for _ in range(h * w)]
    que[0].append([i, j])
    for k in range(h * w):
        if que[k]:
            res = k
            for i, j in que[k]:
                f[i * w + j] = k
                for sr in r:
                    ti = i + sr[0]
                    tj = j + sr[1]
                    if ti >= 0 and tj >= 0 and ti < h and tj < w:
                        if s[ti][tj] == ".":
                            if f[ti * w + tj] == -1:
                                que[k + 1].append([ti, tj])
    return res


fl = 0
for i in range(h):
    if "
        fl = 1
        break
if fl == 0:
    print(h + w - 2)
else:
    res = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == ".":
                res = max(res, bfs(i, j))
    print(res)

Solution (Python):
from collections import deque
import copy

def BFS(h,w,sy,sx,xy_list):
 dist=[[-1]*w for i in range(h)]
 dist[sy][sx]=0
 xy_list[sy][sx]='

 dq=deque()
 dq.append((sy,sx))

 while dq:
  y,x=dq.popleft()
  for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
   ny=y+dy
   nx=x+dx
   if 0<=ny<h and 0<=nx<w and xy_list[ny][nx]!='
    dq.append((ny,nx))
    xy_list[ny][nx]='
    dist[ny][nx]=dist[y][x]+1

 return dist

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

 ans=0
 for hh in range(h):
  for ww in range(w):
   if s[hh][ww]=='
    continue
   xy_list=copy.deepcopy(s)
   dist=BFS(h,w,hh,ww,xy_list)
   for d in dist:
    ans=max(ans,max(d))

 print(ans)

if __name__=="__main__":
  main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
INF = 10010001001
way = [[0, 1], [0, -1], [1, 0], [-1, 0]]

ans = 0
for sy in range(h):
    for sx in range(w):
        dist = [[INF] * w for _ in range(h)]
        dist[sy][sx] = 0
        if S[sy][sx] == '
            continue
        q = deque()
        q.append((sy, sx))
        while q:
            y, x = q.popleft()
            for dy, dx in way:
                ny, nx = y + dy, x + dx
                if 0 <= ny <= h - 1 and 0 <= nx <= w - 1 and S[ny][nx] == '.' and dist[ny][nx] == INF:
                    dist[ny][nx] = dist[y][x] + 1
                    ans = max(ans, dist[y][x] + 1)
                    q.append((ny, nx))
print(ans)