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

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

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

ans = 0

#startを順に探索
for y in range(h):
    for x in range(w):
    
        i = 0
        move = [[-1] * w for _ in range(h)]
        #壁はスキップ
        if(maze[y][x] == '#'):
            continue

        #幅優先探索
        q = queue.Queue()
        q.put([x, y])
        move[y][x] = 0

        while not q.empty():
            pos = q.get()
            for i in range(4):
                next = [pos[0] + dx[i], pos[1] + dy[i]]

                #端
                if(next[0] == w or next[1] == h or next[0] < 0 or next[1] < 0):
                    continue

                if(maze[next[1]][next[0]] == '.' and move[next[1]][next[0]] == -1):
                    move[next[1]][next[0]] = move[pos[1]][pos[0]] + 1
                    q.put(next)
        ans = max([ans] + [max(v) for v in move])

print(ans)

Submission status: Accepted

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

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

inf = float('inf')

import queue

ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w] != '#':
            q = queue.Queue()
            d = [[inf for _ in range(W)] for _ in range(H)]
            # 距離を保存
            q.put([h, w])
            d[h][w] = 0
            # スタートをキューに、距離を0に
            while not q.empty():
                p = q.get()
                # if p == g:
                #     break
                for i in range(4):
                    nx = p[1] + dx[i]
                    ny = p[0] + dy[i]
                    if nx >= 0 and nx < W and ny >= 0 and ny < H and S[ny][nx] != '#' and d[ny][nx] == inf:
                        q.put([ny, nx])
                        d[ny][nx] = d[p[0]][p[1]] + 1
            for hh in range(H):
                for ww in range(W):
                    if d[hh][ww] != inf:
                        ans = max(ans, d[hh][ww])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
S=[input() for _ in range(h)]
inf=float("inf")
ans=0

for i in range(h):
    for j in range(w):
        if S[i][j]=="#":
            continue
        else:
            dist=[[inf for _ in range(w)] for _ in range(h)]
            dist[i][j]=0
            queue=deque([(i,j)])
            while queue:
                si,sj=queue.popleft()
                for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                    if 0<=ni<=h-1 and 0<=nj<=w-1 and S[ni][nj] != "#":
                        if dist[ni][nj] > dist[si][sj] + 1:
                            dist[ni][nj] = dist[si][sj] + 1
                            queue.append((ni, nj))
                max_dist = 0
                for ii in range(h):
                    for jj in range(w):
                        if dist[ii][jj] != inf:
                            max_dist = max(max_dist, dist[ii][jj])
                            ans = max(max_dist,ans)
print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))

Submission status: Accepted

Solution code:

from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))

Submission status: Accepted

Solution code:

from collections import deque
def check(x,y):
    if 0<=x and x<h:
        if 0<=y and y<w:
            return True
    return False

count=0
def bfs():
    while (q):
        x,y,count=q.popleft()
        
        if check(x,y)==False or (x,y) in finished or c[x][y]=='#':
            continue

        else:
            q.append([x,y-1,count+1])
            q.append([x,y+1,count+1])
            q.append([x+1,y,count+1])
            q.append([x-1,y,count+1])
            finished.add((x,y))
            bfscount.append(count)

    return max(bfscount)

q = deque()
h,w=map(int,input().split())
global finished 
finished = set()
c=[]
for i in range(h):
    c.append(list(map(str,input())))
ans=[]
bfscount=[]
for i in range(h):
    for j in range(w):
        if c[i][j]==".":
            q.append([i,j,0])
            ans.append(bfs())
            finished = set()
            bfscount=[]
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]

def bfs():
    global goal
    #0はstartとまだ通ってない場所
    d=[[float('inf')]*w for _ in range(h)]
    d[st[0]][st[1]]=0
    #進行方向
    x=[0,1,0,-1]
    y=[1,0,-1,0]

    p=deque([])
    p.append(st)#start座標を入れる

    while p:
        zahyo=p.popleft()
        for i in range(4):
            nx=zahyo[0]+x[i]
            ny=zahyo[1]+y[i]

            if 0<=nx<=h-1 and 0<=ny<=w-1 and d[nx][ny]==float('inf') and maze[nx][ny]=='.':
                d[nx][ny]=d[zahyo[0]][zahyo[1]]+1
                p.append([nx,ny])
                if goal<d[nx][ny]:
                    goal=d[nx][ny]

goal=0
ans=0
#starを決める
for i in range(h):
    for j in range(w):
        if maze[i][j]=='.':
            st=[i,j]
            bfs()
            if ans<goal:
                ans=goal
print(ans)

Submission status: Accepted

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

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


def bfs(sy, sx):
    if s[sy][sx] == '#':
        return -1
    # 未探索ステータス-1で初期化しておく
    dist = [[-1] * w for _ in range(h)]
    dist[sy][sx] = 0
    dq = deque()
    dq.append((sy, sx))
    while dq:
        y, x = dq.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if s[ny][nx] == '#' or dist[ny][nx] != -1:
                    continue
                dist[ny][nx] = dist[y][x] + 1
                dq.append((ny, nx))
    return np.array(dist).max()


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

Submission status: Accepted

Solution code:
from collections import deque


def BFS(x,y):
    color=[["white" for i in range(w+2)] for j in range(h+2)]
    D=[[-1 for i in range(w+2)] for j in range(h+2)]

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

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


h,w=map(int,input().split())
S=[["#"]+list(input())+["#"] for i in range(h)]
S.insert(0,["#"]*(w+2))
S.append(["#"]*(w+2))

ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if S[i][j]!="#":
            ans=max(ans,BFS(i,j))

print(ans)

Submission status: Accepted

Solution code:
import copy
import sys
from collections import deque
H,W = (int(_) for _ in input().split())  
f_tmp = []
for _ in range(H):
    f_tmp.append(list(input()))
dp = [[0] * (W+1) for i in range(H+1)]
#dにスタート位置を入力する
d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
max_root = 0
for s_i in range(H):
    for s_j in range(W):
        f = copy.deepcopy(f_tmp)
        if f[s_i][s_j] != '#':
            q = deque()
            q.append([s_i,s_j,0])
            flg = False
            while len(q)>0:
                #print(f)
                #print(q)
                node = q.popleft()
                if node is not None:
                    y = node[0]
                    x = node[1]
                    z = node[2]
                    f[y][x] = '#'
                    for dx, dy in d:
                        nx, ny = x + dx, y + dy
                        if not (0 <= nx < W and 0 <= ny < H) or f[ny][nx] == '#':
                            #print("NG")
                            continue
                        else:
                            tmp = [ny,nx,z+1]
                            if f[ny][nx] != 'y':
                                q.append(tmp)
                            if f[ny][nx] == 'g' and flg == False:
                                flg = True
                                if max_root < z+1:
                                    max_root = z+1
                            f[ny][nx] = 'y'
                            
                            if max_root < z+1:
                                max_root =z+1
print(max_root)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype='int')
#T=[]
S=np.zeros_like(T,dtype='int') 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype='int')
        
print(d-1)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
 
 
H,W= [int(x) for x in input().split()]
n=[]
T=np.zeros((H,W),dtype=int)
#T=[]
S=np.zeros_like(T,dtype=int) 
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#B=T.copy()    
d=0
c=deque()  
for i in range(H):
    for j in range(W):
         
        if T[i][j] ==1:continue
 
          
        c.append((i,j))
        S[i][j] = 1
        #c.append(j)
        
        #t=len(c)
        while True:

                try:
                  m,n = c.popleft()
                except IndexError: break
                
                
                for kk in [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]:
                  if not (0<=kk[0]<H and 0<= kk[1] <W): continue
                  if T[kk]==1:continue
                  if S[kk] == 0:
                    c.append(kk)
                    S[kk] = S[m][n]+1        
                        
 
        #print(T)
        d = max(d,np.max(S))
        S=np.zeros_like(T,dtype=int)
        
print(d-1)

Submission status: Accepted

Solution code:
import collections

h, w = map(int, input().split())
s = [[""]*(w+2)]
for _ in range(h):
    _s = list(input())
    _s.insert(0, "")
    _s.append("")
    s.append(_s)
s.append([""]*(w+2))

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

ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if s[i][j] == "#":
            continue

        q = collections.deque([[i, j]])

        f = [[-1]*(w+2) for _ in range(h+2)]
        f[i][j] += 1

        while 0 < len(q):
            _x, _y = q.pop()
            for _dx, _dy in zip(dx, dy):
                x = _x + _dx
                y = _y + _dy
                if s[x][y] == "." and f[x][y] == -1:
                    f[x][y] = f[_x][_y] + 1
                    q.appendleft([x, y])

        for _f in f:
            ans = max(ans, max(_f))

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

hw = list(map(int, input().split()))
field = [list(input()) for l in range(hw[0])]
ans = 0

#下右上左
direction = [[1, 0], [0, 1], [-1, 0], [0, -1]]

for i in range(hw[0]):
    for j in range(hw[1]):
        #そもそもスタートposが#だったらその時点で終わり
        if field[i][j] == "#":
            continue
        
        #距離マップを準備
        costmap = [[-1] * hw[1] for k in range(hw[0])]
        costmap[i][j] = 0
        
        #キューを準備
        que = deque([[i, j]])
        
        while len(que) > 0:
            #キューから取り出す
            nh, nw = que.popleft()

            #方向を決める        
            for dh, dw in direction:

                #行った先判定
                #はみ出してないか？
                if dh + nh > hw[0] - 1:
                    continue
                if dh + nh < 0:
                    continue
                if dw + nw > hw[1] - 1:
                    continue
                if dw + nw < 0:
                    continue 

                #壁じゃないか？
                if field[nh + dh][nw + dw] == "#":
                    continue

                #探索済みじゃないか？
                if costmap[nh + dh][nw + dw] != -1:
                    continue

                #コストを書き込む
                costmap[nh + dh][nw + dw] = costmap[nh][nw] + 1

                #書き込んだ行をキューに入れる
                que.append([nh + dh, nw + dw])
        ans = max(ans, max([max(d) for d in costmap]))
print(ans)

Submission status: Accepted

Solution code:
import queue

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

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

ans = 0

for i in range(h) :
    for j in range(w) :
        if s[i][j] == '#' :
            continue
        dist = [[-1 for i in range(w)] for j in range(h)]
        q = queue.Queue()
        q.put([j,i])
        dist[i][j] = 0
        cnt = 0
        while not q.empty() :
            xy = q.get()
            for k in range(4) :
                x = xy[0] + dx[k]
                y = xy[1] + dy[k]
                if y < 0 or y >= h or x < 0 or x >= w :
                    continue
                if s[y][x] == '#' :
                    continue
                if dist[y][x] != -1 :
                    continue
                q.put([x, y])
                dist[y][x] = dist[xy[1]][xy[0]] + 1
        for k in range(h) :
            for l in range(w) :
                ans = max(ans, dist[k][l])


print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#abc151_d
import sys
from collections import deque
mv = ((1,0),(-1,0),(0,1),(0,-1))
h,w = map(int,input().split())
board = [["#"]*(w+2) for _ in range(h+2)]
for i in range(h):
    s = input()
    for j in range(w):
        board[i+1][j+1] = str(s[j])
cur_max = 0 # 初期点を変更しながら全探索した時のmax
#print(board[0][0] == ".")
#for i in range(h+2):
    #print(board[i])
for i in range(h+2):
    for j in range(w+2):
        #print(i,j,board[i][j])
        tmp =  board[i][j]
        if tmp == ".":
            #print("yes",i,j)
            visit = deque()
            start_pos = (i,j)
            visit.append(start_pos)
            cnt = [[-1]*(w+2) for _ in range(h+2)] # -1埋め
            cnt[i][j] = 0 #スタート地点は0
            while visit:
                point = visit.popleft()
                #print(point[0], point[1])
                for k in mv:
                    pos = (point[0]+k[0],point[1]+k[1])
                    #print(pos)
                    if str(board[pos[0]][pos[1]]) == ".":
                        if cnt[pos[0]][pos[1]] == -1: #unvisited
                            #print(i,j,"yes")
                            cnt[pos[0]][pos[1]] = cnt[point[0]][point[1]] + 1
                            visit.append((pos[0],pos[1]))
                            if cnt[pos[0]][pos[1]] > cur_max:
                                cur_max = cnt[pos[0]][pos[1]]
print(cur_max)

Submission status: Accepted

Solution code:
#python3
from collections import deque
INF = int(1e9)
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

    ans = -1
    for si in range(h):
        for sj in range(w):
            if maze[si][sj] == '#':
                continue
            
            dist = [[INF for _ in range(w)] for _ in range(h)]
            Q = deque()
            Q.append((si, sj))
            dist[si][sj] = 0
            while len(Q) > 0:
                pi, pj = Q.popleft()

                for di, dj in d:
                    x = pi + di
                    y = pj + dj
                    if (x < 0) | (y < 0) | (x >= h) | (y >= w):
                        continue
                    if maze[x][y] == '#':
                        continue 
                    if dist[x][y] != INF:
                        continue

                    Q.append((x, y))
                    dist[x][y] = dist[pi][pj] + 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()

Submission status: Accepted

Solution code:
from collections import deque

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

def bfs(x,y):
  d = deque()
  d.append([x,y,0])
  visited = [[False for i in range(W)] for j in range(H)]
  will_search = [[False for i in range(W)] for j in range(H)]
  maxd = -1
  while len(d) > 0:
    x,y,w = d.popleft()
    visited[x][y] = True
    next_point = []
    for dx,dy in [[1,0], [-1,0], [0,-1], [0,1]]:
      if 0 <= x + dx and x + dx < H and 0 <= y + dy and y + dy < W and S[x+dx][y+dy] == ".":
        next_point.append([x + dx, y + dy])
    for p, q in next_point:
      if visited[p][q]:
        continue
      if will_search[p][q]:
        continue
      d.append([p,q,w+1])
      will_search[p][q] = True
      maxd = max(maxd, w+1)

  return maxd

ans = -1
for X in range(H):
  for Y in range(W):
    if S[X][Y] == "#":
      continue
    ans = max(bfs(X,Y), ans)
    
print(ans)

Submission status: Accepted

Solution code:
row,col=map(int,input().split())
maze=[list(input()) for _ in range(row)]
result = []
 
def create_next_adj_list(point):
  cur_x, cur_y, cur_depth = point
  return [(cur_x, cur_y+1, cur_depth+1), (cur_x+1, cur_y, cur_depth+1), (cur_x, cur_y-1, cur_depth+1), (cur_x-1, cur_y, cur_depth+1)]
 
for r in range(row):
  for c in range(col):
    if maze[r][c] == '.':
 
      visited = [ [0]*col for _ in range(row)]
      visited[r][c] = -1
    
      adj_list = [(r, c+1, 0), (r+1, c, 0), (r, c-1, 0), (r-1, c, 0)]

      while adj_list:
        point = adj_list.pop(0)

        if 0<=point[0]<row and 0<=point[1]<col and visited[point[0]][point[1]] != -1:
          visited[point[0]][point[1]] = -1
          if maze[point[0]][point[1]] != '#':
            for adj in create_next_adj_list(point):
              adj_list.append(adj)

      result.append(point[-1])

print(max(result))

Submission status: Accepted

Solution code:
import bisect
import math
from queue import Queue
import sys
from copy import copy, deepcopy
from collections import defaultdict, Counter, deque
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

inf = float("inf")


def main():

    H, W = map(int, readline().split())
    S = [[s for s in input()] for h in range(H)]
    
    ret = 0
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                tmp_ret = 0
                maze = deepcopy(S)
                maze[h][w] = tmp_ret
                
                q1 = Queue()
                q1.put((h, w))
                
                q2 = Queue()
                
                while not (q1.empty() and q2.empty()):
                    while not q1.empty():
                        h, w = q1.get()
                        for dh, dw in delta:
                            if h + dh < H and h + dh >= 0 \
                            and w + dw < W and w + dw >= 0 \
                            and maze[h + dh][w + dw] == '.':
                                maze[h + dh][w + dw] = '#'
                                q2.put((h + dh, w + dw))

                    if not q2.empty():
                        q1 = q2
                        q2 = Queue()
                        tmp_ret += 1
                        
                ret = max(ret, tmp_ret)
    
    print(ret)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import math
from queue import Queue
import sys
from copy import copy, deepcopy
from collections import defaultdict, Counter, deque
from itertools import combinations, permutations
from heapq import heapify, heappop, heappush

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 


inf = float("inf")

def main():

    H, W = map(int, readline().split())
    S = [[s for s in input()] for h in range(H)]
    
    ret = 0
    
    delta = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    
    
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                tmp_ret = 0
                maze = deepcopy(S)
                maze[h][w] = tmp_ret
                
                q1 = Queue()
                q1.put((h, w))
                
                q2 = Queue()
                
                while not (q1.empty() and q2.empty()):
                    while not q1.empty():
                        h, w = q1.get()
                        for dh, dw in delta:
                            if h + dh < H and h + dh >= 0 \
                            and w + dw < W and w + dw >= 0 \
                            and maze[h + dh][w + dw] == '.':
                                maze[h + dh][w + dw] = tmp_ret
                                q2.put((h + dh, w + dw))

                    if not q2.empty():
                        q1 = q2
                        q2 = Queue()
                        tmp_ret += 1
                        
                ret = max(ret, tmp_ret)
    
    print(ret)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
MAZE=[list(input()) for _ in range(H)]

d=((-1,0),(0,-1),(1,0),(0,1))
ans_l=set()

def search(pos):
    D=[[0]*W for _ in range(H)]
    while len(pos)>0:
        x,y,depth=pos.popleft()
        D[x][y]=-1
        for i in range(4):
            nx=x+d[i][0]
            ny=y+d[i][1]
            if 0<=nx<H and 0<=ny<W and MAZE[nx][ny]=='.' and D[nx][ny]!=-1:
                pos.append((nx,ny,depth+1))
                D[nx][ny]=-1
    return depth

for i in range(H):
    for j in range(W):
        if MAZE[i][j]=='.':
            p=deque([[i,j,0]])
            ans_l.add(search(p))

print(max(ans_l))

Submission status: Accepted

Solution code:
INF = 1001001001
from collections import deque
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)])
        d = [[INF] * W for _ in range(H)]
        d[si][sj] = 0
        while q:
            i, j = q.popleft()
            for dir in range(4):
                ni = i + di[dir]
                nj = j + dj[dir]
                if (ni<0 or ni>=H or nj<0 or nj>=W): continue
                if S[ni][nj] == '#': continue
                if d[ni][nj] == INF:
                    d[ni][nj] = d[i][j] + 1
                    q.append((ni,nj))
        tmp = 0
        for i in range(H):
            for j in range(W):
                if d[i][j] != INF:
                    tmp = max(tmp, d[i][j])
        ans = max(ans, tmp)
print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
maze = []
for i in range(n):
  l = input()
  dl = []
  for j in range(m):
    if l[j] == '.':
      dl.append(0)
    else:
      dl.append(1)
  maze.append(dl)
ans = 0
for i in range(n):
  for j in range(m):
    if maze[i][j] == 0:
      a = [list(l) for l in maze]
      a[i][j] = 1
      q = [(i, j)]
      d = 0
      while len(q) > 0:
        nq = []
        for x, y in q:
          if x > 0 and a[x - 1][y] == 0:
            a[x - 1][y] = 1
            nq.append((x - 1, y))
          if y > 0 and a[x][y - 1] == 0:
            a[x][y - 1] = 1
            nq.append((x, y - 1))
          if x < n - 1 and a[x + 1][y] == 0:
            a[x + 1][y] = 1
            nq.append((x + 1, y))
          if y < m - 1 and a[x][y + 1] == 0:
            a[x][y + 1] = 1
            nq.append((x, y + 1))
        if len(nq) > 0:
          d += 1
        q = nq
      ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

[H, W] = [int(i) for i in input().split()]
S = [list(input()) for _ in range(H)]
dy, dx = [1, 0, -1, 0], [0, 1, 0, -1]

def bfs(sy, sx):
    if S[sy][sx] == '#':
        return 0
        
    reached = [[-1]*W for _ in range(H)]
    que = deque([[sy, sx]])
    reached[sy][sx] = 0
    
    while que:
        [y, x] = que.pop()
        for i in range(4):
            yy, xx = y + dy[i], x + dx[i]
            if yy < 0 or xx < 0 or yy > H-1 or xx > W-1 or S[yy][xx] == '#' or reached[yy][xx] != -1:
                continue
            else:
                reached[yy][xx] = reached[y][x] + 1
                que.appendleft([yy, xx])
                
    distance = 0
    for i in range(H):
        for j in range(W):
            distance = max(distance, reached[i][j])
            
    return distance

ans = 0
for a in range(H):
    for b in range(W):
        ans = max(ans, bfs(a, b))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
import copy

def bfs(maze, sy, sx, H, W):
    queue = deque([[sy, sx]])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = 0
    di = [-1, 0, 1, 0]
    dj = [0, -1, 0, 1]
    while queue:
        y, x = queue.popleft()
        for dir in range(4):
            new_y, new_x = y+di[dir], x+dj[dir]
            if new_x >= W or new_y >= H:
                pass
            elif new_x < 0 or new_y < 0:
                pass
            elif 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])
    return visited

H, W = map(int, input().split())
MAZE = [input() for _ in range(H)]
ans = 0
tmp = 0
for i in range(H):
    for j in range(W):
        if MAZE[i][j] == "#":
            continue
        tmp = np.max(bfs(MAZE, i, j, H, W))
        ans = max(ans, tmp)
print(ans)