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
H, W = map(int, input().split())
dif = [(-1, 0), (1, 0), (0, 1), (0, -1)]
Map = [list(input()) for i in range(H)]
visited = [[False for i in range(W)] for j in range(H)]
deq = deque()


def bfs(node):
    nx, ny = node
    deq.append(node)

    visited[nx][ny] = True
    distance = [[float("inf") for i in range(W)] for j in range(H)]
    distance[nx][ny] = 0
    while deq:
        x, y = deq.popleft()
        for dx, dy in dif:
            if 0 <= x+dx < H and 0 <= y+dy < W and Map[x+dx][y+dy] == "." and visited[x+dx][y+dy] == False:
                visited[x+dx][y+dy] = True
                distance[x+dx][y+dy] = distance[x][y]+1
                deq.append((x+dx, y+dy))
    return distance


def s_bfs(node):
    nx, ny = node
    deq.append(node)
    Visited = [[False for i in range(W)] for j in range(H)]
    Visited[nx][ny] = True
    distance = [[float("inf") for i in range(W)] for j in range(H)]
    distance[nx][ny] = 0
    while deq:
        x, y = deq.popleft()
        for dx, dy in dif:
            if 0 <= x+dx < H and 0 <= y+dy < W and Map[x+dx][y+dy] == "." and Visited[x+dx][y+dy] == False:
                Visited[x+dx][y+dy] = True
                distance[x+dx][y+dy] = distance[x][y]+1
                deq.append((x+dx, y+dy))
    return distance


ans = 1
roads = deque()
for i in range(H):
    for j in range(W):
        if Map[i][j] == ".":
            roads.append((i, j))

while roads:
    x, y = roads.popleft()
    if visited[x][y] == False:
        B = s_bfs((x, y))
        s = -1
        choice=[]
        most_far_distance = 0
        for i in range(H):
            for j in range(W):
                if B[i][j] != float("inf") and B[i][j] > most_far_distance:
                    most_far_distance = B[i][j]
        for i in range(H):
            for j in range(W):
                if B[i][j] == most_far_distance:
                    choice.append((i, j))

        for s in choice:
            C = s_bfs(s)
            for i in range(H):
                for j in range(W):
                    if C[i][j] != float("inf"):
                        ans = max(ans, C[i][j])
print(ans)

Solution (Python):
from collections import deque
def MI(): return map(int, input().split())

def bfs(field,s):
  MOVE=[(0,1),(1,0),(0,-1),(-1,0)]
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if dist[ni][nj]!=-1:
        continue
      if field[ni][nj]=='
        continue
      q.append((d+1,(ni,nj)))
  return d
ans=0
H,W=MI()
field=[input() for _ in range(H)]
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Solution (Python):
from collections import deque
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def bfs(field,s):
  MOVE=[(0,1),(1,0),(0,-1),(-1,0)]
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if dist[ni][nj]!=-1:
        continue
      if field[ni][nj]=='
        continue
      q.append((d+1,(ni,nj)))
  return d
ans=0
H,W=MI()
field=[input() for _ in range(H)]
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Solution (Python):
from collections import deque
def II(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def bfs(field,s):
  MOVE=[(0,1),(1,0),(0,-1),(-1,0)]
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if dist[ni][nj]!=-1:
        continue
      if field[ni][nj]=='
        continue
      q.append((d+1,(ni,nj)))
  return d
ans=0
H,W=MI()
field=[input() for _ in range(H)]
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Solution (Python):
from collections import deque

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


def solve_maze(s):
    bias = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    inf = 10 ** 9

    d = [[inf] * W for _ in range(H)]
    d[s[0]][s[1]] = 0

    q = deque()
    q.append(s)
    while q:
        u, v = q.popleft()
        for i, j in bias:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and d[u + i][v + j] > d[u][v] + 1):
                d[u + i][v + j] = d[u][v] + 1
                q.append((u + i, v + j))

    res = 0
    for i in range(H):
        for j in range(W):
            if d[i][j] < inf:
                res = max(res, d[i][j])
                
    return res


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

print(ans)

Solution (Python):
import sys
import itertools
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)
 
H,W = map(int,readline().split())
grid = ''
grid += '
for _ in range(H):
    grid += '
grid += '
L = len(grid)
INF = float('inf')

def bfs(start):
    dist = [-INF] * L
    q = [start]
    dist[start] = 0
    while q:
        qq = []
        for x,dx in itertools.product(q,[1,-1,W+2,-W-2]):
            y = x+dx
            if dist[y] != -INF or grid[y] == '
                continue
            dist[y] = dist[x] + 1
            qq.append(y)
        q = qq
    return max(dist) 

ans = 0
for i in range(L):
    if grid[i] == '.':
        start = i
        max_dist = bfs(start)
        ans = max(ans,max_dist)
print(ans)

Solution (Python):
from collections import deque

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

v = {(1,0), (-1,0), (0,1), (0,-1)}
q = deque()
ans = 0

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
                    
            
            dist = [[-1 for _ in range(W)] for _ in range(H)]
            dist[i][j] = 0
            q.append([j, i])
            while len(q) > 0:
                now = q.popleft()
                x, y = now[0], now[1]
                d = dist[y][x]
                for dx, dy in v:
                    nx, ny = x+dx, y+dy
                    if 0<=nx<W and 0<=ny<H and dist[ny][nx]==-1 and maze[ny][nx]=='.':
                        dist[ny][nx] = d+1
                        q.append([nx, ny])
            
            ans = max(ans, d)
print(ans)

Solution (Python):
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Solution (Python):
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  dist=[[-1]*W for _ in range(H)]
  d,i,j=-1,-1,-1
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni,nj=i+di,j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Solution (Python):
def MI(): return map(int, input().split())
from collections import deque
def bfs(field,s):
  q=deque([(0,s)])
  MOVE=[(-1,0),(0,-1),(1,0),(0,1)]
  dist=[[-1]*W for i in range(H)]
  d,i,j=-1,-1,-1  
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni=i+di
      nj=j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))
      ans=max(ans,d)
print(ans)

Solution (Python):
from collections import deque
def MI(): return map(int, input().split())
def bfs(field,s):
  q=deque([(0,s)])
  MOVE=[(-1,0),(0,-1),(0,1),(1,0)]
  d,i,j=-1,-1,-1
  dist=[[-1]*W for i in range(H)]  
  while q:
    d,(i,j)=q.popleft()
    if dist[i][j]!=-1:
      continue
    dist[i][j]=d
    for di,dj in MOVE:
      ni=i+di
      nj=j+dj
      if not 0<=ni<H or not 0<=nj<W:
        continue
      if field[ni][nj]=='
        continue
      if dist[ni][nj]!=-1:
        continue
      q.append((d+1,(ni,nj)))
  return d,i,j
H,W=MI()
field=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if field[i][j]=='.':
      d,i,j=bfs(field,(i,j))      
      ans=max(ans,d)
print(ans)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


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

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
        dis = [[-1 for k in range(w)] for k in range(h)]
        dis[i][j] = 0
        d = deque()
        d.append([i, j])
        while len(d):
            now = d.popleft()
            y = now[0]
            x = now[1]
            for k in range(4):
                ny = y + dy_dx[k][0]
                nx = x + dy_dx[k][1]
                if 0 <= ny < h and 0 <= nx < w:
                    if s[ny][nx] != '
                        dis[ny][nx] = dis[y][x] + 1
                        ans = max([ans, dis[ny][nx]])
                        d.append([ny, nx])

print(ans)

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


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

dy_dx = [[1,0],[0,1],[-1,0],[0,-1]]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
        dis = [[-1 for k in range(w)] for k in range(h)]
        dis[i][j] = 0
        d = deque()
        d.append([i, j])
        while len(d):
            now = d.popleft()
            y = now[0]
            x = now[1]
            for k in range(4):
                ny = y + dy_dx[k][0]
                nx = x + dy_dx[k][1]
                if 0 <= ny < h and 0 <= nx < w:
                    if s[ny][nx] != '
                        dis[ny][nx] = dis[y][x] + 1
                        ans = max([ans, dis[ny][nx]])
                        d.append([ny, nx])

print(ans)

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

sy=0
sx=0
for i in range(H):
    for j in range(W):
        c=0
        route=deque([(i,j,0)])
        S=copy.deepcopy(S1)
        while route:
            a,b,n=route.popleft()
            c=n
            if 0<=a<=H-1 and 0<=b<=W-1:
                if S[a][b]=='.':
                    S[a][b]='
                    route.append((a+1,b,n+1))
                    route.append((a-1,b,n+1))
                    route.append((a,b+1,n+1))
                    route.append((a,b-1,n+1))
                    
        ans.append(c-1)

print(max(ans))

Solution (Python):
from itertools import product

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


def neighbors(ih, iw):
    for ih1, iw1 in (
        (ih - 1, iw),
        (ih + 1, iw),
        (ih, iw - 1),
        (ih, iw + 1),
    ):
        if 0 <= ih1 < h and 0 <= iw1 < w and maze[ih1][iw1] == '.':
            yield (ih1, iw1)



def len_maze(ih, iw):
    
    if maze[ih][iw] == '
        return 0

    stepped = [[False] * w for _ in range(h)]
    q0 = [(ih, iw)]
    l = -1
    while q0:
        q1 = set()
        for ih0, iw0 in q0:
            stepped[ih0][iw0] = True
            for ih1, iw1 in neighbors(ih0, iw0):
                if not stepped[ih1][iw1]:
                    q1.add((ih1, iw1))
        q0 = list(q1)
        l += 1

    return l


answer = max(len_maze(ih, iw) for ih, iw in product(range(h), range(w)))
print(answer)

Solution (Python):
import queue

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


def bfs(dist, i, j):
    q = queue.Queue()
    q.put((i, j, 0))
    while not q.empty():
        i, j, c = q.get()
        
        if i != 0 and dist[i-1][j] == 0:
            dist[i-1][j] = c+1
            q.put((i-1, j, c+1))
        if j != 0 and dist[i][j-1] == 0:
            dist[i][j-1] = c+1
            q.put((i, j-1, c+1))
        if i != h-1 and dist[i+1][j] == 0:
            dist[i+1][j] = c+1
            q.put((i+1, j, c+1))
        if j != w-1 and dist[i][j+1] == 0:
            dist[i][j+1] = c+1
            q.put((i, j+1, c+1))
    return dist, c

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] == '.':
            dist = [[(maze[y][x] == '
            dist[i][j] = -10
            dist, c = bfs(dist, i, j)
            tmp_ans = c
            if tmp_ans > ans:
                ans = tmp_ans

print(ans)

Solution (Python):
from collections import deque
m = [[1, 0], [-1, 0], [0, 1], [0, -1]]
h, w = map(int, input().split())
l = []
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):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    H, W = map(int, readline().split())
    S = [[0] * W for _ in range(H)]
    for i in range(H):
        S[i] = readline().strip()

    dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '
                continue
            dist = [[-1] * W for _ in range(H)]
            dist[i][j] = 0
            queue = deque([(i, j)])
            res = 0
            while queue:
                x, y = queue.popleft()
                for dx, dy in dxdy4:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.' and dist[nx][ny] == -1:
                        dist[nx][ny] = dist[x][y] + 1
                        if res < dist[nx][ny]:
                            res = dist[nx][ny]
                        queue.append((nx, ny))
            if ans < res:
                ans = res

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

def main():
  h, w = map(int, input().split())
  area = [[s for s in sys.stdin.readline().strip()] for _ in range(h)]
  start_point = {0:set(), 1:set(), 2:set(), 3:set(), 4:set()}
  min_neighbor = 4
  for i in range(h):
    for j in range(w):
      if area[i][j] == '
        continue
      roads = 0
      if i > 0 and area[i - 1][j] == '.':
        roads += 1
      if i < h - 1 and area[i + 1][j] == '.':
        roads += 1
      if j > 0 and area[i][j - 1] == '.':
        roads += 1
      if j < w - 1 and area[i][j + 1] == '.':
        roads += 1
      min_neighbor = min(min_neighbor, roads)
      start_point[roads].add((i, j))
  max_cost = 0
  for start in start_point[min_neighbor]:
    queue = deque()
    queue.append(start)
    cost = 0
    visited = set()
    while len(queue) > 0:
      roads = len(queue)
      found = False
      for i in range(roads):
        s = queue.popleft()
        if s in visited:
          continue
        found = True
        visited.add(s)
        i = s[0]
        j = s[1]
        if i > 0 and area[i - 1][j] == '.':
          queue.append((i - 1, j))
        if i < h - 1 and area[i + 1][j] == '.':
          queue.append((i + 1, j))
        if j > 0 and area[i][j - 1] == '.':
          queue.append((i, j - 1))
        if j < w - 1 and area[i][j + 1] == '.':
          queue.append((i, j + 1))
      if not found:
        cost -= 1
      max_cost = max(cost, max_cost)
      if found:
        cost += 1
  print(max_cost)

if __name__ == '__main__':
  main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

OK = "."
NG = "

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
    for j,c in enumerate(s):
        u = i*cols+j
        if i>0:
            if c==OK and ss[i-1][j]==OK:
                v = u - cols
                ns[u].add(v)
                ns[v].add(u)
        if j>0:
            if c==OK and s[j-1]==OK:
                v = u - 1
                ns[u].add(v)
                ns[v].add(u)
                    
n = rows * cols

def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    while q:
        u = q.pop()
        d = seen[u]
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
    return seen
ans = -1
for i in range(rows):
    for j in range(cols):
        if ss[i][j] == "
            continue
        u = i*cols+j
        dist = bfs(u)
        ans = max(ans, max(num for num in dist if num is not None))
print(ans)

Solution (Python):



from fractions import gcd
from itertools import combinations,permutations,accumulate 

from collections import deque,defaultdict,Counter
import decimal
import re











import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
dx = [-1,0,1,0]
dy = [0,-1,0,1]
h,w = readInts()
S = [list(input()) for _ in range(h)]
def bfs(y,x):
    dq = deque()
    dq.append((y,x))
    res = -1
    dist = [[-1] * w for _ in range(h)]
    dist[y][x] = 0
    while dq:
        y,x = dq.popleft()
        res = max(res,dist[y][x])
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if not(0 <= ny < h and 0 <= nx < w):
                continue
            if S[ny][nx] == '
                continue
            dist[ny][nx] = dist[y][x] + 1
            dq.append((ny,nx))
    return res
ans = -1
for y in range(h):
    for x in range(w):
        if S[y][x] != '
            ans = max(ans,bfs(y,x))
print(ans)

Solution (Python):
import copy
from collections import deque

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

maze_o = [0]*h
for i in range(h):
    maze_o[i] = list(input())

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

ans = 0
for y in range(h):
    for x in range(w):
        if maze_o[y][x] == "
            continue
        maze = copy.deepcopy(maze_o)
        distance = deque([0])
        rireki = deque([])
        stack = deque([(y, x)])
        maze[y][x] = "
        while stack:
            yy, xx = stack.popleft()
            d = distance.popleft()
            rireki.append(d)
            for dxi,dyi in zip(dx, dy):
                if not (0<=dxi+xx<w and 0<=dyi+yy<h):
                    continue
                if maze[dyi+yy][dxi+xx] == "
                    continue
                distance.append(d+1)
                stack.append((dyi+yy,dxi+xx))
                maze[dyi+yy][dxi+xx] = "
        ans = max(ans, max(rireki))
print(ans)

Solution (Python):
from collections import deque
import numpy as np

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

ini = -1
q = deque()

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
ans = 0

for y in range(H):
    for x in range(W):
        dist = [[ini for _ in range(W)] for _ in range(H)]
        if grid[y][x] == "
        dist[y][x] = 0
        q.append((y, x))

        while(len(q) > 0):
            oy, ox = q.popleft()
            for di in range(4):
                ny = oy + dy[di]
                nx = ox + dx[di]

                if (ny < 0 or ny >= H or nx < 0 or nx >= W): continue
                if grid[ny][nx] == "
                if dist[ny][nx] != ini: continue

                dist[ny][nx] = dist[oy][ox] + 1
                q.append((ny, nx))

        ans = max(np.max(dist), ans)

print(ans)

Solution (Python):
from collections import deque

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

ini = -1
q = deque()

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)
ans = 0

for y in range(H):
    for x in range(W):
        dist = [[ini for _ in range(W)] for _ in range(H)]
        if grid[y][x] == "
        dist[y][x] = 0
        q.append((y, x))

        while(len(q) > 0):
            oy, ox = q.popleft()
            for di in range(4):
                ny = oy + dy[di]
                nx = ox + dx[di]

                if (ny < 0 or ny >= H or nx < 0 or nx >= W): continue
                if grid[ny][nx] == "
                if dist[ny][nx] != ini: continue

                dist[ny][nx] = dist[oy][ox] + 1
                q.append((ny, nx))

        ans = max(max(map(max, dist)), ans)

print(ans)

Solution (Python):
from collections import deque 
from copy import deepcopy

import sys
input = sys.stdin.readline
H,W = (int(i) for i in input().split())
map_initial =[["
for h in range(1,H+1):
    map_initial[h] =["

def BSF(x,y):
    dist =0
    map =deepcopy(map_initial)
    if map[x][y] =="
        return dist 
    dq =set()
    dq.add((x,y))
    dq_sarch =set()
    while len(dq) >0:
        h,w =dq.pop()
        map[h][w] ="
        if map[h+1][w]==".":
            dq_sarch.add((h+1,w))
        if map[h-1][w]==".":
            dq_sarch.add((h-1,w))
        if map[h][w+1]==".":
            dq_sarch.add((h,w+1))
        if map[h][w-1]==".":
            dq_sarch.add((h,w-1))
        if len(dq)==0:
            dq =deepcopy(dq_sarch)
            dq_sarch.clear()
            dist +=1
        
    return dist-1


dist_all =[]
for i in range(1,H+1):
    for j in range(1,W+1):
        dist_all.append(BSF(i,j) )
print(max(dist_all))

Solution (Python):
from collections import deque
import numpy as np



def bfs(sx, sy):
    
    d = [[float("-inf")] * m for i in range(n)]

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

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

    
    while que:
        
        p = que.popleft()
        
        
        
        
        for i in range(4):
            
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            
            
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "
                
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    a = np.max(d) 
    return a

n, m = map(int, input().split())
maze = [list(input()) for i in range(n)]
ans = 1

for x in range(n):
    for y in range(m):
        sx = x
        sy = y
        if maze[sx][sy] == "
            continue
        A = bfs(sx, sy)
        ans = max(A, ans)
print(int(ans))

Solution (Python):
from collections import deque
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
check=[[0,-1],[0,1],[-1,0],[1,0]]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            d = deque()
            d.append([i,j])
            a = [[-1] * w for _ in range(h)]
            a[i][j]=0
            while d:
                v = d.popleft()
                ii=v[0]
                jj=v[1]
                for c in check:
                    x=c[0]
                    y=c[1]
                    if ii+x in range(h) and jj+y in range(w):
                        if a[ii+x][jj+y]==-1:
                            if s[ii+x][jj+y]==".":
                                a[ii+x][jj+y]=a[ii][jj]+1
                                d.append([ii+x,jj+y])
                            else:
                                a[ii+x][jj+y]=0
            ans2=sorted(sum(a,[]),reverse=True)[0]
            if ans<ans2:
                ans=ans2
print(ans)

Solution (Python):


import sys
from collections import deque


def main():
    h, w = map(int, sys.stdin.readline().split())
    area = [[s for s in sys.stdin.readline().strip()] for _ in range(h)]
    start_point = {0: set(), 1: set(), 2: set(), 3: set(), 4: set()}
    min_neighbor = 4
    for i in range(h):
        for j in range(w):
            if area[i][j] == "
                continue
            roads = 0
            
            if i > 0 and area[i - 1][j] == ".":
                roads += 1
            
            if i < h - 1 and area[i + 1][j] == ".":
                roads += 1
            
            if j > 0 and area[i][j - 1] == ".":
                roads += 1
            
            if j < w - 1 and area[i][j + 1] == ".":
                roads += 1
            min_neighbor = min(min_neighbor, roads)
            start_point[roads].add((i, j))
    max_cost = 0
    for start in start_point[min_neighbor]:
        
        queue = deque()
        queue.append(start)
        cost = 0
        visited = set()
        while len(queue) > 0:
            roads = len(queue)
            found = False
            for i in range(roads):
                s = queue.popleft()
                if s in visited:
                    continue
                found = True
                visited.add(s)
                i = s[0]
                j = s[1]
                
                if i > 0 and area[i - 1][j] == ".":
                    queue.append((i - 1, j))
                
                if i < h - 1 and area[i + 1][j] == ".":
                    queue.append((i + 1, j))
                
                if j > 0 and area[i][j - 1] == ".":
                    queue.append((i, j - 1))
                
                if j < w - 1 and area[i][j + 1] == ".":
                    queue.append((i, j + 1))
            if not found:
                cost -= 1
            max_cost = max(cost, max_cost)
            if found:
                cost += 1
    print(max_cost)


if __name__ == '__main__':
    main()

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

H += 2
W += 2
P = [[] for _ in range(H*W)]

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

for y in range(1, H-1):
  for x in range(1, W-1):
    for z in move:
      P[x+W*y].append(x+z[0]+W*(y+z[1]))

for y in range(H-2):
  L = input()
  for x, s in enumerate(L):
    if s == "
      P[x+1 + W*(y+1)] = []

def bfs(x, y):
    s = x + W*y
    d = [-1] * (H*W)
    d[s] = 0
    p_old = [s]
    cnt = 1
    m_cnt = 0
    last = 1
    
    while p_old:
      p_new = []
      for i in p_old:
        for j in P[i]:
          if d[j] == -1 and P[j] != []:
            d[j] = cnt
            m_cnt = max(m_cnt, cnt)
            p_new.append(j)
      p_old = p_new
      cnt += 1
      
    return m_cnt

ans = 0

for y in range(1, H-1):
  for x in range(1, W-1):
    ans = max(ans, bfs(x, y))

print(ans)

Solution (Python):
from networkx import*
e=enumerate
_,*s=open(0)
g=[]
for i,t in e(s,1):
 for j,u in e(t):g+=[(k:=i*20+j,k+20)]*(u>'
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

Solution (Python):
from networkx import*
_,*s=open(i:=0)
g=[]
for t in s:
 i+=1;j=0
 for u in t:g+=[(k:=i*20+j,k+20)]*(u>'
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

Solution (Python):
from networkx import*
_,*s=open(i:=0)
g=[]
for t in s:
 i+=1;j=0
 for u in t:g+=[(k:=i*20+j,k+20)]*(u>'
print(max(t[i]for _,t in shortest_path_length(Graph(g))for i in t))

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


q = queue.Queue()
a = []
def init():
  global a
  a = []
  for i in range(h):
    a.append([-1] * w)

def bfs(cx, cy):
  nxs = [1, 0, -1, 0]
  nys = [0, -1, 0, 1]
  for i in range(4):
    nx = cx + nxs[i]
    ny = cy + nys[i]
    if 0 <= nx and nx < w and 0 <= ny and ny < h and m[ny][nx] == '.' and a[ny][nx] == -1:
      a[ny][nx] = a[cy][cx] + 1
      q.put([nx, ny])
  
def check(start_x, start_y):
  if m[start_y][start_x] == '
    return 0
  
  global a, q
  init()
  q.put([start_x, start_y])
  a[start_y][start_x] = 0
  end_x = -1
  end_y = -1
  while not q.empty():
    cx, cy = q.get()
    bfs(cx, cy)
    end_x = cx
    end_y = cy
  return a[end_y][end_x]

ans = 0
for i in range(h * w - 1):
    start_x = i % w
    start_y = i // w
    ans = max(ans, check(start_x, start_y))
    
print(ans)