Problem:
 Score : 400 points    Problem Statement Takahashi has a maze, which is a grid of H \times W squares with H horizontal rows and W vertical columns.  The square at the i -th row from the top and the j -th column is a "wall" square if S_{ij} is # , and a "road" square if S_{ij} is . .  From a road square, you can move to a horizontally or vertically adjacent road square.  You cannot move out of the maze, move to a wall square, or move diagonally.  Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.  Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.  In this situation, find the maximum possible number of moves Aoki has to make.      Constraints  1 \leq H,W \leq 20  S_{ij} is . or # .  S contains at least two occurrences of . .  Any road square can be reached from any road square in zero or more moves.         Input Input is given from Standard Input in the following format:  H  W  S_{11} ... S_{1W}  :  S_{H1} ... S_{HW}       Output Print the maximum possible number of moves Aoki has to make.        Sample Input 1 3 3
...
...
...      Sample Output 1 4  If Takahashi chooses the top-left square as the starting square and the bottom-right square as the goal square, Aoki has to make four moves.       Sample Input 2 3 5
...#.
.#.#.
.#...      Sample Output 2 10  If Takahashi chooses the bottom-left square as the starting square and the top-right square as the goal square, Aoki has to make ten moves.

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def build_grid(H, W, intv, _type, space=True, padding=False):
    
    if space:
        _input = lambda: input().split()
    else:
        _input = lambda: input()
    _list = lambda: list(map(_type, _input()))
    
    if padding:
        offset = 1
    else:
        offset = 0
    grid = list2d(H+offset*2, W+offset*2, intv)
    for i in range(offset, H+offset):
        row = _list()
        for j in range(offset, W+offset):
            grid[i][j] = row[j-offset]
    return grid

def bfs(grid, src):
    """ BFS(グリッド、重みなし) """
    from collections import deque

    H, W = len(grid), len(grid[0])
    h, w = src
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))
    que = deque([(h, w, 0)])
    dist = list2d(H, W, -1)
    dist[h][w] = 0
    while que:
        h, w, c = que.popleft()
        for dh, dw in directions:
            h2 = h + dh
            w2 = w + dw
            if grid[h2][w2] == '
                continue
            if dist[h2][w2] != -1:
                continue
            dist[h2][w2] = c + 1
            que.append((h2, w2, c+1))
    return dist

H, W = MAP()
grid = build_grid(H, W, '

ans = 0
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j] != '
            
            res = bfs(grid, (i, j))
            for k in range(1, H+1):
                for l in range(1, W+1):
                    
                    ans = max(ans, res[k][l])
print(ans)

Solution (Python):
from collections import deque

U, D, L, R = (-1, 0), (+1, 0), (0, -1), (0, +1)

is_good = lambda x, y, R, C: True if x < R and x >= 0 and y < C and y >= 0 else False


def traverse(grid, start, distance_grid):
  d = deque([(start, 0)])
  tx, ty = start
  distance_grid[tx][ty] = 0
  
  dis = 0
  visited = set([start])
  while d:
    node, path = d.popleft()
    cx, cy = node
    for dx, dy in U, D, L, R:
      if is_good(cx + dx, cy + dy, len(grid), len(grid[0])) and grid[cx + dx][cy + dy] != '
        nx, ny = cx + dx, cy + dy
        visited.add((nx, ny))
        d.append([(nx, ny), path+1])
        distance_grid[nx][ny] = distance_grid[cx][cy]+1
  
  for arr in distance_grid:
    dis = max(dis, max(arr))
  return dis

from copy import deepcopy

def bfs():
  R, C = tuple(map(int, input().split()))
  grid =[list(input()) for _ in range(R)]
  temp = [[-1 for _ in range(C)] for _ in range(R)]
  
  answer = 0
  for row in range(R):
    for col in range(C):
      if grid[row][col] != '
        start = (row, col)
        distance_grid = deepcopy(temp)
        answer = max(answer, traverse(grid, start, distance_grid))
  return answer


print(bfs())

Solution (Python):
import copy
from collections import deque


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (-1, 0), (0, -1), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if (maze[next_h][next_w] == ".") and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])
    ret = 0
    for i in range(H):
        tmp = max(dist[i])
        if tmp > ret:
            ret = tmp
    return ret


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

    dist = [[-1 for _ in range(W)] for _ in range(H)]
    ans = 0
    for sh in range(H):
        for sw in range(W):
            if S[sh][sw] == "
                continue
            d = copy.deepcopy(dist)
            max_move = bfs(H, W, S, d, sh, sw)
            if max_move > ans:
                ans = max_move
    print(ans)

Solution (Python):
import copy
import sys
sys.setrecursionlimit(10**6)

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

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

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0) ,walker)
    else:
        return None


candicate = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
            far=0

            for gx in range(W):
                for gy in range(H):
                    if S[gy][gx]=='.':
                        if far < temp_walker[gy][gx]:
                            far = temp_walker[gy][gx]

            
            candicate.append(far)
print(max(candicate))

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

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

def search(n,m):
    ans = -1  
    
    X = [[0 for i in range(w)] for j in range(h)]  
    X[n][m] = 1
    que = [(n,m)]
    while que:
        new_que = []
        for x,y in que:
            for dx,dy in d:
                if 0<= x+dx < h and 0<= y+dy < w and meiro[x+dx][y+dy] == '.' and X[x+dx][y+dy] == 0:
                    X[x+dx][y+dy] = 1
                    new_que.append((x+dx , y+dy))
        ans += 1
        que = new_que
    return ans

for i in range(h):
    for j in range(w):
        if meiro[i][j] == '.':
            ans = max(ans , search(i,j))
            
print(ans)

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

def cal_dist(sx, sy):
    
    x_max, y_max = h, w
    dist = [[float('inf')] * w for _ in range(h)]

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

    
    dist_max = 0
    while len(que) > 0:
        x, y = que.popleft()

        dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
        for i in range(0, 4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < x_max and 0 <= ny < y_max and \
               s[nx][ny] != '
                que.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1
                dist_max = max(dist[nx][ny], dist_max)

    return dist_max

dist_max = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
            continue
        dist = cal_dist(i, j)
        if dist == float('inf'):
            continue
        dist_max = max(dist, dist_max)
print(dist_max)

Solution (Python):
H,W=map(int,input().split())
s=[]
for _ in range(H):
    s.append(list(input()))
def dfs(y,x):
    q=[(y,x)]
    visited=[[-1]*W for _ in range(H)]
    visited[y][x]=0
    while q:
        cy,cx=q.pop(0)
        for dy,dx in ((1,0),(-1,0),(0,-1),(0,1)):
            nx=cx+dx
            ny=cy+dy
            if 0<=ny<H and 0<=nx<W and s[ny][nx]=='.' and visited[ny][nx]==-1:
                visited[ny][nx]=visited[cy][cx]+1
                q.append((ny,nx))
    return max(max(i) for i  in visited)
ans=0
for h in range(H):
    for w in range(W):
        if s[h][w]=='.':
            ans=max(dfs(h,w),ans)
print(ans)

Solution (Python):
import numpy
H,W = map(int, input().split())
S = [list('
S.insert(0, list('
S.append(list('
vector = [(1,0), (-1,0), (0,1), (0,-1)]
ans = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]=='.':
            Q = [(i,j)]
            distance = [[0]*(W+2) for i in range(H+2)]
            distance[i][j] = 1
            while Q!=[]:
                x,y = Q.pop(0)
                for k in vector:
                    x1,y1 = x+k[0],y+k[1]
                    if S[x1][y1]=='.' and distance[x1][y1]==0:
                        Q.append((x1,y1))
                        distance[x1][y1] = distance[x][y] + 1
            ans = max(ans, numpy.max(distance))
print(ans-1)

Solution (Python):
import queue
H, W = map(int, input().split())
g = [list(input()) for _ in range(H)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def bfs(g, sh, sw):
    
    dist = [[-1] * W for _ in range(H)]
    que = queue.Queue()
    res = 0
    que.put((sh,sw))
    dist[sh][sw] = 0
    while not que.empty():
        sh, sw = que.get()
        res = max(res, dist[sh][sw])
        for i in range(4):
            nh = sh + dx[i]
            nw = sw + dy[i]
            if nh < 0 or nw < 0 or nh >= H or nw >= W:
                continue
            if g[nh][nw] == '
                continue
            if dist[nh][nw] == -1:
                dist[nh][nw] = dist[sh][sw] + 1
                que.put((nh, nw))
    return res

ans = 0
for sh in range(H):
    for sw in range(W):
        if g[sh][sw] == '
            continue
        ans = max(ans, bfs(g, sh, sw))
print(ans)

Solution (Python):
from collections import deque
inf=10**6
dx=[-1,0,1,0]
dy=[0,1,0,-1]
h,w=map(int,input().split())
maze=[list(input()) for _ in range(h)]
def bfs(sx,sy):
    dist=[[inf for _ in range(w)] for _ in range(h)]
    dist[sx][sy]=0
    d=deque()
    d.append([sx,sy])
    while d:
        x,y=d.popleft()
        for i in range(4):
            nx=x+dx[i]
            ny=y+dy[i]
            if nx<0 or nx>=h or ny<0 or ny>=w or maze[nx][ny]=='
                continue
            d.append([nx,ny])
            dist[nx][ny]=dist[x][y]+1
    val=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]!=inf:
                val=max(val,dist[i][j])
    return val
ans=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            ans=max(ans,bfs(i,j))
print(ans)

Solution (Python):
from collections import defaultdict
from queue import Queue
H, W = map(int, input().split())
m = [input() for i in range(H)]
G = defaultdict(list)
l = []
for i in range(H):
    for j in range(W):
        v = i*W + j+1
        if m[i][j] != '.':
            continue
        l.append(v)
        if i + 1 < H and m[i+1][j] == '.':
            G[v].append((i+1)*W + j+1)
        if 0 <= i - 1 and m[i-1][j] == '.':
            G[v].append((i-1)*W + j+1)
        if j + 1 < W and m[i][j+1] == '.':
            G[v].append(i*W + j+2)
        if 0 <= j - 1 and m[i][j-1] == '.':
            G[v].append(i*W + j)

def bfs(v):
    visited = defaultdict(bool)
    q = Queue()
    visited[v] = 1
    dist = [-1] * (H*W)
    dist[v-1] = 0
    q.put(v)
    while not q.empty():
        v = q.get()
        for c in G[v]:
            if not c in visited:
                visited[c] = 1
                dist[c-1] = dist[v-1] + 1
                q.put(c)
    return dist

ans = 0
for v in l:
    ans = max(ans, max(bfs(v)))
print(ans)

Solution (Python):

from collections import defaultdict
H, W = map(int, input().split())
M = []
for i in range(H):
    M.append(list(input()))


def getMaxDistantPoint(Sx, Sy):
    BIG = 10**16

    def bigcost():
        return BIG
    costs = defaultdict(bigcost)
    costs[(Sx, Sy)] = 0
    current = [(Sx, Sy)]
    visited = set()
    while len(current) > 0:
        next = []
        for v in current:
            c = costs[v]
            if v[0] > 0 and M[v[1]][v[0]-1] == ".":
                coord = (v[0]-1, v[1])
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
            if v[0] < W-1 and M[v[1]][v[0]+1] == ".":
                coord = (v[0]+1, v[1])
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
            if v[1] < H-1 and M[v[1]+1][v[0]] == ".":
                coord = (v[0], v[1]+1)
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
            if v[1] > 0 and M[v[1]-1][v[0]] == ".":
                coord = (v[0], v[1]-1)
                if coord not in visited:
                    visited.add(coord)
                    next.append(coord)
                    costs[coord] = min(c+1, costs[coord])
        current = next
    maxCost = 0
    maxCoord = None
    for c in costs:
        if costs[c] != BIG:
            if costs[c] > maxCost:
                maxCoord = c
                maxCost = costs[c]
    return (maxCoord, maxCost)


result = 0
for Sx in range(W):
    for Sy in range(H):
        if M[Sy][Sx] == '.':
            result = max(result, getMaxDistantPoint(Sx, Sy)[1])
print(result)

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

inf=100000000
ma=[]
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            x=[[inf for i_sub in range(w)] for j_sub in range(h)]
            
            q=queue.Queue()
            d=0
            
            q.put([i,j])
            x[i][j]=0
            
            while q.qsize()!=0:
                
                d+=1
                l=q.qsize()
                
                for t in range(l):
                    I,J=q.get()
                    
                    
                    if I-1>=0 and s[I-1][J]=="." and x[I-1][J]==inf:
                        q.put([I-1,J])
                        
                        x[I-1][J]=d
                    if I+1<=h-1 and s[I+1][J]=="." and x[I+1][J]==inf:
                        q.put([I+1,J])
                        x[I+1][J]=d
                    if J-1>=0 and s[I][J-1]=="." and x[I][J-1]==inf:
                        q.put([I,J-1])
                        x[I][J-1]=d
                    if J+1<=w-1 and s[I][J+1]=="." and x[I][J+1]==inf:
                        q.put([I,J+1])
                        x[I][J+1]=d
            ma_sub=0
            for k in range(h):
                for l in range(w):
                    if x[k][l]!=inf:
                        ma_sub=max(ma_sub,x[k][l])
            ma.append(ma_sub)

print(max(ma))

Solution (Python):
def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    from collections import defaultdict
    cnt = defaultdict(int)
    for item in s:
        for c in item:
            cnt[c] += 1
    if '
        print(H+W-2)
        quit()

    def bfs(row, col, R, C, s):
        from collections import deque
        q = deque()
        q.append([(row, col), 0])
        seen = set()
        ans = 0
        while q:
            (r, c), dist = q.popleft()
            ans = max(dist, ans)
            seen.add((r, c))
            for (next_r, next_c) in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if (next_r, next_c) not in seen and \
                    0 <= next_r < R and 0 <= next_c < C and \
                   s[next_r][next_c] == '.':
                    q.append([(next_r, next_c), dist + 1])
        return ans

    max_v = 0
    for h in range(H):
        for w in range(W):
            if s[h][w] == '.':
                max_v = max(max_v, bfs(h, w, H, W, s))
    print(max_v)
resolve()

Solution (Python):
import collections
H,W = map(int,input().split())
if H == W == 1:
    print(0)
    exit()
if (H == 1 and W == 2) or (H == 2 and W == 1):
    print(1)
    exit()
LL=[]
for i in range(H):
    LL.append(input())

L = ((1,0),(0,1),(-1,0),(0,-1))
q = collections.deque()
max_L = []
for i in range(H):
    for j in range(W):
        d = [[0]*W for i in range(H)]
        if LL[i][j] ==".":
            q.append((i,j))
            d[i][j] = 0
            max1 = 0
            while q:
                x,y = q.popleft()
                for dx,dy in L:
                    if 0>x+dx or x+dx>H-1 or 0>y+dy or y+dy>W-1 or d[x+dx][y+dy] !=0:
                        continue
                    if  LL[x+dx][y+dy] == ".":
                        d[x+dx][y+dy] = d[x][y] +1
                        q.append((x+dx,y+dy))
                        max1 = max(max1,d[x+dx][y+dy])
                        max_L.append(max1)
                        
print(max(max_L))

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

def bfs(startx,starty):
    d = [[-1]*w for i in range(h)]
    q = deque([[startx,starty]])
    d[startx][starty] = 0
    cnt = 0
    while(q):
        x,y = q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x,new_y = x+i,y+j
            if (new_x>h-1) or (new_x<0) or (new_y>w-1) or (new_y<0):
                continue
        
            elif s[new_x][new_y] == '
                continue
        
            elif d[new_x][new_y] == -1:
                d[new_x][new_y] = d[x][y]+1
                q.append([new_x,new_y])
                cnt = max(cnt,d[new_x][new_y])
    
    return cnt

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            ans = max(ans,bfs(i,j))

print(ans)

Solution (Python):
import queue
H, W = list(map(int, input().split()))
M = [[i for i in input()] for j in range(H)]

def bfs(x, y):
  D = [[10 ** 9 for i in range(W)] for j in range(H)]
  q = queue.Queue()
  q.put([x, y])
  D[y][x] = 0
  direct = [[-1, 0], [1, 0], [0, -1], [0, 1]]
  max_distance = 0
  while q.qsize() != 0:
    x, y = q.get()
    for dx, dy in direct:
      nx, ny = x + dx, y + dy
      if nx < 0 or nx >= W or ny < 0 or ny >= H:
        continue
      if M[ny][nx] == "
        continue
      if D[ny][nx] > D[y][x] + 1:
        D[ny][nx] = D[y][x] + 1
        max_distance = max([max_distance, D[ny][nx]])
        q.put([nx, ny])
  return max_distance

result = 0
for y in range(H):
  for x in range(W):
    if M[y][x] == "
      continue
    result = max([result, bfs(x, y)])
print(result)

Solution (Python):
def grid2graph(grid):
    
    H, W = len(grid), len(grid[0])
    f = {}
    cnt = 0
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '.':
                f[(h, w)] = cnt
                cnt += 1
    G = [[] for i in range(cnt)]
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '
                continue
            i = f[(h, w)]
            if 0 <= h-1 and grid[h-1][w] == '.':
                j = f[(h-1, w)]
                G[i].append(j)
            if 0 <= w-1 and grid[h][w-1] == '.':
                j = f[(h, w-1)]
                G[i].append(j)
            if h+1 < H and grid[h+1][w] == '.':
                j = f[(h+1, w)]
                G[i].append(j)
            if w+1 < W and grid[h][w+1] == '.':
                j = f[(h, w+1)]
                G[i].append(j)
    return G


def warshall_floyd(G):
    inf = 10**18
    n = len(G)
    d = [[inf for i in range(n)] for j in range(n)]
    for i in range(n):
        d[i][i] = 0
        for j in G[i]:
            d[i][j] = 1
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


H, W = map(int, input().split())
S = []
for h in range(H):
    S.append(list(input()))
G = grid2graph(S)
d = warshall_floyd(G)
n = len(d)
ans = 0
for i in range(n-1):
    for j in range(n):
        ans = max(ans, d[i][j])
print(ans)

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

def bfs(startx,starty):
    d = [[-1]*W for _ in range(H)]
    q = deque([[startx,starty]])
    d[startx][starty] = 0
    cnt = 0
    while(q):
        x,y = q.popleft()
        for i,j in ([1,0],[-1,0],[0,1],[0,-1]):
            new_x,new_y = x+i,y+j
            if(new_x>H-1 or new_x<0 or new_y>W-1 or new_y<0):
                continue
            elif(S[new_x][new_y] == "
                continue
            elif(d[new_x][new_y] == -1):
                d[new_x][new_y] = d[x][y] + 1
                q.append([new_x,new_y])
                cnt = max(cnt,d[new_x][new_y])
    return cnt

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

Solution (Python):
import queue
H,W=map(int,input().split())
field=[list(input()) for _ in range(H)]

def meiro(s):
    que=queue.Queue()
    dist=[[-1 for _ in range(W)] for _ in range(H)]
    dist[s[0]][s[1]]=0
    que.put(s)
    mv=((1,0),(-1,0),(0,1),(0,-1))
    max=0
    while not que.empty():
        h,w=que.get()
        for y,x in mv:
            nh=h+y
            nw=w+x
            if nh<0 or nh>=H or nw<0 or nw>=W:
                continue
            elif field[nh][nw]=="
                continue
            elif dist[nh][nw]!=-1:
                continue
            else:
                dist[nh][nw]=dist[h][w]+1
                que.put((nh,nw))
                if max<dist[nh][nw]:
                    max=dist[nh][nw]

    return max

ans=0
for i in range(H):
    for k in range(W):
        if field[i][k]=="
            continue
        tmp=meiro((i,k))
        if tmp>ans:
            ans=tmp
print(ans)

Solution (Python):
H,W=map(int,input().split())
s=[list(input()) for _ in range(H)]
d=[(1,0),(0,1),(-1,0),(0,-1)]
ans=0
def search(n,m):
    X=[[0]*W for _ in range(H)]
    X[n][m]=1
    ans=-1
    que=[]
    que.append((n,m))
    while que:
        newque=[]
        for x,y in que:
            for dx,dy in d:
                if 0<=x+dx<H and 0<=y+dy<W and s[x+dx][y+dy]=="." and X[x+dx][y+dy]==0:
                    X[x+dx][y+dy]=1
                    newque.append((x+dx,y+dy))
        ans+=1
        que=newque
    return ans
        
for i in range(H):
    for j in range(W):
        if s[i][j]==".":
            ans=max(ans,search(i,j))
                
print(ans)

Solution (Python):
H,W=map(int, input().split())
maze=[]
maze.append(list("
for h in range(H):
    maze.append(list("
maze.append(list("

from collections import deque
import itertools
import copy

def chk_bfd(sy,sx):
    m_max=0
    ma=copy.deepcopy(maze)
    ma[sy][sx]=0
    d=[(1,0),(-1,0),(0,1),(0,-1)]
    q=deque([[sy,sx]])
    while q:
        y,x=q.popleft()
        for dy,dx in d:
            if ma[y+dy][x+dx]=='.':
                q.append([y+dy,x+dx])
                ma[y+dy][x+dx]=ma[y][x]+1
                m_max=max(m_max,ma[y+dy][x+dx])
    return m_max

s=[]
for h in range(H+2):
    for w in range(W+2):
        if maze[h][w]=='.':
            s.append([h,w])

res=0
for sy,sx in s:
    res=max(res,chk_bfd(sy,sx))

print(res)

Solution (Python):
from collections import deque
h,w = map(int,input().split())
s =["
opt = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == ".":
            temp = [[0]*(w+2) for i in range(h+2)]
            temp[i][j] = 1
            dq = deque([(i,j)])
            
            while dq:
                x,y = dq.popleft()
                for k in opt:
                    x1,y1 = x+k[0],y+k[1]
                    if s[x1][y1] == "." and temp[x1][y1] == 0:
                        temp[x1][y1] = temp[x][y] + 1
                        dq.append((x1,y1))
                        ans=max(ans,temp[x1][y1])
print(ans-1)

Solution (Python):
import numpy as np
from collections import deque
h,w = map(int,input().split())
s =["
s = np.array(s)
opt = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == ".":
            temp = [[0]*(w+2) for i in range(h+2)]
            temp[i][j] = 1
            dq = deque([(i,j)])
            
            while dq:
                x,y = dq.popleft()
                for k in opt:
                    x1,y1 = x+k[0],y+k[1]
                    if s[x1][y1] == "." and temp[x1][y1] == 0:
                        temp[x1][y1] = temp[x][y] + 1
                        dq.append((x1,y1))
            ans = max(ans,np.max(temp))
print(ans-1)

Solution (Python):
import numpy as np
from collections import deque
h,w = map(int,input().split())
s =["
s = np.array(s)
opt = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0

for i in range(h+2):
    for j in range(w+2):
        if s[i][j] == ".":
            temp = [[0]*(w+2) for i in range(h+2)]
            temp[i][j] = 1
            dq = deque([(i,j)])
            
            while dq:
                x,y = dq.popleft()
                for k in opt:
                    x1,y1 = x+k[0],y+k[1]
                    if s[x1][y1] == "." and temp[x1][y1] == 0:
                        temp[x1][y1] = temp[x][y] + 1
                        dq.append((x1,y1))
            ans = max(ans,np.max(temp))
print(ans-1)

Solution (Python):
import numpy as np
from collections import deque
h,w = map(int,input().split())
s =["
s = np.array(s)
opt = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0

for i in range(h+2):
    for j in range(w+2):
        temp = [[0]*(w+2) for i in range(h+2)]
        temp[i][j] = 1
        dq = deque([(i,j)])
        
        while dq:
            x,y = dq.popleft()
            if s[x][y] == ".":
                for k in opt:
                    x1,y1 = x+k[0],y+k[1]
                    if s[x1][y1] == ".":
                        if temp[x1][y1] == 0:
                            temp[x1][y1] = temp[x][y] + 1
                            dq.append((x1,y1))
                        elif temp[x1][y1] > temp[x][y] + 1:
                            temp[x1][y1] = temp[x][y] + 1
                            dq.append((x1,y1))
        ans = max(ans,np.max(temp))
print(ans-1)

Solution (Python):
from collections import deque

INF = 10 ** 6
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
maze = [list(input()) for _ in range(H)]
def bfs(sx, sy):
    reached = [[INF for _ in range(W)] for _ in range(H)]
    reached[sx][sy] = 0
    d = deque()
    d.append([sx, sy])
    while d:
        x, y = d.popleft()
        for i in range(4):    
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > H - 1 or ny < 0 or ny > W - 1 or maze[nx][ny] == "
                continue
            d.append([nx, ny])
            reached[nx][ny] = reached[x][y] + 1
    gl = 0
    for i in range(H):
        for j in range(W):
            if reached[i][j] != INF:
                gl = max(gl, reached[i][j])
    return gl

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

Solution (Python):
import sys

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

mxm = 0
mmm = 0
mxcx = -1
mxcy = -1

for i in range(h):
    for j in range(w):
      
        
        
        
      if(s[i][j] == '.'):
        do.append([i,j])
        ex = [[0]*w for i in range(h)]
        ex[i][j] = 1
      else:
        continue
        
      while(len(do)!=0):
        x,y = do.pop(0)
        
        for k,l in [[1,0],[-1,0],[0,1],[0,-1]]:
          a = x+k
          b = y+l
          
          if(-1 < a < h and -1 < b < w):
            if(s[a][b] == '.' and ex[a][b] == 0):
              hantei = ex[x][y] + 1
              ex[a][b] = hantei
              o = a
              p = b
              do.append([a,b])
              
      
      
      
      
          
      
      
      
      
                
        
      if(mxm < hantei - 1):
        
        mxm = hantei - 1
        mxcx = o
        mxcy = p
print(mxm)

Solution (Python):
import sys
from collections import deque

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

def bfs(sy,sx):
    queue = deque([[sy,sx]])
    log = [[0 for i in range(W)] for j in range(H)]
    while queue:
        p = queue.popleft()

        for i,j in [1,0],[-1,0],[0,1],[0,-1]:
            next_p = [p[0]+i,p[1]+j]
            
            if 0 <= next_p[0] < H and 0 <= next_p[1] < W:
                if next_p[0] == sy and next_p[1] == sx:
                    continue

                if maze[next_p[0]][next_p[1]] == '.'\
                    and log[next_p[0]][next_p[1]] == 0:
                    log[next_p[0]][next_p[1]] = log[p[0]][p[1]] + 1
                    queue.append([next_p[0],next_p[1]])
    
    return log

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            tmp_i = i
            tmp_j = j
            break

tmplog = bfs(tmp_i,tmp_j)
max_v = 0

for i in range(H):
    for j in range(W):
        if tmplog[i][j] > max_v:
            max_v = tmplog[i][j]
            tmp_i = i
            tmp_j = j

tmplog = bfs(tmp_i,tmp_j)
max_v = 0

for i in range(H):
    for j in range(W):
        if tmplog[i][j] > max_v:
            max_v = tmplog[i][j]
            s_y = i
            s_x = j

finlog = bfs(s_y,s_x)

for i in range(H):
    for j in range(W):
        if finlog[i][j] > max_v:
            max_v = finlog[i][j]

print(max_v)