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 copy

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


def main():
    H, W = [int(s) for s in input().split()]
    MAP = []
    for h in range(H):
        row = input()
        MAP.append(list(row))

    points = []
    for h in range(H):
        for w in range(W):
            if MAP[h][w] == '.':
                points.append((h, w))

    max_step = 0
    for point in points:
        
        map = copy.deepcopy(MAP)
        step = search(map, point)
        max_step = max(step, max_step)
    print(max_step)


def search(map, point):
    map[point[0]][point[1]] = "0"

    currents = [point]
    new_points = []
    cost = 1
    while True:
        if len(currents) == 0:
            if len(new_points) == 0:
                
                return get_max_cost(map)
            currents = new_points
            new_points = []
            cost += 1
        point = currents.pop(0)

        for m in MOVEMENT:
            next_point = (point[0] + m[0], point[1] + m[1])
            if is_valid(map, next_point):
                map[next_point[0]][next_point[1]] = str(cost)
                new_points.append(next_point)


def print_map(map):
    for row in map:
        print("".join(row))


def is_valid(map, point):
    if point[0] < 0 or point[1] < 0:
        return False
    if point[0] >= len(map) or point[1] >= len(map[0]):
        return False
    if map[point[0]][point[1]] == ".":
        return True
    return False


def get_max_cost(map):
    max_cost = 0
    for row in map:
        for col in row:
            if col == '.':
                return None
            elif col == '
                continue
            max_cost = max(max_cost, int(col))
    return max_cost


if __name__ == "__main__":
    main()

Solution (Python):


from collections import deque

def main():
    H,W = map(int,input().split())
    S = [list(str(input())) for _ in range(H)]
    INF = float('inf')
    
    def maiz(x,y):
        if S[x][y] == "
            return -1
        else:
            length = [[INF for _ in range(W)] for _ in range(H)]
            length[x][y] = 0
            dx,dy = [1,0,-1,0],[0,1,0,-1]
            queue = deque()
            queue.append((x,y))
            while queue:
                x,y = queue.popleft()
                for i in range(4):
                    nx,ny = x+dx[i],y+dy[i]
                    if (0 <= nx and nx < H and 0 <= ny and ny < W and S[nx][ny] == "." and length[nx][ny] == INF):
                        queue.append((nx,ny))
                        length[nx][ny] = min(length[nx][ny],length[x][y] + 1)
            num = 0
            for i in range(H):
                for j in range(W):
                    if length[i][j] != INF:
                        num = max(num,length[i][j])
            return num
    
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans,maiz(i,j))
            
    print(ans)
        
if __name__ == "__main__":
    main()

Solution (Python):
H,W=map(int,input().split())
S=[list(input()) for i in range(H)]
S_=[[] for i in range(H)]
for i in range(H):
  for j in range(W):
    S_[i].append(S[i][j])
def chkS(i,j,H,W):
  if 0<=i<H and 0<=j<W:
    return True
  else:
    return False
import copy
  
def tansaku(i,j,__):
  global H,W,S
  X=[]
  
  ni=i
  nj=j-1
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass
    
  
  ni=i
  nj=j+1
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass
    
  
  ni=i+1
  nj=j
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass
    
    
  
  ni=i-1
  nj=j
  if chkS(ni,nj,H,W):
    if S[ni][nj]=='.':
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    elif S[ni][nj]=='
      pass
    elif S[ni][nj]>S[i][j]+1:
      S[ni][nj]=S[i][j]+1
      X.append([ni,nj])
    else:
      pass

  if len(X)==0:
    return X,S[i][j]
  else:
    return X,__+1

  
ans=0
for i in range(H):
  for j in range(W):
    if S_[i][j] =='.':
      _=[[i,j]]
      S=copy.deepcopy(S_)
      S[i][j]=0
      __=0
      while len(_)>0:
        _X=[]
        for NEXT in _:
          X,__=tansaku(NEXT[0],NEXT[1],__)
          _X.extend(X)
        _=_X
      if __>ans:
        ans=__
print(ans)

Solution (Python):
from collections import deque
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans=0
for i in range(H):
    for j in range(W):
        if S[i][j]=="
            continue
        st=(i,j)
        q=deque([st])
        dx=[1,-1,0,0]
        dy=[0,0,1,-1]
        dist=[[-1 for j in range(W)] for i in range(H)]
        dist[st[0]][st[1]]=0
        while(len(q)>0):
            r=q.popleft()
            x,y=r
            for k in range(4):
                nx=x+dx[k]
                ny=y+dy[k]
                if 0<=nx<H and 0<=ny<W:
                    if dist[nx][ny]==-1 and S[nx][ny]==".":
                        dist[nx][ny]=dist[x][y]+1
                        q.append((nx,ny))
        tmp=max([max(i) for i in dist])
        ans=max(tmp,ans)
print(ans)

Solution (Python):


from collections import deque
import math


def inputIntList():
  return [int(s) for s in input().split()]


def inputInt():
  return int(input())


def main():
  H, W = inputIntList()
  S = [[s for s in input()] for _ in range(H)]

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

      dist = [[-1 for _ in range(W)] for _ in range(H)]
      q = deque()

      start = (si, sj)
      if dist[si][sj] == -1:
        dist[si][sj] = 0
        q.append(start)

      while q:
        qi, qj = q.popleft()
        for di, dj in (-1, 0), (0, -1), (1, 0), (0, 1):
          ni = qi + di
          nj = qj + dj
          if ni < 0 or ni >= H:
            continue
          if nj < 0 or nj >= W:
            continue
          if S[ni][nj] == '
            continue
          if dist[ni][nj] == -1:
            dist[ni][nj] = dist[qi][qj]+1
            q.append((ni, nj))
            ans = max(ans, dist[ni][nj])
  return ans


if __name__ == "__main__":
  print(main())

Solution (Python):
from collections import deque

INF = -1

sizeI, sizeJ = map(int, input().split())
a = [input().rstrip() for _ in range(sizeI)]

def bfs(startI, startJ):
    dist = [[INF for _ in range(sizeJ)] for _ in range(sizeI)]
    dist[startI][startJ] = 0
    q = deque([(startI, startJ)])
    while q:
        i, j = q.pop()
        curDist = dist[i][j]
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < sizeI and 0 <= nj < sizeJ and dist[ni][nj] == INF and a[ni][nj] == '.':
                dist[ni][nj] = 1 + curDist
                q.appendleft((ni, nj))
    return max([max(row) for row in dist])

ret = -float('inf')
for i in range(sizeI):
    for j in range(sizeJ):
        if a[i][j] == '.':
            ret = max(ret, bfs(i, j))
print(ret)

Solution (Python):
from collections import deque

INF = -1

sizeI, sizeJ = map(int, input().split())
a = [input().rstrip() for _ in range(sizeI)]

def bfs(startI, startJ):
    dist = [[INF for _ in range(sizeJ)] for _ in range(sizeI)]
    dist[startI][startJ] = 0
    q = deque([(startI, startJ)])
    while q:
        i, j = q.pop()
        curDist = dist[i][j]
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < sizeI and 0 <= nj < sizeJ and dist[ni][nj] == INF and a[ni][nj] == '.':
                dist[ni][nj] = 1 + curDist
                q.appendleft((ni, nj))
    return max([max(row) for row in dist])

ret = -float('inf')
for i in range(sizeI):
    for j in range(sizeJ):
        if a[i][j] == '.':
            ret = max(ret, bfs(i, j))
print(ret)

Solution (Python):
from collections import deque
import copy

def cha(maze,h,w):
    maze = copy.deepcopy(maze)
    for i in range(h):
        for j in range(w):
            if maze[i][j] == ".":
                maze[i][j] = 10**10
            if maze[i][j] == "
                maze[i][j] = -1
    return maze

def bfs(maze,sy,sx):
    maze = copy.deepcopy(maze)
    maze[sy][sx] = 0
    que = deque([[sy,sx]])
    while que:
        y,x = que.popleft()
        for next_y,next_x in [(y+1,x),(y-1,x),(y,x+1),(y,x-1)]:
            if maze[next_y][next_x] == -1:
                continue
            dist = maze[next_y][next_x]
            if dist > maze[y][x] + 1:
                maze[next_y][next_x] = maze[y][x] + 1
                que.append([next_y,next_x])
    return maze

def search(maze):
    c = 0
    for i in maze:
        i.append(c)
        c = max(i)
    return c

def _main():
    h,w = map(int,input().split())
    maze = [["
    for _ in range(h):
        maze.append(list(input()))
    maze.append(["
    for i in range(h+2):
        maze[i].insert(0,"
        maze[i].insert(w+1,"
    C = 0
    for sy in range(h+2):
        for sx in range(w+2):
            if maze[sy][sx] == ".":
                C = max((search(bfs(cha(maze,h+2,w+2),sy,sx)),C))
    print(C)

if __name__=="__main__":
    _main()

Solution (Python):
from collections import deque
h,w=map(int,input().split())

maze=[]
INF=10**6
dx=[1,0,-1,0]
dy=[0,1,0,-1]


for i in range(h):
    row=list(input())
    maze.append(row)


ans=0
for i in range(h):
    for j in range(w):
        queue=deque()
        d=[]
        used=[]
        for p in range(h):
            used.append([False for k in range(w)])
            d.append([INF for k in range(w)])
            
        if maze[i][j]==".":
            d[i][j]=0
            used[i][j]=True
            queue.append([i,j])

            while len(queue)>0:
                y,x=queue.popleft()
                for k in range(4):
                    nx=x+dx[k]
                    ny=y+dy[k]
                    if 0<=ny<h and 0<=nx<w:
                        if d[ny][nx]>d[y][x]+1 and maze[ny][nx]=="." and 0==used[ny][nx]:
                            d[ny][nx]=d[y][x]+1
                            ans=max(ans,d[ny][nx])
                            queue.append([ny,nx])
                            used[ny][nx]=True
print(ans)

Solution (Python):
from collections import deque


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

INF = 10 ** 6
m = [[10 ** 6] * W for _ in range(H)]
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]


def bfs(y, x):
    q = deque()
    q.append((y, x))

    while len(q):
        y, x = q.popleft()

        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]

            if (0 <= ny < H and 0 <= nx < W and
                m[ny][nx] == INF and S[ny][nx] != '

                q.append((ny, nx))
                m[ny][nx] = m[y][x] + 1

ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] != "
            m = [[10 ** 6] * W for _ in range(H)]
            m[y][x] = 0
            bfs(y, x)
            for i in range(H):
                for j in range(W):
                    if m[i][j] != INF:
                        ans = max(ans, m[i][j])

print(ans)

Solution (Python):

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

def bfs(sx, sy):
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque([[sx, sy]])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(len(dx)):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == -1\
                and maze[nx][ny] == ".":
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
                    q.append([nx, ny])
    dist = -1
    for i in range(H):
        dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "
            continue
        ans = max(ans, bfs(x,y))
print(ans)

Solution (Python):

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

def bfs(sx, sy):
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    q = deque([[sx, sy]])
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(len(dx)):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and visited[nx][ny] == -1\
                and maze[nx][ny] == ".":
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
                    q.append([nx, ny])
    dist = -1
    for i in range(H):
        dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "
            continue
        ans = max(ans, bfs(x,y))
print(ans)

Solution (Python):



import sys
def p(*_a):
  _s=" ".join(map(str,_a))
  
  sys.stderr.write(_s+"\n")

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

S=[ "" for _ in range(H+2) ]


S[0]="
S[H+1]="
for h in range(1,H+1):
	s = input()
	S[h] = "



XY=[[1,0],[-1,0],[0,1],[0,-1]]

INF=float("inf") 
ans=0

from collections import deque

for h in range(1,H+1):
	for w in range(1,W+1):

		if S[h][w]=="

		M=[[ INF for w in range(W+2) ] for h in range(H+2)]
		M[h][w]=0

		Q = deque()
		Q.append([h,w])
		mmax=0

		
		
		while Q:
			h,w=Q.popleft()
			
			if S[h][w]=="
			
			m = M[h][w]
			mmax=max(mmax,m)
			for x,y in XY:
				if S[h+y][w+x]=="
				
				if M[h+y][w+x] > (m+1):
					M[h+y][w+x] = m+1
					Q.append([h+y,w+x])
					mmax=max(mmax,m+1)

			

		for MH in M:
			for m in MH:
				if m==INF: continue
				ans=max(ans,m)





print(ans)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

h,w = inpl()
s = [input() for i in range(h)]

dx = [1,0,-1,0]
dy = [0,1,0,-1]
res = -INF
for y in range(h):
    for x in range(w):
        if s[y][x] == '
            continue
        ans = 0
        dist = [[-1]*w for i in range(h)]
        dist[y][x] = 0
        q = deque([[x,y]])
        while q:
            v = q.popleft()
            
            vx,vy = v[0],v[1]
            for dir in range(4):
                ny = vy + dy[dir]
                nx = vx + dx[dir]
                if ny<0 or ny>h-1 or nx<0 or nx>w-1:
                    continue
                if s[ny][nx] == '
                    continue
                dist[ny][nx] = dist[vy][vx] + 1
                ans = max(ans, dist[ny][nx])
                q.append([nx,ny])
        
            
        res = max(res, ans)
print(res)

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

def calc_distance(maze):
    global maxd
    global sx, sy
    global nextx, nexty
    INF = 100000000

    field_x_length = len(maze[0])
    field_y_length = len(maze)

    distance = []
    for i in range(field_y_length):
        distance.append([])
        for j in range(field_x_length):
            distance[i].append(INF)

    queue = []

    queue.insert(0, (sy, sx))

    distance[sy][sx] = 0

    while True:
        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 and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
                if maxd < distance[y][x] + 1:
                    maxd = distance[y][x] + 1
                    nexty = ny
                    nextx = nx
        if len(queue) == 0: break

maxd = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            sx, sy = j, i
        else: continue
        distance = calc_distance(maze)
print(maxd)

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


def calc(sh, sw):
    dist = [[float('inf')] * W for i in range(H)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dist[sh][sw] = 0
    que = deque([[sh, sw]])

    while que:
        sh, sw = que.pop()
        for dh, dw in directions:
            if not ((0 <= sh + dh < H) and (0 <= sw + dw < W)):
                continue

            if G[sh + dh][sw + dw] == '
                continue

            if dist[sh + dh][sw + dw] != float('inf'):
                continue

            dist[sh + dh][sw + dw] = dist[sh][sw] + 1
            que.appendleft([sh + dh, sw + dw])

    ret = 0
    for d in dist:
        for w in range(W):
            if d[w] == float('inf'):
                continue
            ret = max(ret, d[w])

    return ret


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

print(ans)

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

chart = [input() for _ in range(H)]

def node(h, w):
    return h * W + w

minDist = [[10**10] * N for _ in range(N)]

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

for h in range(H):
    for w in range(W):
        if chart[h][w] == '
            continue

        if h > 0 and chart[h - 1][w] == '.':
            minDist[node(h, w)][node(h - 1, w)] = 1
            minDist[node(h - 1, w)][node(h, w)] = 1
        if h < H - 1 and chart[h + 1][w] == '.':
            minDist[node(h, w)][node(h + 1, w)] = 1
            minDist[node(h + 1, w)][node(h, w)] = 1
        if w > 0 and chart[h][w - 1] == '.':
            minDist[node(h, w)][node(h, w - 1)] = 1
            minDist[node(h, w - 1)][node(h, w)] = 1
        if w < W - 1 and chart[h][w + 1] == '.':
            minDist[node(h, w)][node(h, w + 1)] = 1
            minDist[node(h, w + 1)][node(h, w)] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = minDist[i][k] + minDist[k][j]
            if minDist[i][j] > d:
                minDist[i][j] = d

ans = 0
for dists in minDist:
    for d in dists:
        if d < 10**10:
            ans = max(ans, d)

print(ans)

Solution (Python):
from collections import deque
 
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
 
dirr = ((1, 0), (0, 1), (-1, 0), (0, -1))
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
        q = deque()
        q.append((i, j, 0))
        visited = [[False] * w for _ in range(h)]
        visited[i][j] = True
        while q:
            x, y, z = q.popleft()
            for dx, dy in dirr:
                nx, ny = x + dx, y + dy
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append((nx, ny, z + 1))
                        if z + 1 > ans: ans = z + 1
                        visited[nx][ny] = True
print(ans)

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

def validPoint(i,j):
	if i < 0 or i >= H:
		return False
	if j < 0 or j >= W:
		return False
	return True

def wfs(start):
	search = deque([(start, 0)])
	dist = [[-1 for j in range(W)] for i in range(H)]
	
	
	v = [(0,-1), (0,1), (-1,0), (1,0)]
	dist[start[0]][start[1]] = 0
	while len(search) > 0:
		s = search.popleft()
		i,j = s[0][0], s[0][1]
		d = s[1]
		if dist[i][j] < d:
			continue
		for (x,y) in v:
			if validPoint(i+x, j+y):
				if m[i+x][j+y] == "
					continue
				if dist[i+x][j+y] == -1 or dist[i+x][j+y] > d+1:
					dist[i+x][j+y] = d+1
					search.append(((i+x,j+y),d+1))
	return max([max(dist[i]) for i in range(H)])

ans = 0
for i in range(H):
	for j in range(W):
		if m[i][j] == "
			continue
		ans = max(ans, wfs((i,j)))
print(ans)

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

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

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '
        q = deque()
        q.append([i, j, 0])
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        visited[i][j] = True
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q[0]
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
                        visited[nx][ny] = True
                        ans = max(ans, z + 1)
            q.popleft()
print(ans)

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

def bfs(a,b):
    maxdist=0
    da=[1,-1,0,0]
    db=[0,0,1,-1]
    dist=[[-1]*w for i in range(h)]
    dist[a][b]=0
    stack=deque([(a,b)])
    while stack:
        y,x=stack.popleft()
        D=dist[y][x]
        for dy,dx in zip(da,db):
            X=x+dx
            Y=y+dy
            if 0<=Y and Y<=h-1 and X<=w-1 and 0<=X:
                if meiro[Y][X]=='.':
                    if dist[Y][X]==-1:
                        dist[Y][X]=D+1
                        stack.append((Y,X))
                    elif dist[Y][X]>0:
                        dist[Y][X]=min(dist[Y][X],D+1)
                else:
                    dist[Y][X]==-(10**6)
    return dist
saidai=0
for i in range(h):
    for j in range(w):
        if meiro[i][j]=='.':
            saidai=max(saidai,np.array(bfs(i,j)).max())
print(saidai)

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


def calc(sh, sw):
    dist = [[float('inf')] * W for i in range(H)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    dist[sh][sw] = 0
    que = deque([[sh, sw]])

    while que:
        sh, sw = que.pop()
        for dh, dw in directions:
            if not ((0 <= sh + dh < H) and (0 <= sw + dw < W)):
                continue

            if G[sh + dh][sw + dw] == '
                continue

            if dist[sh + dh][sw + dw] != float('inf'):
                continue

            dist[sh + dh][sw + dw] = dist[sh][sw] + 1
            que.appendleft([sh + dh, sw + dw])

    ret = 0
    for d in dist:
        for w in range(W):
            if d[w] == float('inf'):
                continue
            ret = max(ret, d[w])

    return ret


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

print(ans)

Solution (Python):
import collections


def search(data, w, h, start):
    maps = [[-1] * w for i in range(h)]
    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    que = collections.deque([(start[1], start[0])])
    maps[start[1]][start[0]] = 0
    result = 0
    while que:
        y, x = que.popleft()
        num = maps[y][x]
        for m in move:
            if 0 <= y+m[0] < h and 0 <= x+m[1] < w:
                if maps[y+m[0]][x+m[1]] != -1:
                    continue
                if data[y+m[0]][x+m[1]] == '
                    continue
                elif data[y+m[0]][x+m[1]] == '.':
                    maps[y+m[0]][x+m[1]] = num+1
                    result = max(result, maps[y+m[0]][x+m[1]])
                    que.append((y+m[0], x+m[1]))
    return result


def main():
    h, w = map(int, input().split())
    data = []
    for i in range(h):
        tmp = input()
        data.append([j for j in tmp])

    ans = 0
    for i in range(h*w-1):
        if data[i//w][i % w] == '.':
            ans = max(search(data, w, h, (i % w, i//w)), ans)
    print(ans)


main()

Solution (Python):

from collections import deque 

import copy 


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

maze = [list(input()) for _ in range(h)] 

ans=0

def bfs(sx,sy,c):
  maxlen=0
  que = deque() 
  que.append([sx,sy,0]) 
  c[sy][sx] = '@'
  dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]] 

  
  while que: 

    x,y,tmp = que.popleft() 

    for dx,dy in dxy: 

      if 0 <= x+dx < w and 0 <= y+dy < h and c[y+dy][x+dx]=='.': 
        que.append([x+dx,y+dy,tmp+1]) 
        c[y+dy][x+dx] = '@' 
        maxlen=max(maxlen,tmp+1)
  return maxlen

for Sy in range(h):
  for Sx in range(w):
    Maze=copy.deepcopy(maze)
    if Maze[Sy][Sx]=='.':
      
      Tmp=bfs(Sx,Sy,Maze)
      
      ans=max(ans,Tmp)
print(ans)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
h += 2; w += 2
maze = "
for _ in range(h-2):
    maze += "
maze += "

def bfs(start):
    INF = h*w+1
    dist = [INF] * (h*w)
    dist[start] = 0
    q = deque([start])
    while q:
        cur_loc = q.popleft()
        cur_val = dist[cur_loc]
        for move in (-1,1,w,-w):
            next_loc = cur_loc + move
            if maze[next_loc] == "
                continue
            next_val = cur_val + 1
            if next_val >= dist[next_loc]:
                continue
            dist[next_loc] = next_val
            q.append(next_loc)
    return max(x for x in dist if x < INF)

ans = max(bfs(start) for start in range(h*w) if maze[start] != "
print(ans)

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

Glaph = [[float("inf") for i in range(H*W)] for j in range( H*W )]
for i in range(H):
  for j in range(W):
    
    if S[i][j] == ".":
 
      Glaph[i*W+j][i*W+j] = 0
      if i-1 != -1 and S[i-1][j] == ".":
        Glaph[i*W+j][(i-1)*W+j] = 1
      if i+1 != H and S[i+1][j] == ".":
        Glaph[i*W+j][(i+1)*W+j] = 1
      if j-1 != -1 and S[i][j-1] == ".":
        Glaph[i*W+j][i*W+(j-1)] = 1
      if j+1 != W and S[i][j+1] == ".":
        Glaph[i*W+j][i*W+(j+1)] = 1
        
def warshall_floyd(n) : 
  for i in range(n):      
    for j in range(n):    
      for k in range(n):  
        Glaph[j][k] = min(Glaph[j][k], Glaph[j][i] + Glaph[i][k])
        
warshall_floyd(H*W)

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

print(ans)

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

max_step = 0
for i in range(H * W):
    sy, sx = i // W, i % W
    if S[sy][sx] == "
        continue

    steps = [[-1] * W for _ in range(H)]
    steps[sy][sx] = 0
    queue = [(sy, sx)]
    while len(queue) >= 1:
        cy, cx = queue.pop(0)
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                continue
            if S[ny][nx] == "
                continue
            queue.append((ny, nx))
            steps[ny][nx] = steps[cy][cx] + 1

    ms = max(max(r) for r in steps)
    max_step = max(ms, max_step)

print(max_step)

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

max_step = 0
for i in range(H * W):
    sy, sx = i // W, i % W
    if S[sy][sx] == "
        continue

    steps = [[-1] * W for _ in range(H)]
    steps[sy][sx] = 0
    queue = [(sy, sx)]
    while len(queue) >= 1:
        cy, cx = queue.pop(0)
        for dy, dx in ((0, 1), (0, -1), (1, 0), (-1, 0)):
            ny, nx = cy + dy, cx + dx
            if not (0 <= ny <= H - 1 and 0 <= nx <= W - 1):
                continue
            if S[ny][nx] == "
                continue
            queue.append((ny, nx))
            steps[ny][nx] = steps[cy][cx] + 1

    ms = max(max(r) for r in steps)
    max_step = max(ms, max_step)

print(max_step)

Solution (Python):
INF = 1001001001
from collections import deque
h,w = map(int,input().split())
s = [input() for _ in range(h)]
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 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):

from collections import deque



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

step=[[1,0],[-1,0],[0,1],[0,-1]]

mx=0
for h in range(H):
    for w in range(W):
        if S[h][w]=="
        chk=[[False]*W for i in range(H)]
        q=deque([[h,w,0]])
        chk[h][w]=True
        while q:
            y,x,c=q.popleft()
            for dh,dw in step:
                if not (0<=y+dh<H and 0<=x+dw<W):continue
                if S[y+dh][x+dw]=="
                if chk[y+dh][x+dw]==False:
                    chk[y+dh][x+dw]=True
                    q.append([y+dh,x+dw,c+1])
                else:
                    mx=max(mx,c)

print(mx)