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.



Sample input:
3 3
...
...
...


Sample output:
4

Submission status: Accepted

Solution code:
import queue

def bfs(start):
  d_mat = [[-1]*(w+2) for i in range(h+2)]
  q.put(start)
  d_mat[start[0]][start[1]] = 0
  while not q.empty():
    x, y = q.get()
    d = d_mat[x][y]
    if mat[x-1][y] == "." and d_mat[x-1][y] == -1:
      d_mat[x-1][y] = d+1
      q.put((x-1, y))
    
    if mat[x+1][y] == "." and d_mat[x+1][y] == -1:
      d_mat[x+1][y] = d+1
      q.put((x+1, y))
    
    if mat[x][y-1] == "." and d_mat[x][y-1] == -1:
      d_mat[x][y-1] = d+1
      q.put((x, y-1))
    
    if mat[x][y+1] == "." and d_mat[x][y+1] == -1:
      d_mat[x][y+1] = d+1
      q.put((x, y+1))
  return d_mat[x][y]
h, w = map(int, input().split())
mat = ["#"*(w+2)]
for y in range(h):
  mat.append("#"+input()+"#")
mat.append("#"*(w+2))

d_mat1 = [[-1]*(w+2) for i in range(h+2)]
d_mat2 = [[-1]*(w+2) for i in range(h+2)]
q = queue.Queue()
start_list = []
flag = True
for x in range(1, w+1):
  if flag:
    for y in range(1, h+1):
      if mat[y][x] == ".":
        start = (y, x)
        start_list.append(start)
        
q.put(start)

while not q.empty():
  x, y = q.get()
  d = d_mat1[x][y]
  if mat[x-1][y] == "." and d_mat1[x-1][y] == -1:
    d_mat1[x-1][y] = d+1
    q.put((x-1, y))
    
  if mat[x+1][y] == "." and d_mat1[x+1][y] == -1:
    d_mat1[x+1][y] = d+1
    q.put((x+1, y))
    
  if mat[x][y-1] == "." and d_mat1[x][y-1] == -1:
    d_mat1[x][y-1] = d+1
    q.put((x, y-1))
    
  if mat[x][y+1] == "." and d_mat1[x][y+1] == -1:
    d_mat1[x][y+1] = d+1
    q.put((x, y+1))



print(max(list(map(bfs, start_list))))

Submission status: Accepted

Solution code:
from collections import deque

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

start=[[j,i] for i in range(W) for j in range(H)]
res=0

for pt in start:
    v=[[0]*W for _ in range(H)]
    if S[pt[0]][pt[1]]=='#':
        continue
    q=deque([pt+[0]])
    dist=0

    while len(q)>0:
        h,w,cnt=q.popleft()
        
        if v[h][w]==1:
            continue
        else:
            v[h][w]=1

        dist=max(dist,cnt)

        for dh,dw in [[1,0],[-1,0],[0,1],[0,-1]]:
            nh=h+dh
            nw=w+dw
            if 0>nh or nh>=H or 0>nw or nw>=W or S[nh][nw]=='#':
                continue
            q.append([nh,nw,cnt+1])
    
    res=max(res,dist)

print(res)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
s = [0] * h
for i in range(h):
    s[i] = str(input())

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(w*h):
        for i in range(w*h):
            for j in range(w*h):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


d = [[float("inf")] * (h * w) for i in range((h * w))]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            a = i * w + j
            d[a][a] = 0
            for m, n in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                ss = i + m
                t = j + n
                if 0 <= ss <= h-1 and 0 <= t <= w-1 and s[ss][t] == '.':
                    b = ss * w + t
                    d[a][b] = 1
                    d[b][a] = 1
     #自身のところに行くコストは０
ans = 0
box = warshall_floyd(d)
for i in range(h * w):
    for j in range(h*w):
        if box[j][i] > 1000000:
            box[j][i] = 0
        ans = max(ans,box[j][i])

print(ans)

Submission status: Accepted

Solution code:
import heapq
H, W = map(int, input().split())
area = ['#']*(W+2)
for i in range(H):
    area += ['#']+list(input())+['#']
area += ['#']*(W+2)
H+=2
W+=2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='#': continue
        hq = []
        dist = [-1]*(H*W)
        dist[st] = 0
        heapq.heappush(hq, (0, st))
        while hq:
            cost, now = heapq.heappop(hq)
            for dx in move:
                nxt = now+dx
                if dist[nxt]>=0 or area[nxt]=='#': continue
                dist[nxt] = dist[now] + 1
                ans = max(ans, dist[nxt])
                heapq.heappush(hq, (dist[nxt], nxt))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
area = ['#']*(W+2)
for i in range(H):
    area += ['#']+list(input())+['#']
area += ['#']*(W+2)
H+=2
W+=2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='#': continue
        dq = deque([])
        dist = [-1]*(H*W)
        dq.append(st)
        dist[st] = 0
        while dq:
            now = dq.popleft()
            for dx in move:
                nxt = now+dx
                if dist[nxt]>=0 or area[nxt]=='#': continue
                dist[nxt] = dist[now]+1
                ans = max(ans, dist[nxt])
                dq.append(nxt)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import queue

INF = 10 ** 10

def solve(H: int, W: int, S: list):

    # right, bottom, left, top
    h_move = [0, 1, 0, -1]
    w_move = [1, 0, -1, 0]

    max_distance = 0
    for h_start in range(H):
        for w_start in range(W):
            if  S[h_start][w_start] != ".":
                continue
            distance = []
            for _ in range(H):
                l = [INF] * W
                distance.append(l)
            q = queue.Queue()
            q.put((h_start, w_start)) # スタート地点
            distance[h_start][w_start] = 0

            while not q.empty():
                h, w = q.get()
                for i in range(4):
                    h_next = h + h_move[i]
                    w_next = w + w_move[i]
                    # マップ外・壁・訪問済みを除外
                    if (h_next < 0 or h_next >= H or w_next < 0 or w_next >= W or S[h_next][w_next] != "." or distance[h_next][w_next] != INF):
                        continue
                    q.put((h_next, w_next))
                    distance[h_next][w_next] = min(distance[h][w] + 1, distance[h_next][w_next])
                    max_distance = max(max_distance, distance[h_next][w_next])

    print(max_distance)
    return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))
    W = int(next(tokens))
    S = [next(tokens) for _ in range(H)]
    solve(H, W, S)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import queue
import copy

INF = 10 ** 10

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

maze = [[-1] * (W+2)]
for _ in range(H):
    maze.append( [-1] + list( map(lambda c: INF if c == '.' else -1, input()) ) + [-1] )
maze.append([-1] * (W+2))

maze_backup = copy.deepcopy(maze)
maxpath = 0
for start_y in range(1, H+1):
    for start_x in range(1, W+1):
        if maze[start_y][start_x] == -1:
            continue
        

        bfs_q = queue.Queue()
        bfs_q.put( (start_y, start_x) )
        maze[start_y][start_x] = 0

        while not bfs_q.empty():
            y, x = bfs_q.get()
            for dy, dx in ((-1, 0), (1, 0), (0, 1), (0, -1)):
                if maze[y+dy][x+dx] > maze[y][x] + 1:
                    maze[y+dy][x+dx] = maze[y][x] + 1
                    bfs_q.put( (y+dy, x+dx) )

        maxpath = max(maxpath, max(max(row) for row in maze))
        maze = copy.deepcopy(maze_backup)

print(maxpath)

Submission status: Accepted

Solution code:
from collections import deque
def max_dis_from(xi,yi):
    d = deque([(xi,yi)])
    dis = [[-1]*(w+2) for i in range(h+2)]
    dis[yi][xi] = 0
    while d:
        x,y = d.popleft()
        for i in range(4):
            newy = y+dy[i]
            newx = x+dx[i]
            if maze[newy][newx] == "." and dis[newy][newx] == -1:
                d.append((newx,newy))
                dis[newy][newx] = dis[y][x] + 1
    return dis[y][x]   
h,w = map(int,input().split())
maze = []
maze.append(["#"]*(w+2))
for i in range(h):
    maze.append(["#"]+list(input())+["#"])
maze.append(["#"]*(w+2))
dx = [0,1,0,-1]
dy = [1,0,-1,0]
maxdis = 1
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j] == ".":
            maxdis = max(maxdis,max_dis_from(j,i))
print(maxdis)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
x = [''.join(["#"]*(w+2))]
s = x+["#"+input()+"#" for _ in range(h)]+x
ans = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        checked = [[False]*(w+2) for _ in range(h+2)]
        checked[i][j]=True
        stack=[[i,j]]
        stack_=[]
        count = 1
        while stack:
            pair=stack.pop()
            for x,y in [[1,0],[-1,0],[0,1],[0,-1]]:
                if s[pair[0]+x][pair[1]+y]=="." and checked[pair[0]+x][pair[1]+y] == False:
                    stack_.append([pair[0]+x,pair[1]+y])
                    checked[pair[0]+x][pair[1]+y] = True
            if stack==[]:
                stack = stack_.copy()
                stack_ = []
                count += 1

        ans = max(ans,count)
        
print(ans-2)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque 
INF = 100000
dir = ((1, 0), (-1, 0), (0, 1), (0, -1)) 
def main():
    H, W = map(int, readline().split())
    maze = []
    for _ in range(H):
        s = readline().rstrip().decode()
        maze.append(s) 
    
    
    def bfs(si, sj):
        dq = deque()
        dq.append((si, sj))        
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[si][sj] = 0
        while len(dq)>0:
            i, j = dq.popleft()
            for di, dj in dir:
                nxi = i+di
                nxj = j+dj
                if (nxi<0) or (nxj<0) or (nxi>=H) or (nxj>=W):
                    continue
                if maze[nxi][nxj] == '#':
                    continue
                if dist[nxi][nxj] != INF:
                    continue
                dist[nxi][nxj] = dist[i][j]+1
                dq.append((nxi, nxj))
        res = 0
        for i in range(H):
            for j in range(W):
                if dist[i][j] == INF:
                    continue
                res = max(dist[i][j], res)        
        return res

    ans = 0
    for si in range(H):
        for sj in range(W):
            if maze[si][sj] == '#':
                continue
            ans = max(bfs(si, sj), ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall


def next_locations(maze, H, W, i, j):
    if maze[i][j] == '#':
        return list()
    locations = list()
    if i - 1 >= 0 and maze[i - 1][j] == '.':
        locations.append((i - 1, j))
    if i + 1 < H and maze[i + 1][j] == '.':
        locations.append((i + 1, j))
    if j - 1 >= 0 and maze[i][j - 1] == '.':
        locations.append((i, j - 1))
    if j + 1 < W and maze[i][j + 1] == '.':
        locations.append((i, j + 1))
    return locations


def location_to_index(W, i, j):
    return W * i + j


def main():
    H, W = list(map(int, input().split(' ')))
    INF = H * W
    maze = list()
    for _ in range(H):
        maze.append(input())
    d = [[INF for _ in range(H * W)] for _ in range(H * W)]
    for i in range(H):
        for j in range(W):
            from_index = location_to_index(W, i, j)
            locs = next_locations(maze, H, W, i, j)
            for loc in locs:
                to_index = location_to_index(W, loc[0], loc[1])
                d[from_index][to_index] = 1 if from_index != to_index else 0
    d = csgraph_from_dense(d, null_value=INF)
    d = floyd_warshall(d)
    answer = 0
    for from_index in range(H * W):
        for to_index in range(H * W):
            dist = d[from_index][to_index]
            if dist == float('inf'):
                continue
            if dist > answer:
                answer = dist
    print(int(answer))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
ans = 0
def bfs(dist, s, queue):
    ret = 0
    while len(queue) > 0:
        y, x = queue.pop(0)
        for i, j in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
            h, w = y + i, x + j
            if 0 <= h < H and 0 <= w < W:
                if s[h][w] == "." and dist[h][w] == -1:
                    dist[h][w] = dist[y][x] + 1
                    queue.append([h, w])
    for i in range(H):
        ret = max(ret, max(dist[i]))
    return ret

for i in range(H):
    for j in range(W):
        if s[i][j] == ".":
            dist = [[-1] * W for _ in range(H)]
            dist[i][j] = 0
            queue = [(i, j)]
            ans = max(ans, bfs(dist, s, queue))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

inf = 10 ** 9

def bfs(si, sj, str_list, dist, h, w):
    q = deque([[si, sj]])
    dist[si][sj] = 0
    max_tmp = 0
    while len(q) != 0:
        i, j = q.popleft()
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ni = i + dx
            nj = j + dy
            if ni < 0 or ni >= h or nj < 0 or nj >= w:
                continue
            if str_list[ni][0][nj] != '.':
                continue
            if dist[ni][nj] != inf:
                continue
            dist[ni][nj] = dist[i][j] + 1
            q.append([ni, nj])
            max_tmp = max(max_tmp, dist[ni][nj])
    return max_tmp

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

    max_num = 0

    for si in range(h):
        for sj in range(w):
            if str_list[si][0][sj] != '.':
                continue
            dist = [[inf] * w for i in range(h)]
            bfs_result = bfs(si, sj, str_list, dist, h, w)
            max_num = max(max_num, bfs_result)

    print(max_num)  

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''ika tako
スタートが決められたとき、そこから最も遠いマスは、
幅優先探索で最後に訪れたマスとなる。
よって、道である各マスをスタート地点として全て試し、
最長移動距離の最大値が答え。
H,W  の上限が小さいので、スタート地点候補が最大400、
1回の探索で探索するマスが最大400、あわせて160000回に
比例する計算量で間に合う。
'''
from collections import deque
 
def bfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]
 
    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '#':
                continue
            if dist[ni][nj] != -1:
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j

h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            d, i, j = bfs(field, (i, j))
            ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
import sys
h,w = map(int,input().split())
S = [list(input()) for i in range(h)]
ans = 0

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

for i in range(h):
    for j in range(w):
        visit = [[0 for i in range(w)] for i in range(h)]
        pos = []
        if S[i][j] == '.':
            visit[i][j] = 1
            pos.append([i, j])
            while len(pos) > 0:
                now = pos.pop(0)
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if S[y][x] != '#' and visit[y][x] == 0:
                            visit[y][x] = visit[now[0]][now[1]] + 1
                            pos.append([y, x])
        for p in range(h):
            for q in range(w):
                ans = max(ans, visit[p][q])
                
print(ans - 1)

Submission status: Accepted

Solution code:
import sys
h,w = map(int,input().split())
S = [list(input()) for i in range(h)]
ans = []

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

for i in range(h):
    for j in range(w):
        visit = [[0 for i in range(w)] for i in range(h)]
        pos = []
        if S[i][j] == '.':
            visit[i][j] = 1
            d = 0
            pos.append([i, j, 0])
            while len(pos) > 0:
                now = pos.pop(0)
                d = now[2]
                for k in range(4):
                    y = now[0]+dy_dx[k][0]
                    x = now[1]+dy_dx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if S[y][x] != '#' and visit[y][x] == 0:
                            visit[y][x] = 1
                            pos.append([y, x, d + 1])
            ans.append(d)
                
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque


def BFS(x,y):
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[0 for _ in range(w)] for _ in range(h)]

    color[x][y]="gray"
    D[x][y]=0
    queue=deque([[x,y]])

    num=0
    while len(queue)>0:
        a,b=queue.popleft()
        for c,d in [[1,0],[-1,0],[0,1],[0,-1]]:
            X,Y=a+c,b+d
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]=="white" and S[X][Y]==".":
                    D[X][Y]=D[a][b]+1
                    num=max(num,D[X][Y])
                    color[X][Y]="gray"
                    queue.append([X,Y])
        color[a][b]="black"
    
    return num


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]==".":
            ans=max(ans,BFS(i,j))

print(ans)

Submission status: Accepted

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

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

def longest_BFS(h, w):
    ret = -1
    if S[h][w] == '#':
        return -1
    table = [[-1 for i in range(W)] for j in range(H)]
    table[h][w] = 0
    next_step = [[h, w]]
    while next_step:
        ret += 1
        step = next_step[:]
        next_step = []
        while step:
            u = step.pop()
            for i in range(4):
                if u[0]+dx[i] >= 0 and u[0]+dx[i] < H \
                    and u[1]+dy[i] >= 0 and u[1]+dy[i] < W \
                    and S[u[0]+dx[i]][u[1]+dy[i]] == '.' \
                    and table[u[0]+dx[i]][u[1]+dy[i]] == -1:
                    next_step += [[u[0]+dx[i], u[1]+dy[i]]]
                    table[u[0]+dx[i]][u[1]+dy[i]] = ret

    return ret

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, longest_BFS(h, w))
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
import sys
import queue
mok=queue.Queue()
s = [[str(c) for c in l.strip()] for l in sys.stdin]
dx=[1,0,-1,0]
dy=[0,1,0,-1]

maxx=0
for i in range(h):
  for j in range(w):
    d=[[-1]*w for k in range(h)]
    d[i][j]=0
    if s[i][j]=='.':
      mok.put([i,j])
      while not mok.empty():
        [nx,ny]=mok.get()
        for k in range(4):
          if 0<=nx+dx[k]<h and 0<=ny+dy[k]<w and s[nx+dx[k]][ny+dy[k]]=='.' and d[nx+dx[k]][ny+dy[k]]==-1:
            d[nx+dx[k]][ny+dy[k]]=d[nx][ny]+1
            if d[nx+dx[k]][ny+dy[k]]>maxx:
              maxx=d[nx+dx[k]][ny+dy[k]]
            mok.put([nx+dx[k],ny+dy[k]])

print(maxx)

Submission status: Accepted

Solution code:
from collections import deque
H,W = [int(x) for x in input().split()]
maze = []
for i in range(H):
    maze.append(list(input()))
#隣接リスト表記にする
#i行目j列目をi*W+jで表現
l = [[] for i in range(H*W)]
for i in range(H-1):
    for j in range(W-1):
        if maze[i][j] == "." and maze[i+1][j] == ".":
            l[j+W*i].append(j+W*(i+1))
            l[j+W*(i+1)].append(j+W*i)
        if maze[i][j] == "." and maze[i][j+1] == ".":
            l[j+W*i].append(j+W*i+1)
            l[j+W*i+1].append(j+W*i)
#右端を追加
for i in range(H-1):
    if maze[i][W-1] == "." and maze[i+1][W-1] == ".":
            l[W*i+W-1].append(W*i+2*W-1)
            l[W*i+2*W-1].append(W*i+W-1)
#下端を追加
for j in range(W-1):
    if maze[H-1][j] == "." and maze[H-1][j+1] == ".":
            l[j+W*(H-1)].append(W*(H-1)+j+1)
            l[j+W*(H-1)+1].append(j+W*(H-1))
#ここまでで隣接リスト表記できた
kosuu = H*W
ans = 0
for i in range(kosuu):
    dist = [-1]*kosuu
    d = deque()
    dist[i] = 0
    d.appendleft(i)
    while d:
        v = d.popleft()
        for j in l[v]:
            if dist[j] == -1:
                dist[j] = dist[v] + 1
                d.append(j)
    ans = max(ans,max(dist))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input()for _ in range(h)]
a=[[400]*w for _ in range(h)]
ans=0
def bfs(b,i,j):
    b[i][j]=0
    seen=[[0]*w for _ in range(h)]
    todo=deque([(i,j)])
    while len(todo)>0:
        x,y=todo.popleft()
        if seen[x][y]==1:
            continue
        seen[x][y]=1
        if x>0 and seen[x-1][y]==0 and s[x-1][y]=='.':
            b[x-1][y]=b[x][y]+1
            todo.append((x-1,y))
        if x>0 and s[x-1][y]=='#':
            seen[x-1][y]=1
        if x<h-1 and seen[x+1][y]==0 and s[x+1][y]=='.':
            b[x+1][y]=b[x][y]+1
            todo.append((x+1,y))
        if x<h-1 and s[x+1][y]=='#':
            seen[x+1][y]=1
        if y>0 and seen[x][y-1]==0 and s[x][y-1]=='.':
            b[x][y-1]=b[x][y]+1
            todo.append((x,y-1))
        if y>0 and s[x][y-1]=='#':
            seen[x][y-1]=1
        if y<w-1 and seen[x][y+1]==0 and s[x][y+1]=='.':
            b[x][y+1]=b[x][y]+1
            todo.append((x,y+1))
        if y<w-1 and s[x][y+1]=='#':
            seen[x][y+1]=1
    ret=0 
    for bi in b:
        for bij in bi:
            if bij<400:
                ret=max(ret,bij)
    #print(b)
    return ret

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

Submission status: Accepted

Solution code:
from collections import deque

def maze(h, w, sh, sw, list1):
    if list1[sh][sw]=="#":
        return 0
    flag = True
    for i in range(h):
        for j in range(w):
            if list1[i][j]=="#":
                flag=False
    if flag:
        return h+w-2
    
    que = deque()
    que.append([sh, sw, 0])
    list2 = list1.copy()
    direct = [(0,1), (0,-1), (1,0), (-1, 0)]
    count = 0
    while que:
        nh, nw, co = que.pop()
        count = co
        co +=1
        li=list(list2[nh])
        li[nw]="#"
        list2[nh]="".join(li)
        for i, j in direct:
            if nh+i<0 or nh+i>=h or nw+j<0 or nw+j>=w:
                pass
            elif list2[nh+i][nw+j]==".":
                que.appendleft([nh+i, nw+j, co])
    return count
        
h, w = (int(x) for x in input().split())
list1 = []
ans = 0
for i in range(h):
    list1.append(input())
for i in range(h):
    for j in range(w):
        ans_ij = maze(h, w, i, j , list1)
        if ans_ij>ans:
            ans=ans_ij
print(ans)

Submission status: Accepted

Solution code:
import queue

H,W = map(int, input().split())
S = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    tmp = input()
    S[i] = list(tmp)
dismax = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':continue
        gone = [[-1 for i in range(W)] for j in range(H)]
        gone[i][j] = 0
        dis = 0
        q = queue.Queue()
        q.put(i)
        q.put(j)
        while not q.empty():
            tmpi = q.get()
            tmpj = q.get()
            if tmpi - 1 >= 0 and gone[tmpi - 1][tmpj] == -1 and S[tmpi - 1][tmpj] == ".": 
                gone[tmpi - 1][tmpj] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi - 1][tmpj]: dis = gone[tmpi - 1][tmpj]
                q.put(tmpi - 1)
                q.put(tmpj)
            if tmpj - 1 >= 0 and gone[tmpi][tmpj - 1] == -1 and S[tmpi][tmpj - 1] == ".":
                gone[tmpi][tmpj - 1] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi][tmpj - 1]: dis = gone[tmpi][tmpj - 1]
                q.put(tmpi)
                q.put(tmpj - 1)
            if tmpi + 1 < H and gone[tmpi + 1][tmpj] == -1 and S[tmpi + 1][tmpj] == ".":
                gone[tmpi + 1][tmpj] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi + 1][tmpj]: dis = gone[tmpi + 1][tmpj]
                q.put(tmpi + 1)
                q.put(tmpj)
            if tmpj + 1 < W  and gone[tmpi][tmpj + 1] == -1 and S[tmpi][tmpj + 1] == ".":
                gone[tmpi][tmpj + 1] = gone[tmpi][tmpj] + 1
                if dis < gone[tmpi][tmpj + 1]: dis = gone[tmpi][tmpj + 1]
                q.put(tmpi)
                q.put(tmpj + 1)
        if dismax < dis: dismax = dis
print(dismax)

Submission status: Accepted

Solution code:
#bfs
import queue

h, w = map(int, input().split())
c = [list(input()) for i in range(h)]
visited = [[0 for i in range(w)] for j in range(h)]
q = queue.Queue()
ans = 0
            
dyx = [[0, 1], [1, 0], [-1, 0], [0, -1]]

for i in range(h):
    for j in range(w):
        if c[i][j] == '.':
            q.put([i, j])
            visited[i][j] = 1
            while not q.empty():
                now = q.get()
                for k in range(4):
                    y = now[0] + dyx[k][0]
                    x = now[1] + dyx[k][1]
                    if 0 <= y < h and 0 <= x < w:
                        if c[y][x] != '#' and visited[y][x] == 0:
                            visited[y][x] = visited[now[0]][now[1]] + 1
                            q.put([y, x])
        for l in range(h):
            for m in range(w):
                ans = max(ans, visited[l][m])
        queue = []
        visited = [[0 for i in range(w)] for j in range(h)]
print(ans-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from heapq import heappop, heappush

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

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

ans = 0
for h1 in range(h):
    for w1 in range(w):
        D = [[False]*w for i in range(h)]
        Q = [(0, (h1, w1))]
        while Q:
            q = heappop(Q)
            qh, qw = q[1][0], q[1][1]
            if qh < 0 or qh >= h or qw < 0 or qw >= w:
                continue
            if map_list[qh][qw] == "#":
                continue
            if D[qh][qw]:
                continue
            D[qh][qw] = True
            ans = max(q[0], ans)
            heappush(Q, (q[0]+1, (qh+1, qw)))
            heappush(Q, (q[0]+1, (qh-1, qw)))
            heappush(Q, (q[0]+1, (qh, qw+1)))
            heappush(Q, (q[0]+1, (qh, qw-1)))
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def check(ny, nx, sS):
    if 0<=ny<H and 0<=nx<W:
        if sS[ny][nx]=='.':
            return True
    else:
        return False

def bfs(sy, sx, sS):
    deq = deque()
    deq.append([(sy-1, sx-1)]) # insert indices
    sS[sy-1][sx-1] = '#'
    ddy = [-1, 0, 1, 0]
    ddx = [0, -1, 0, 1]
    step = 0
    while deq[0]:
        #print('deq', deq)
        nqueue = []
        cqueue = deq.popleft()
        for val in cqueue:
            y, x = val
            for dy, dx in zip(ddy, ddx):
                ny, nx = y+dy, x+dx
                if check(ny, nx, sS):
                    sS[ny][nx] = '#'
                    nqueue.append((ny, nx))
        deq.append(nqueue)
        if not(deq[0]):
            break
        step += 1
    return step

res = 0
for i in range(H):
    for j in range(W):
        #print('i, j:', i, j)
        if S[i][j] == '.':
            sS = deepcopy(S)
            val = bfs(i+1, j+1, sS)
            res = max(res, val)

print(res)

Submission status: Accepted

Solution code:
from collections import deque

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

# print(C)


def bfs(C, visited_list, que):
    _max_move_num = 0
    while len(que) > 0:
        h, w, d = que.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + j
            new_w = w + k
            if (new_h >= H or new_w >= W or new_w < 0 or new_h < 0):
                continue
            if (C[new_h][new_w] != '#' and visited_list[new_h][new_w] == 0):
                new_d = d + 1
                # print('探索', new_h, new_w, new_d)
                if (_max_move_num < new_d):
                    _max_move_num = new_d
                visited_list[new_h][new_w] = 1
                que.append((new_h, new_w, new_d))

    # print(_max_move_num)
    return(_max_move_num)


max_move_num = 0
for h in range(H):
    for w in range(W):
        if (C[h][w] == '.'):
            start_h, start_w = h, w
            # print(start_h, start_w)
            que = deque([(start_h, start_w, 0)])
            visited_list = [[0]*W for _ in range(H)]
            visited_list[start_h][start_w] = 1
            max_move_num_ = bfs(C, visited_list, que)
            # print('=================')
            if(max_move_num_ > max_move_num):
                max_move_num = max_move_num_

print(max_move_num)