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())
S = [input() for _ in range(H)]

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


def bfs(i, j):
    if S[i][j] == '
        return 0

    visited = [[False] * W for _ in range(H)]
    visited[i][j] = True
    que = deque([(i, j, 0)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = True
                que.append((ni, nj, d+1))

    return d


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, bfs(i, j))
print(ans)

Solution (Python):
import sys
 
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()
nas = lambda: stdin.readline().split()

from collections import deque

h, w = na()
s = [ns() for i in range(h)]
maze = [[s[i][j] for j in range(w)] for i in range(h)]
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

def bfs(sx, sy):
    q = deque()
    inf = 1 << 60
    d = [[inf for i in range(w)] for i in range(h)]
    d[sy][sx] = 0
    q.append((sx, sy))
    mx = 0
    while len(q):
        p = q.popleft()
        for i in range(4):
            nx, ny = p[0] + dx[i], p[1] + dy[i]
            if 0 <= nx and nx < w and 0 <= ny and ny < h and maze[ny][nx] != '
                q.append((nx, ny))
                update = d[p[1]][p[0]] + 1
                d[ny][nx] = update
                mx = max(mx, update)
    return mx

ans = 0
for i in range(h):
    for j in range(w):
        if maze[i][j] != '
            ans = max(ans, bfs(j, i))

print(ans)

Solution (Python):

def bfs(source: int):
    queue = [source]
    dist = {source: 0}
    while queue:
        x = queue.pop(0)
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] == "." and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global W, maze
    H, W = map(int, input().split())
    H, W = H + 2, W + 2
    maze = "
    for _ in range(H - 2):
        maze += "
    maze += "
    ans = max(bfs(i) for i, c in enumerate(maze) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = [0] * (H * W)
    dist[start] = 1
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] == "." and not dist[nx]:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist) - 1


def main():
    global H, W, maze
    H, W = map(int, input().split())
    H, W = H + 2, W + 2
    maze = "
    for _ in range(H - 2):
        maze += "
    maze += "
    ans = max(bfs(i) for i, c in enumerate(maze) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] == "." and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global W, maze
    H, W = map(int, input().split())
    H, W = H + 2, W + 2
    maze = "
    for _ in range(H - 2):
        maze += "
    maze += "
    ans = max(bfs(i) for i, x in enumerate(maze) if x == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global W, maze
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    maze = [False] * W  
    for s in S:
        maze += [False] + [c == "." for c in s] + [False]
    maze += [False] * W
    ans = max(bfs(i) for i, x in enumerate(maze) if x)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque


def bfs(start: int):
    queue = deque([start])
    dist = {start: 0}
    while queue:
        x = queue.popleft()
        for nx in (x + 1, x - 1, x + W, x - W):
            if maze[nx] and nx not in dist:
                dist[nx] = dist[x] + 1
                queue.append(nx)
    return max(dist.values())


def main():
    global H, W, maze
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    maze = [0] * W  
    for s in S:
        maze += [0] + [c == "." for c in s] + [0]
    maze += [0] * W
    ans = max(bfs(i) for i, x in enumerate(maze) if x)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque

MOD = 10 ** 9 + 7
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def bfs(sx: int, sy: int):
    queue = deque([(sx, sy)])
    dist = {sx * MOD + sy: 0}
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if S[nx][ny] == ".":
                if nx * MOD + ny not in dist:
                    dist[nx * MOD + ny] = dist[x * MOD + y] + 1
                    queue.append((nx, ny))
    return max(dist.values())


def main():
    global S
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    S = ["
    ans = max(bfs(i, j) for i, s in enumerate(S) for j, c in enumerate(s) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, defaultdict

INF = 1 << 30
MOD = 10 ** 9 + 7
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def bfs(sx: int, sy: int):
    queue = deque([(sx, sy)])
    dist = defaultdict(lambda: INF)
    dist[sx * MOD + sy] = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if S[nx][ny] == ".":
                if nx * MOD + ny not in dist:
                    dist[nx * MOD + ny] = dist[x * MOD + y] + 1
                    queue.append((nx, ny))
    return max(dist.values())


def main():
    global S
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    S = ["
    ans = max(bfs(i, j) for i, s in enumerate(S) for j, c in enumerate(s) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, defaultdict

INF = 1 << 30
MOD = 10 ** 9 + 7
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def bfs(sx: int, sy: int):
    queue = deque([(sx, sy)])
    dist = defaultdict(lambda: INF)
    dist[sx * MOD + sy] = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if S[nx][ny] == "." and dist[x * MOD + y] + 1 < dist[nx * MOD + ny]:
                dist[nx * MOD + ny] = dist[x * MOD + y] + 1
                queue.append((nx, ny))
    return max(dist.values())


def main():
    global S
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    S = ["
    ans = max(bfs(i, j) for i, s in enumerate(S) for j, c in enumerate(s) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, defaultdict

INF = 1 << 30
MOD = 10 ** 9 + 7
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def bfs(sx: int, sy: int):
    queue = deque([(sx, sy)])
    dist = defaultdict(lambda: INF)
    dist[sx * MOD + sy] = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if S[nx][ny] == ".":
                if dist[x * MOD + y] + 1 < dist[nx * MOD + ny]:
                    dist[nx * MOD + ny] = dist[x * MOD + y] + 1
                    queue.append((nx, ny))
    return max(dist.values())


def main():
    global S
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    S = ["
    ans = max(bfs(i, j) for i, s in enumerate(S) for j, c in enumerate(s) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from collections import deque, defaultdict

INF = 1 << 30
MOD = 10 ** 9 + 7
dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]


def bfs(sx: int, sy: int):
    queue = deque([(sx, sy)])
    dist = defaultdict(lambda: INF)
    dist[sx * MOD + sy] = 0
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            if S[nx][ny] == ".":
                if dist[x * MOD + y] + 1 < dist[nx * MOD + ny]:
                    dist[nx * MOD + ny] = dist[x * MOD + y] + 1
                    queue.append((nx, ny))
    return max(dist.values())


def main():
    global S
    H, W, *S = open(0).read().split()
    H, W = int(H) + 2, int(W) + 2
    S = ["
    ans = max(bfs(i, j) for i, s in enumerate(S[1:H + 1], 1) for j, c in enumerate(s[1:W + 1], 1) if c == ".")
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

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




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

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

    
    
    
    
    
    
    
    
    

    
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
    
    max_root = 0
    
    while que:
        
        p = que.popleft()
        
        
        
        
        for i in range(4):
            
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            
            
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] != "
                
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
                max_root = max(max_root, d[ny][nx])    
    return max_root



ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            ans = max(bfs(h, w), ans)
print(ans)

Solution (Python):

from collections import deque

INF = int(1e20)
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

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

    for si in range(h):
        for sj in range(w):
            if maze[si][sj] == '
                continue
            dist = [[INF for i in range(w)] for j in range(h)]
            q = deque()

            def update(i, j, x):
                if dist[i][j] != INF:
                    return None
                dist[i][j] = x
                q.append((i,j))
            
            update(si, sj, 0)
            while len(q) != 0:
                i, j = q.popleft()

                for dir in range(4):
                    ni = i+di[dir]
                    nj = j+dj[dir]
                    if (ni<0)|(ni>=h)|(nj<0)|(nj>=w):
                        continue
                    if maze[ni][nj] == '
                        continue
                    update(ni, nj, dist[i][j]+1)
        
            for i in range(h):
                for j in range(w):
                    if dist[i][j] == INF:
                        continue
                    ans = max(ans, dist[i][j])
    print(ans)

main()

Solution (Python):

from collections import deque
from collections import namedtuple

Vertex = namedtuple('Vertex', ['i', 'j'])  
INF = int(1e10)
di = [1, 0, -1, 0]
dj = [0, 1, 0, -1]

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

    for si in range(h):
        for sj in range(w):
            if maze[si][sj] == '
                continue 
            dist = [[INF for i in range(w)] for j in range(h)]
            q = deque()

            def update(i, j, x):
                if dist[i][j] != INF:
                    return None
                dist[i][j] = x
                q.append(Vertex(i, j))


            update(si, sj, 0)
            while len(q) != 0:
                i, j = q.popleft()
                for dir in range(4):
                    ni = i+di[dir]
                    nj = j+dj[dir]
                    if (ni < 0) | (ni >= h) | (nj < 0) | (nj >= w):
                        continue

                    if maze[ni][nj] == '
                        continue
                    update(ni, nj, dist[i][j]+1)

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

    print(ans)

main()

Solution (Python):
import sys
import pprint
from collections import deque
import itertools

def bfs(i,j,maze,depth):
    queue = deque([[i,j]])
    depth[i][j] = 0
    while queue:
        x, y = queue.popleft()


        if maze[x][y] == '
            continue


        for a,b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_x, new_y = x+a, y+b
            if maze[new_x][new_y] == '
                pass


            else:
                depth[new_x][new_y] = depth[x][y] + 1
                queue.append([new_x, new_y])


    return max(list(itertools.chain.from_iterable(depth)))


def main():
    H, W = list(map(int, input().split()))
    maze = [['


    for m in range(1,H+1):
        maze[m][1:W+1] = list(input())

    ans = []
    for i in range(1, H+1):
        for j in range(1, W+1):


            depth = [[-1] * (W+2) for __ in range(H+2)]
            ans.append(bfs(i,j,maze,depth))

    print(max(ans))

main()

Solution (Python):
import sys
import pprint
from collections import deque
import itertools

def bfs(i,j,maze,depth):
    queue = deque([[i,j]])
    depth[i][j] = 0
    while queue:
        x, y = queue.popleft()

        if maze[x][y] == '
            continue

        for a,b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_x, new_y = x+a, y+b
            if maze[new_x][new_y] == '
                pass
            else:
                depth[new_x][new_y] = depth[x][y] + 1
                queue.append([new_x, new_y])

    return max(list(itertools.chain.from_iterable(depth)))

def main():
    H, W = list(map(int, input().split()))
    maze = [['

    for m in range(1,H+1):
        maze[m][1:W+1] = list(input())

    ans = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            depth = [[-1] * (W+2) for __ in range(H+2)]
            ans.append(bfs(i,j,maze,depth))

    print(max(ans))

main()

Solution (Python):

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

maze = []
maze.append(['
for i in range(h):
    row = [c for c in input()]
    row.insert(0, '
    row.append('
    maze.append(row)
maze.append(['

def search(item):
    x, y, dist = item
    ret = [
        (x+i,y+j, dist+1) for (i,j)
        in [(1,0), (-1,0), (0,1), (0,-1)]
        if maze[x+i][y+j] == '.'
    ]
    return ret

def bfs(fn, todo):
    seen = dict()
    for item in todo:
        x, y, d = item
        seen[(x, y)] = True    
    
    longest = 0
    while len(todo) > 0:
        
        
        
        item, todo = todo[0], todo[1:]
        x, y, dist = item
        if dist>longest:
            longest = dist

        for a in fn(item):
            x, y, dist = a
            if (x, y) in seen:
                continue
            seen[(x,y)] = True
            todo.append(a)

    return longest

def calc(x, y):
    return bfs(search, [(x, y, 0)])

longest_longest = 0

for i in range(1, h+1):
    for j in range(1, w+1):
        if maze[i][j] == "
            continue
        longest = calc(i, j)

        if longest_longest < longest:
            longest_longest = longest  

print(longest_longest)

Solution (Python):
from collections import deque


def dfs(maze, start):
    move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, start)])
    dist = [[-1] * w for _ in range(h)]

    depth, i, j = -1, -1, -1

    while q:
        depth, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = depth
        for di, dj in move:
            ni, nj = i + di, j + dj

            if (not 0 <= ni < h) or (not 0 <= nj < w):
                continue

            if maze[ni][nj] == "
                continue

            q.append((depth + 1, (ni, nj)))

    return depth, i, j


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

maze = []

for _ in range(h):
    maze.append(input())

answer = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == ".":
            depth, i, j = dfs(maze, (i, j))
            answer = max(answer, depth)

print(answer)

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

white=[]
for i in range(r):
    for j in range(c):
        if meiro[i][j]==".":
            white.append([i+1,j+1])

for i in range(r):
    meiro[i].insert(c,"
    meiro[i].insert(0,"
meiro.insert(0,["
meiro.append(["

def bfs(sx,sy):
    idou=[[0,1],[0,-1],[1,0],[-1,0]]
    tesuu=[[-1]*(c+2) for i in range(r+2)]
    from collections import deque
    tesuu[sx][sy]=0
    
    quest=deque([[sx,sy]])
    while len(quest)!=0:
        see=quest.popleft()
        for i in idou:
            if meiro[see[0]+i[0]][see[1]+i[1]]=="
                continue
            if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
                continue
            quest.append([see[0]+i[0],see[1]+i[1]])
            tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
    import itertools
    tesuu=list(itertools.chain.from_iterable(tesuu))
    return max(tesuu)
tesuu_=[]
for i in range(len(white)):
    tesuu_.append(bfs(white[i][0],white[i][1]))
print(max(tesuu_))

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

dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for i in range(H):
    for j in range(W):
        if M[i][j] == '
            continue
        stack = [[i, j]]
        cs = [[0 for i in range(W)] for i in range(H)]
        while stack:
            pos = stack.pop(0)
            cs[pos[0]][pos[1]] += 1
            for d in dir:
                npos = [pos[0] + d[0], pos[1] + d[1]]
                if 0 <= npos[0] < H and 0 <= npos[1] < W and cs[npos[0]][npos[1]] == 0 and M[npos[0]][npos[1]] == '.':
                    stack.append(npos)
                    cs[npos[0]][npos[1]] = cs[pos[0]][pos[1]]
                else:
                    ans = max(ans, cs[pos[0]][pos[1]])
print(ans - 1)

Solution (Python):
from collections import deque

INF = 1001001001
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
H, W = map(int, input().split())
S = [input() for _ in range(H)]

ans = 0

for si in range(H):   
    for sj in range(W):
        if S[si][sj] == '
            continue       
        q = deque([(si, sj)])
        dist = [[INF] * W for _ in range(H)]
        dist[si][sj] = 0
        while q:
            i, j = q.popleft()
            for d in range(4):
                ni = i + di[d]      
                nj = j + dj[d]
                if (ni < 0 or ni >= H or nj < 0 or nj >= W):
                    continue
                if S[ni][nj] == '
                    continue
                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:
                    ans = max(ans, dist[i][j])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

def bfs(x, y):
    s = [[False for i in range(W)] for j in range(H)]
        
    q = [(x, y, 0)]

    while q:
        a, b, c = q.pop(0)
        if S[a][b] == '
        s[a][b] = True
        
        if a+1 < H and S[a+1][b] == '.': q.append((a+1, b, c+1))
        if 0 <= a-1 and S[a-1][b] == '.': q.append((a-1, b, c+1))
        if b+1 < W and S[a][b+1] == '.': q.append((a, b+1, c+1))
        if 0 <= b-1 and S[a][b-1] == '.': q.append((a, b-1, c+1))
        
    return max(0, c-1)
    

if __name__ == '__main__':
    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):
            ans = max(ans, bfs(i, j))
            
    print(ans)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
grid = '
for _ in range(H):
    grid += '
grid += '
move = [1, -1, W+2, -W-2]

def bfs(start):
  lst = [10**9] *((H+2)*(W+2))
  lst[start] = 0
  q = deque([start])
  while q:
    x = q.popleft()
    dx = lst[x]
    for d in move:
      y = x + d
      if grid[y] == '
        continue
      dy = dx + 1
      if dy >= lst[y]:
        continue
      lst[y] = dy
      q.append(y)
  return max(x for x in lst if x < 10**9)
  
  
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '

Solution (Python):
from collections import deque
import sys

H, W = map(int, input().split())
grid = '
for _ in range(H):
    grid += '
grid += '
move = [1, -1, W+2, -W-2]

def bfs(start):
  lst = [10**9] *((H+2)*(W+2))
  lst[start] = 0
  q = deque([start])
  while q:
    x = q.popleft()
    dx = lst[x]
    for d in move:
      y = x + d
      if grid[y] == '
        continue
      dy = dx + 1
      if dy >= lst[y]:
        continue
      lst[y] = dy
      q.append(y)
  return max(x for x in lst if x < 10**9)
  
  
print(max(bfs(i) for i in range((H+2)*(W+2)) if grid[i] != '

Solution (Python):
def resolve():
    from collections import deque
    H, W = map(int, input().split())
    H += 2
    W += 2
    maze = '
    for _ in range(H-2):
        maze += '
    maze += '

    def bfs(root):
        if maze[root] == '
            return -1
        dist = [-1] * (H*W)
        dist[root] = 0
        q = deque([root])
        while q:
            x = q.popleft()
            for d in [1, -1, W, -W]:
                if maze[x+d] == '.' and dist[x+d] == -1:
                    q.append(x+d)
                    dist[x+d] = dist[x] + 1
        return max(dist)

    ans = max(bfs(i) for i in range(H*W))
    print(ans)
resolve()

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

def cost(x):
    v=[[0]*w for _ in range(h)]
    v[x[1]][x[0]]=1
    que = [x]
    ans=-1
    while que:
        newque = []
        for X,Y in que:
            for x,y in ((0,-1),(-1,0),(0,1),(1,0)):
                if 0<=X+x<w and 0<=Y+y<h and g[Y+y][X+x]=='.' and v[Y+y][X+x]==0:
                    v[Y+y][X+x] = 1
                    newque.append((X+x,Y+y))
        ans+=1
        que = newque
    return ans

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

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

def serch(S, x, y, next_temp):
  ans = []
  cand = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
  for pos in cand:
    a, b = pos
    if S[a][b] == "." and pos not in next_temp:
      ans.append(pos)
  return ans

def length(S, i, j):
  S[i][j] = 0
  temp = serch(S, i, j, [])
  counter = 0
  while len(temp) != 0:
    next_temp = []
    counter += 1
    for pos in temp:
      x, y = pos
      S[x][y] = counter
      next_temp += serch(S, x, y, next_temp)
    else:
      temp = next_temp
  return counter

import copy
max_l = 0
for i in range(1, h + 1):
  for j in range(1, w + 1):
    if S[i][j] == ".":
      T = copy.deepcopy(S)
      max_l = max(length(T, i, j), max_l)
print(max_l)

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

ans = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] == "
            continue

        dist = [[-1 for a in range(w)] for b in range(h)]
        dist[i][j] = 0

        q = collections.deque()
        q.append((i, j))
        while q:
            now = q.popleft()
            for x, y in [[0, 1], [0, -1], [-1, 0], [1, 0]]:
                if 0 <= now[0] + x <= h-1 and 0 <= now[1] + y <= w-1:
                    if grid[now[0]+x][now[1]+y] == "." and dist[now[0]+x][now[1]+y] == -1:
                        dist[now[0]+x][now[1]+y] = dist[now[0]][now[1]] + 1
                        q.append((now[0]+x, now[1]+y))

        temp = 0
        for k in range(h):
            temp = max(temp, max(dist[k]))
        ans = max(ans, temp)

print(ans)

Solution (Python):
from collections import deque

def bfs(maze,sy,sx):
    visited=[[-1 for _ in range(W+2)] for _ in range(H+2)]
    queue=deque([[sy,sx]])
    visited[sy][sx]=0
    dist=0
    
    while queue:
        y,x=queue.popleft()
        for j,k in ([1,0],[-1,0],[0,1],[0,-1]):
            new_y,new_x=y+j,x+k
            if maze[new_y][new_x]=="." and visited[new_y][new_x]==-1:
                visited[new_y][new_x]=visited[y][x]+1
                queue.append([new_y,new_x])
                dist=max(dist, visited[new_y][new_x])
    return(dist)
    
H,W=map(int,input().split())
maze=["
maze+=["
maze+=["

Ans=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if maze[i][j]==".":
            Ans=max(Ans, bfs(maze,i,j))
print(Ans)

Solution (Python):
"""
https://atcoder.jp/contests/abc151/tasks/abc151_d
"""
H, W = map(int, input().split())
S = []
for i in range(H):
    s = input()
    S.append(list(s))


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

def is_street(s, t):
    """
    道であること（壁ではないこと）を確認
    """
    return S[s][t] == '.'

def count(maze):
    """
    最大のコストを探索
    """
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  

    q = [[h, w]]
    while len(q) != 0:
        si, sj = q.pop(0)
        cost = m[si][sj]

        for i in range(4):
            ni = si + di[i]
            nj = sj + dj[i]
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if not is_street(ni, nj): 
                continue
            if m[ni][nj] != -1:
                continue

            m[ni][nj] = cost + 1
            q.append([ni, nj])

    max_cost = count(m)
    return max_cost

ans = -1

for i in range(H):
    for j in range(W):
        if not is_street(i, j):
            continue
        c = bfs(i, j)
        ans = max(ans, c)

print(ans)

Solution (Python):
"""
https://atcoder.jp/contests/abc151/tasks/abc151_d
"""
H, W = map(int, input().split())
S = []
for i in range(H):
    s = input()
    S.append(list(s))


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

def is_street(s, t):
    """
    道であること（壁ではないこと）を確認
    """
    return S[s][t] == '.'

def count(maze):
    """
    最大のコストを探索
    """
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  

    q = [[h, w]]
    while len(q) != 0:
        si, sj = q.pop(0)
        cost = m[si][sj]

        for i in range(4):
            ni = si + di[i]
            nj = sj + dj[i]
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if not is_street(ni, nj): 
                continue
            if m[ni][nj] != -1:
                continue

            m[ni][nj] = cost + 1
            q.append([ni, nj])

    max_cost = count(m)
    return max_cost

ans = -1

for i in range(H):
    for j in range(W):
        if not is_street(i, j):
            continue
        c = bfs(i, j)
        ans = max(ans, c)

print(ans)

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


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

def is_street(s, t):
    """
    道であること（壁ではないこと）を確認
    """
    return S[s][t] == '.'

def count(maze):
    """
    最大のコストを探索
    """
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  

    q = [[h, w]]
    while len(q) != 0:
        si, sj = q.pop(0)
        cost = m[si][sj]

        for i in range(4):
            ni = si + di[i]
            nj = sj + dj[i]
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if not is_street(ni, nj): 
                continue
            if m[ni][nj] != -1:
                continue

            m[ni][nj] = cost + 1
            q.append([ni, nj])

    max_cost = count(m)
    return max_cost

ans = -1

for i in range(H):
    for j in range(W):
        if not is_street(i, j):
            continue
        c = bfs(i, j)
        ans = max(ans, c)

print(ans)

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


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

def is_street(s, t):
    """
    道であること（壁ではないこと）を確認
    """
    return S[s][t] == '.'

def count(maze):
    """
    最大のコストを探索
    """
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  

    q = [[h, w]]
    while len(q) != 0:
        t, u = q.pop(0)
        cost = m[t][u]

        for i in range(4):
            ni = t + di[i]
            nj = u + dj[i]
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if not is_street(ni, nj): 
                continue
            if m[ni][nj] != -1:
                continue

            m[ni][nj] = cost + 1
            q.append([ni, nj])

    max_cost = count(m)
    return max_cost

ans = -1

for i in range(H):
    for j in range(W):
        if is_street(i, j):
            c = bfs(i, j)
            ans = max(ans, c)

print(ans)