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

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)





from collections import deque



INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    max_count = 0
    while queue:
        y,x,count = queue.popleft()
        max_count = max(max_count, count)
        if (y,x) in seen:
            continue
        seen.add((y, x))
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                queue.append((next_y, next_x, count+1))
                
    return max_count


def run():
    H, W = map(int, input().split())
    MAZE = ['
    for _ in range(H):
        s = input()
        s = '
        MAZE.append(s)
    MAZE.append('

    
    

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for s_i, s_j in ways:
        seen = set((s_i, s_j))
        min_count = bfs(MAZE, (s_i, s_j), seen)
        
        
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)





from collections import deque



INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    max_count = 0
    while queue:
        y,x,count = queue.popleft()
        max_count = max(max_count, count)
        if (y,x) in seen:
            continue
        seen.add((y, x))
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                queue.append((next_y, next_x, count+1))
                
    return max_count


def run():
    H, W = map(int, input().split())
    MAZE = ['
    for _ in range(H):
        s = input()
        s = '
        MAZE.append(s)
    MAZE.append('

    
    

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for s_i, s_j in ways:
        seen = set((s_i, s_j))
        min_count = bfs(MAZE, (s_i, s_j), seen)
        
        
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Solution (Python):
import copy
h,w = map(int, input().split()) 
map=[[-1]*w for i in range(h)]

for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="
            map[i][j]=-2

zanteisaidai=0

def saidaikyori(saisyo_gyou,saisyo_retu,saidaiti):
    map_copy=copy.deepcopy(map)
    map_copy[saisyo_gyou][saisyo_retu]=0
    kyori=0
    while kyori<300:
        for gyou in range(h):
            for retu in range(w):
                if map_copy[gyou][retu]==kyori:
                    if gyou+1<h:
                        if map_copy[gyou+1][retu]==-1:
                            map_copy[gyou+1][retu]=kyori+1
                    if 0<=gyou-1:
                        if map_copy[gyou-1][retu]==-1:
                            map_copy[gyou-1][retu]=kyori+1
                    if retu+1<w:
                        if map_copy[gyou][retu+1]==-1:
                            map_copy[gyou][retu+1]=kyori+1
                    if 0<=retu-1:
                        if map_copy[gyou][retu-1]==-1:
                            map_copy[gyou][retu-1]=kyori+1

        kyori+=1
    
    for gyou in range(h):
        for retu in range(w):
            saidaiti=max(saidaiti,map_copy[gyou][retu])
    return saidaiti

for gyou in range(h):
    for retu in range(w):
        if map[gyou][retu]==-1:
            zanteisaidai=saidaikyori(gyou,retu,zanteisaidai)

print(zanteisaidai)

Solution (Python):
h,w = map(int,input().split())
g = []
for _ in range(h):
    S = input()
    tmp = [str(i) for i in S]
    g.append(tmp)
from collections import deque

dp = [[0]*w for _ in range(h)]
def dfs(i,j):
    seen = [[False]*w for _ in range(h)]
    seen[i][j] = True
    q = deque([])
    q.append((i,j,0))
    dist=[(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        x,y,cnt = q.popleft()
        for dx,dy in dist:
            if 0 <=x+dx<h and 0<=y+dy<w and seen[x+dx][y+dy]==False and g[x+dx][y+dy]=='.':
                seen[x+dx][y+dy] = True
                q.append((x+dx,y+dy,cnt+1))
    return cnt
ans = 0
for i in range(h):
    for j in range(w):
        if g[i][j] =='.':
            ans =max(ans,dfs(i,j))
print(ans)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

def bfs(u):
    stack = deque([u])
    visited = set()
    seen = set()
    p = [[INF for j in range(W)] for i in range(H)]
    p[u[0]][u[1]] = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == "
                p[i][j] = -1

    while len(stack) > 0:
        v = stack.popleft()
        
        visited.add(v)
        

        a = (v[0] + 1, v[1])
        b = (v[0]    , v[1] + 1)
        c = (v[0] - 1, v[1])
        d = (v[0]    , v[1] - 1)

        e = [a, b, c, d]

        for ee in e:
            if ee[0] >= 0 and ee[0] <= H-1 and ee[1] >= 0 and ee[1] <= W-1:
                if S[ee[0]][ee[1]] == ".":
                    if ee not in visited:
                        p[ee[0]][ee[1]] = min(p[ee[0]][ee[1]], p[v[0]][v[1]] + 1)
                        if ee not in seen:
                            stack.append(ee)
                            seen.add(ee)

    ans = 0
    for i in range(H):
        ans = max(ans, max(p[i]))
    return ans

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

print(sol)

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

S = []
for i in range(H):
    S.append(list(input()))


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

for i_s in range(H):
    for j_s in range(W):
        if S[i_s][j_s]!='
            
            
            init = 10**9
            d = [[init] * W for i in range(H)]  
            
            que = deque([])
            que.append((i_s,j_s))
            d[i_s][j_s] = 0
            while que:
                p = que.popleft()
                for i in range(4):  
                    nx = p[0] + dx[i]
                    ny = p[1] + dy[i]
                    
                    if (0<=nx<H)and(0<=ny<W)and(S[nx][ny]!="
                        
                        que.append((nx, ny))  
                        
                        d[nx][ny] = d[p[0]][p[1]] + 1  
                        out=max(out,d[p[0]][p[1]] + 1)
            
            

print(out)

Solution (Python):
import queue

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

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

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            seen=[[0 for _ in range(w)] for _ in range(h)]
            length=[[0 for _ in range(w)] for _ in range(h)]
            q=queue.Queue()
            q.put([i,j])
            seen[i][j]=1
            while not q.empty():
                ci,cj=q.get()
                for ni,nj in [[ci-1,cj],[ci+1,cj],[ci,cj-1],[ci,cj+1]]:
                    if 0<=ni<h and 0<=nj<w and s[ni][nj]=="." and seen[ni][nj]==0:
                        q.put([ni,nj])
                        length[ni][nj]=length[ci][cj]+1
                        seen[ni][nj]=1
            ans=max(ans,length[ci][cj])

print(ans)

Solution (Python):






from collections import deque





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





def bfs(sx,sy):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[-1]*W for _ in range(H)]
    q = deque([])
    q.append([sx,sy])
    d[sx][sy] = 0
    ans = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != "
                q.append([nx,ny])
                d[nx][ny] = d[x][y] + 1
                ans = max(ans,d[nx][ny])
    return ans





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

Solution (Python):
import queue
import copy
q = queue.Queue()
h, w = map(int, input().split())
a = [list('
a = [['
a1 = copy.deepcopy(a)
ans = []
        
for i in range(1, h+1):
    for j in range(1, w+1):
        a = copy.deepcopy(a1)
        if a[i][j] == '
            continue        
        q.put([i, j, 0])
        while not q.empty():
            now = q.get()
            
            if a[now[0]][now[1]] == '.':
                ans.append(now[2])
                a[now[0]][now[1]] = '
            else:
                continue
                
            if a[now[0]+1][now[1]] != '
                q.put([now[0]+1, now[1], now[2]+1])
            if a[now[0]-1][now[1]] != '
                q.put([now[0]-1, now[1], now[2]+1])
            if a[now[0]][now[1]+1] != '
                q.put([now[0], now[1]+1, now[2]+1])
            if a[now[0]][now[1]-1] != '
                q.put([now[0], now[1]-1, now[2]+1])
        a1[i][j] == '
print(max(ans))

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

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


def bfs(x, y):
    dp = [[10000000] * W for _ in range(H)]
    dp[y][x] = 0
    if L[y][x] == '
        return dp
    else:
        d = deque()
        d.append([x, y])
        while len(d) > 0:
            s = d.popleft()
            for i in range(4):
                if (s[1] +
                    dy[i] >= 0 and s[1] +
                    dy[i] < H and s[0] +
                    dx[i] >= 0 and s[0] +
                        dx[i] < W):
                    if L[s[1] +
                         dy[i]][s[0] +
                                dx[i]] == '.' and dp[s[1] +
                                                     dy[i]][s[0] +
                                                            dx[i]] == 10000000:
                        d.append([s[0] + dx[i], s[1] + dy[i]])
                        dp[s[1] + dy[i]][s[0] + dx[i]] = dp[s[1]][s[0]] + 1

        return dp


max_num = 0
for i in range(H):
    for j in range(W):
        dp = bfs(j, i)
        for k in dp:
            for p in k:
                if (p == 10000000):
                    continue
                max_num = max(max_num, p)
print(max_num)

Solution (Python):
















































from collections import deque
H, W = map(int, input().split())
L = []
for _ in range(H):
    s = input()
    a = []
    for i in range(len(s)):
        a.append(s[i])
    L.append(a)

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


def bfs(x, y):
    dp = [[10000000] * W for _ in range(H)]
    dp[y][x] = 0
    if L[y][x] == '
        return dp
    else:
        d = deque()
        d.append([x, y])
        while len(d) > 0:
            s = d.popleft()
            for i in range(4):
                if (s[1] +
                    dy[i] >= 0 and s[1] +
                    dy[i] < H and s[0] +
                    dx[i] >= 0 and s[0] +
                        dx[i] < W):
                    if L[s[1] +
                         dy[i]][s[0] +
                                dx[i]] == '.' and dp[s[1] +
                                                     dy[i]][s[0] +
                                                            dx[i]] == 10000000:
                        d.append([s[0] + dx[i], s[1] + dy[i]])
                        dp[s[1] + dy[i]][s[0] + dx[i]] = dp[s[1]][s[0]] + 1

        return dp


max_num = 0
for i in range(H):
    for j in range(W):
        dp = bfs(j, i)
        for k in dp:
            for p in k:
                if (p == 10000000):
                    continue
                max_num = max(max_num, p)
print(max_num)

Solution (Python):
from collections import deque
import itertools

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



def bfs(x, y):
    
    d = [[-1] * w for _ in range(h)]
    
    d[x][y] = 0
    q = deque([(x, y)])
    while q:
        tx, ty = q.popleft()
        
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = tx + dx, ty + dy
            
            if 0 <= nx < h and 0 <= ny < w and g[nx][ny] == '.' and d[nx][ny] < 0:
                d[nx][ny] = d[tx][ty] + 1
                q.append((nx, ny))
    
    return max(list(itertools.chain.from_iterable(d)))



max_count = 0
for x in range(h):
    for y in range(w):
        
        if g[x][y] == ".":
            max_count = max(max_count, bfs(x, y))

print(max_count)

Solution (Python):
import math
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(l, d, cnt):
  tmp = []
  for n in l:
    i, j = n[0], n[1]
    if (0<i) and (S[i-1][j] == '.'):
      if d[i-1][j] > d[i][j]+1:
        d[i-1][j] = d[i][j]+1
        tmp.append([i-1, j])
    if (i<H-1) and (S[i+1][j] == '.'):
      if d[i+1][j] > d[i][j]+1:
        d[i+1][j] = d[i][j]+1
        tmp.append([i+1, j])
    if (0<j) and (S[i][j-1] == '.'):
      if d[i][j-1] > d[i][j]+1:
        d[i][j-1] = d[i][j]+1
        tmp.append([i, j-1])
    if (j<W-1) and (S[i][j+1] == '.'):
      if d[i][j+1] > d[i][j]+1:
        d[i][j+1] = d[i][j]+1
        tmp.append([i, j+1])
  if tmp == []:
    return cnt
  else:
    cnt += 1
    return main(tmp, d, cnt)
  
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      d = [[float('inf') for i in range(W)] for j in range(H)]
      d[i][j] = 0
      cnt = main([[i, j]], d, 0)
      ans = max(ans, cnt)
print(ans)

Solution (Python):

import copy
H,W=map(int,input().split())
MAZE=[0]*H
for i in range(H):
  MAZE[i]=list(str(input()))

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

def solve_maze(sy,sx):
  
  MAZE1=copy.deepcopy(MAZE)
  MAZE1[sy][sx]='
  queue=[]
  queue.append([sy,sx])
  d=[[100000000]*W for i in range(H)]
  d[sy][sx]=0
  while len(queue)>0:
    
    Q=queue.pop(0)
    move=d[Q[0]][Q[1]]

    
    for j in range(4):
      y=Q[0]+dy[j]
      x=Q[1]+dx[j]
      if 0<=y<=(H-1) and 0<=x<=(W-1) and MAZE1[y][x] == '.':
        queue.append([y,x])
        MAZE1[y][x] = '
        d[y][x] = move+1
  return move

d_max=0
for i in range(H):
  for j in range(W):
    if MAZE[i][j]=='.':
      d=solve_maze(i,j)
      if d>d_max:
        d_max=d
print(d_max)

Solution (Python):

import collections as cl
import sys
import copy


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


class Maze:
    def __init__(self, base_map, H, W):
        self.H = H
        self.W = W
        self.maze = base_map

        reachable = []
        for i in range(self.H):
            for j in range(self.W):
                reachable.append([i, j])

        self.reachable = reachable

    def solve(self):
        ans = 0
        for start in self.reachable:
            max_cost = self.calc_cost(start)
            ans = max(ans, max_cost)

        print(ans)

    def isNotReachable(self, i, j):
        return i < 0 or i >= self.H or j < 0 or j >= self.W or self.maze[i][j] == -1

    def calc_cost(self, start):
        costs = copy.deepcopy(self.maze)
        deque = cl.deque([])
        deque.append(start)
        ways = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        visited = [[False for j in range(self.W)] for i in range(self.H)]
        visited[start[0]][start[1]] = True

        while len(deque) > 0:
            cur_point = deque.popleft()
            i, j = cur_point[0], cur_point[1]
            for way in ways:
                next_i = i + way[0]
                next_j = j + way[1]
                if self.isNotReachable(next_i, next_j) or visited[next_i][next_j]:
                    continue
                visited[next_i][next_j] = True
                costs[next_i][next_j] = costs[i][j] + 1
                deque.append([next_i, next_j])
        max_cost = 0
        for row in costs:
            max_cost = max(max_cost, *row)
        return max_cost


def main():
    H, W = MI()
    base_map = []
    for _ in range(H):
        row = input()
        row_in_num = []
        for j in range(len(row)):
            if row[j] == ".":
                row_in_num.append(0)
            else:
                row_in_num.append(-1)

        base_map.append(row_in_num)

    maze = Maze(base_map, H, W)
    maze.solve()


main()

Solution (Python):
from collections import deque
h, w = map(int, input().split())
ma = [["
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i, j])
            while q:
                y, x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1, x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1, x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y, x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y, x-1])
            for l in range(h+2):
                ans = max(ans, max(p[l]))
            
print(ans)

Solution (Python):
from collections import deque
h, w = map(int, input().split())
ma = [["
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i, j])
            while q:
                y, x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1, x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1, x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y, x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y, x-1])
            for l in range(1, h+1):
                ans = max(ans, max(p[l]))
            
print(ans)

Solution (Python):
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


v=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=mp()
grid=["
ans=[]
for i in range(h):
    grid.append("
grid.append("
for i in range(h*w):
    ch=[[0]*(w+2) for i in range(h+2)]
    if grid[i//w+1][i%w+1]==".":
        sx,sy=i//w+1,i%w+1
        que=deque([[sx,sy,0]])
        while len(que):
            q=que.popleft()
            ch[q[0]][q[1]]=1
            ans.append(q[2])
            for x,y in v:
                if grid[q[0]+x][q[1]+y]=="." and ch[q[0]+x][q[1]+y]==0:
                    ch[q[0]+x][q[1]+y]=1
                    que.append([q[0]+x,q[1]+y,q[2]+1])
            
print(max(ans))

Solution (Python):
import queue
def main():
    h, w = map(int, input().split())
    st = [[1]*(w+2) for _ in range(h+2)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                st[i+1][j+1] = 0
    ans = 0
    for i in range(1, h+2):
        for j in range(1, w+2):
            if st[i][j] == 0:
                fs = [[float("inf")]*(w+2) for _ in range(h+2)]
                q = queue.Queue()
                fs[i][j] = 0
                q.put([i, j])
                while not q.empty():
                    y, x = q.get()
                    if st[y-1][x] == 0 and fs[y-1][x] > fs[y][x] + 1:
                        fs[y-1][x] = fs[y][x] + 1
                        q.put([y-1, x])
                    if st[y+1][x] == 0 and fs[y+1][x] > fs[y][x] + 1:
                        fs[y+1][x] = fs[y][x] + 1
                        q.put([y+1, x])
                    if st[y][x-1] == 0 and fs[y][x-1] > fs[y][x] + 1:
                        fs[y][x-1] = fs[y][x] + 1
                        q.put([y, x-1])
                    if st[y][x+1] == 0 and fs[y][x+1] > fs[y][x] + 1:
                        fs[y][x+1] = fs[y][x] + 1
                        q.put([y, x+1])
                    if ans < fs[y][x]:
                        ans = fs[y][x]
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
h, w = map( int, input().split() )
s = []
for _ in range( h ):
    s_i = list( str( input() ) )
    s.append( s_i )

def connect( v ):
    con_v = []
    if v[ 0 ] > 0:
        if s[ v[ 0 ] - 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] - 1, v[ 1 ] ) )
    if v[ 1 ] > 0:
        if s[ v[ 0 ] ][ v[ 1 ] - 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] - 1 ) )
    if v[ 0 ] < h - 1:
        if s[ v[ 0 ] + 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] + 1, v[ 1 ] ) )
    if v[ 1 ] < w - 1:
        if s[ v[ 0 ] ][ v[ 1 ] + 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] + 1 ) )
    return con_v

from heapq import heappush, heappop
INF = 10 ** 10
VISITED = 1
NOT_VISITED = 0
def longest_bfs( i, j ):
    cost = [ INF for _ in range( h * w ) ]
    cost[ i * w + j ] = 0
    visit = [ NOT_VISITED for _ in range( h * w ) ]
    queue = [ ( 0, ( i, j ) ) ]
    while len( queue ) > 0:
        c, v = heappop( queue )
        visit[ v[ 0 ] * w + v[ 1 ] ] = VISITED
        for u in connect( v ):
            if visit[ u[ 0 ] * w + u[ 1 ] ] == VISITED:
                continue
            if cost[ u[ 0 ] * w + u[ 1 ] ] > cost[ v[ 0 ] * w + v[ 1 ] ] + 1:
                cost[ u[ 0 ] * w + u[ 1 ] ] = cost[ v[ 0 ] * w + v[ 1 ] ] + 1
                heappush( queue, ( cost[ u[ 0 ] * w + u[ 1 ] ], u ) )
    return cost

longest_path = 0
for i in range( h ):
    for j in range( w ):
        if s[ i ][ j ] == "
            continue
        path_length = longest_bfs( i, j )
        for p in path_length:
            if p < INF and p > longest_path:
                longest_path = p
print( longest_path )

Solution (Python):
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(i, j):
    cost = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque()
    cost[i][j] = 0
    que.append((i, j))
    if s[i][j] == '
        return 0
    while que:
        ni, nj = que.popleft()
        for k in range(4):
            if 0 <= ni+dy[k] < h and 0 <= nj+dx[k] < w:
                if cost[ni+dy[k]][nj+dx[k]] != -1:
                    continue
                if s[ni+dy[k]][nj+dx[k]] == '.':
                    cost[ni+dy[k]][nj+dx[k]] = cost[ni][nj]+1
                    que.append((ni+dy[k], nj+dx[k]))

    cc = 0
    for i in range(h):
        for j in range(w):
            if cost[i][j] > cc:
                cc = cost[i][j]
    return cc

ans = 0
for i in range(h):
    for j in range(w):
        cost = bfs(i, j)
        ans = max(ans, cost)

print(ans)

Solution (Python):
from collections import deque
H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
mx = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == "
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[h][w] = 0
        que = deque([])
        que.append([h,w])
        while que != deque([]):
            u,v = que.popleft()
            for dir in range(4):
                nu = u + dx[dir]
                nv = v + dy[dir]

                if (nu < 0) or (nu >= H) or (nv < 0) or (nv >= W):
                    continue
                if field[nu][nv] == "
                    continue
                if dist[nu][nv] != -1:
                    continue
            
                que.append([nu,nv])
                dist[nu][nv] = dist[u][v] + 1
            
            
        for i in range(H):
            for j in range(W):
                if mx < dist[i][j]:
                    mx = dist[i][j]
    
print(mx)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy








def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

h,w = inpm()
maze = inplL(h)

ans = 0
for sh in range(h):
    for sw in range(w):
        if maze[sh][sw] == '
            continue

        q = queue.Queue()
        q.put((sh,sw,0))

        field = [[-1]*w for i in range(h)]
        tmp = 0
        while not q.empty():
            yy,xx,kk = q.get()
            if field[yy][xx] >= 0: continue

            field[yy][xx] = kk
            if tmp < kk:
                gh,gw = (yy,xx)
                tmp = kk
            if yy != h-1 and maze[yy+1][xx] == '.':
                q.put((yy+1,xx,kk+1))
            if xx != w-1 and  maze[yy][xx+1] == '.':
                q.put((yy,xx+1,kk+1))
            if yy != 0 and  maze[yy-1][xx] == '.':
                q.put((yy-1,xx,kk+1))
            if xx != 0 and  maze[yy][xx-1] == '.':
                q.put((yy,xx-1,kk+1))
        ans = max(ans,field[gh][gw])

print(ans)

Solution (Python):
from heapq import heappush, heappop
import sys
INFTY=sys.maxsize

def readinput():
    h,w=map(int,input().split())
    sMat=[]
    for _ in range(h):
        sMat.append(list(input()))
    nList=[]
    for _ in range(h*w):
        nList.append(set())
    for i in range(h):
        for j in range(w):
            if sMat[i][j]=='
                continue
            ij=i+j*h
            if i-1>=0 and sMat[i-1][j]=='.':
                nList[ij].add(ij-1)
            if i+1<h and sMat[i+1][j]=='.':
                nList[ij].add(ij+1)
            if j-1>=0 and sMat[i][j-1]=='.':
                nList[ij].add(ij-h)
            if j+1<w and sMat[i][j+1]=='.':
                nList[ij].add(ij+h)
    for i in range(h*w):
        nList[i]=list(nList[i])
    return h,w,nList

def dijkstra(s,n,nList):
    '''優先度付きキューを使用したダイクストラ法

    パラメーター
    s: 始点
    n: 頂点の数
    nList: [ 
        [vertex1, cost1], [vertex2, cost2], ...
        [vertex1, cost1], [vertex2, cost2], ...
        ...
    ]

    返り値
    d: 始点sから各頂点vまでの最短経路上の辺の重みの総和d[v]のリスト
    '''

    WHITE=0
    GRAY=1
    BLACK=2
    color=[WHITE]*n
    d=[INFTY]*n
    for i in range(h*w):
        if len(nList[i])==0:
            d[i]=0

    HQ=[]

    d[s]=0
    heappush(HQ,(d[s],s))

    while(len(HQ)>0):
        du,u=heappop(HQ)
        color[u]=BLACK

        if d[u]<du:
            continue

        for v in nList[u]:
            vw=1
            if color[v]!=BLACK:
                if d[u] + vw < d[v]:
                    d[v] = d[u] + vw
                    color[v]=GRAY
                    heappush(HQ, (d[v], v))
    return d

def main(h,w,nList):
    
    ans=0
    for i in range(h*w):
        if len(nList[i])>0:
            d=dijkstra(i,h*w,nList)
            
            dmax=max(d)
            ans=max(ans,dmax)
    return ans

if __name__=='__main__':
    h,w,nList=readinput()
    ans=main(h,w,nList)
    print(ans)

Solution (Python):
from copy import deepcopy
from collections import Counter, defaultdict, deque
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    dist[S_1][S_2] = 0
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        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:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
ans = 0
maze = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
start_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "
          dist[i][j] = 0
        else:
          start_list.append([i,j])
dist_copy = deepcopy(dist)
for k in start_list:
  dist = deepcopy(dist_copy)
  ans = max(ans,maze_solve(k[0],k[1],maze))
print(ans)