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:
#関数を持ってくる
from collections import deque

#入力(座標をリストで扱いやすいように-1する)
r,c = map(int,input().split())
c_list = [list(input()) for nesya in range(r)]
for hoge in c_list:
  hoge.insert(0,'#')
  hoge.append('#')
c_list.insert(0,['#']*(c+2))
c_list.append(['#']*(c+2))

ans = 0
for j in range(r+2):
  for i in range(c+2):
    #dequeオブジェクトを作る
    d = deque()
    #その座標を扱ったかを調べるためのリストを作る
    hoge_list = [[-1]*(c+2) for motsu in range(r+2)]
    if  c_list[j][i] == '#':
      continue
    else:
      #スタート位置をdに加え、到達時刻を0にする
      d.append((j,i))
      hoge_list[j][i] = 0

      #当該の座標から動かすためのリストを作る
      move =[[1,0],[-1,0],[0,1],[0,-1]]

      #座標に対して作業する
      while len(d) > 0:
        #今から扱う座標をcoordとする
        coord = d.popleft()
  
        #縦横に移動したときそれぞれのマスに作業する
        for k in range(4):
          #移動した後の座標
          x = coord[1] + move[k][1]
          y = coord[0] + move[k][0]
    
          #作業が終わっている座標であったら無視する
          if hoge_list[y][x] != -1:
            pass
          #マスが壁であった場合-2を代入して終わる
          elif c_list[y][x] == '#':
            hoge_list[y][x] = -2
          #作業するマス
          else:
            #当該座標から1移動したはずである
            hoge_list[y][x] = hoge_list[coord[0]][coord[1]] + 1
            ans = max(hoge_list[y][x],ans)
            #dequeに加える
            d.append((y,x))
    

#ゴールの移動回数を出力する
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
G = [input() for i in range(h)]
directions = [(1,0),(0,1),(-1,0),(0,-1)]
ans = 0

for sx in range(w):
  for sy in range(h):
    if G[sy][sx] == "#":
      continue
      
    dist = [[-1] * w for i in range(h)]
    dist[sy][sx] = 0
    que = deque([[sy, sx]])
    
    while len(que):
      y,x = que.popleft()
      for dx,dy in directions:
        nx = x + dx
        ny = y+ dy
        if not (0<=nx<w and 0<=ny<h) or G[ny][nx]=="#":
          continue
        if dist[ny][nx] != -1:
          continue
      
        dist[ny][nx] = dist[y][x] +1
        que.append([ny,nx])
      
    ans = max(ans, max([max(d) for d in dist]))
    
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

def bfs(s_l, sy, sx, h, w):
    visited = [ [-1]*w for i in range(h)]
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    last_dist = -1
    while q:
        y, x = q.popleft()
        # if [y, x] == [gy, gx]:
        #     return visited[gy][gx]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y, n_x = y+j, x+k
            if n_y >= h or n_x >= w or n_y < 0 or n_x < 0:
                continue
            if s_l[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x] + 1
                last_dist = visited[n_y][n_x]
                q.append([n_y,n_x])
    return last_dist

def main():
    h, w = map(int, input().split()) 
    s_l = []
    all_dot_cnt = 0
    for i in range(h):
        row = list(input())
        s_l.append(row)
        all_dot_cnt += row.count('.')
    
    curr_ans = -1
    visited = [ [-1]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if s_l[i][j] == '.':
                res = bfs(s_l, i, j, h, w)
                if res > curr_ans:
                    curr_ans = res
    print(curr_ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(s_l, sy, sx, h, w):
    visited = [ [-1]*w for i in range(h)]
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    last_dist = -1
    while q:
        y, x = q.popleft()
        # if [y, x] == [gy, gx]:
        #     return visited[gy][gx]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y, n_x = y+j, x+k
            if n_y >= h or n_x >= w or n_y < 0 or n_x < 0:
                continue
            if s_l[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x] + 1
                last_dist = visited[n_y][n_x]
                q.append([n_y,n_x])
    return last_dist

def main():
    h, w = map(int, input().split()) 
    s_l = []
    all_dot_cnt = 0
    for i in range(h):
        row = list(input())
        s_l.append(row)
        all_dot_cnt += row.count('.')
    
    curr_ans = -1
    visited = [ [-1]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if s_l[i][j] == '.':
                res = bfs(s_l, i, j, h, w)
                if res > curr_ans:
                    curr_ans = res
    print(curr_ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
for i in range(H):
    maze.append(input())
nl = [(1,0), (0,1), (-1,0),(0,-1)]
ans = 0

def bfs(sy,sx):
    dist = [[-1]*W for _ in range(H)]
    q = deque([])
    q.append((sy,sx))
    dist[sy][sx] = 0
    maxd = 0
    while len(q)>0:
        cy, cx = q.popleft()
        for ny, nx in nl:
            ny += cy
            nx += cx
            if (0 <= ny < H) and (0 <= nx < W):
                if dist[ny][nx] == -1 and maze[ny][nx] == ".":
                    q.append((ny,nx))
                    dist[ny][nx] = dist[cy][cx] +1
                    if maxd < dist[ny][nx]:
                        maxd = dist[ny][nx]
    return maxd

for i in range(H):
    for j in range(W):
        if maze[i][j] == ".":
            maxn = bfs(i,j)
            if maxn > ans:
                ans = maxn
print(ans)

Submission status: Accepted

Solution code:
import collections

INF = 10 ** 5

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W = ZZ()
    Maze = [input() for _ in range(H)]
    D = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    def bfs(sx, sy):
        dist = [[INF] * W for _ in range(H)]
        dist[sx][sy] = 0
        deq = collections.deque()
        deq.append([sx, sy])
        while deq:
            v = deq.popleft()
            for dx, dy in D:
                nx, ny = v[0]+dx, v[1]+dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == INF and Maze[nx][ny] == '.':
                    dist[nx][ny] = dist[v[0]][v[1]] + 1
                    deq.append([nx, ny])
        return dist[v[0]][v[1]]

    max_d = -1

    for i in range(H):
        for j in range(W):
            if Maze[i][j] == '.': max_d = max(max_d, bfs(i, j))
    print(max_d)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def resolve():
    h, w = map(int, input().split())
    maze = [input() for _ in range(h)]
    from collections import deque
    def slv(maze, startx, starty):
        if maze[startx][starty] == "#":
            return 0
        else:
            visited = [[-1] * w for _ in range(h)]
            visited[startx][starty] = 0
            nxt = deque([[startx, starty]])
            while len(nxt) != 0:
                a = nxt.popleft()
                x = a[0]
                y = a[1]
                for i, j in [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]:
                    if 0 <= i < h and 0 <= j < w:
                        if maze[i][j] == "." and visited[i][j] == -1:
                            visited[i][j] = visited[x][y] + 1
                            nxt.append([i,j])
            rtn = 0
            for i in range(h):
                rtn = max(rtn, max(visited[i]))
            return rtn

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

Submission status: Accepted

Solution code:
from collections import deque
import copy
H, W = map(int, input().split())
field = []
for i in range(H):
    field.append(list(input()))
f = copy.deepcopy(field)

def BFS(x, y, field):
    cnt = [[0 for _ in range(W)] for _ in range(H)]
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()
        if(field[x][y] == "#"):
            continue        
            
        field[x][y] = "#"
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nx = x + dx
            ny = y + dy
            if(nx < 0 or nx >= H or ny < 0 or ny >= W):
                continue
            queue.append((nx, ny))
            if(field[nx][ny] != "#"):
                cnt[nx][ny] = cnt[x][y] + 1
    return cnt

ans = 0
for i in range(H):
    for j in range(W):
        if(field[i][j] == "#"):
            continue
        cnt = BFS(i, j, f)
        for k in range(len(cnt)):
            tmp = max(cnt[k])
            ans = max(ans, tmp)
        f = copy.deepcopy(field)
print(ans)

Submission status: Accepted

Solution code:
def resolve():
    h, w = map(int, input().split())
    maze = [input() for _ in range(h)]
    from collections import deque
    def slv(maze, startx, starty):
        if maze[startx][starty] == "#":
            return 0
        else:
            visited = [[-1] * w for _ in range(h)]
            visited[startx][starty] = 0
            nxt = deque([[startx, starty]])
            while len(nxt) != 0:
                a = nxt.popleft()
                x = a[0]
                y = a[1]
                if 0 <= (x + 1) < h and 0 <= y < w:
                    if maze[x + 1][y] == "." and visited[x + 1][y] == -1:
                        visited[x + 1][y] = visited[x][y] + 1
                        nxt.append([x + 1, y])
                if 0 <= x < h and 0 <= y - 1 < w:
                    if maze[x][y - 1] == "." and visited[x][y - 1] == -1:
                        visited[x][y - 1] = visited[x][y] + 1
                        nxt.append([x, y - 1])
                if 0 <= x - 1 < h and 0 <= y < w:
                    if maze[x - 1][y] == "." and visited[x - 1][y] == -1:
                        visited[x - 1][y] = visited[x][y] + 1
                        nxt.append([x - 1, y])
                if 0 <= x < h and 0 <= y + 1 < w:
                    if maze[x][y + 1] == "." and visited[x][y + 1] == -1:
                        visited[x][y + 1] = visited[x][y] + 1
                        nxt.append([x, y + 1])
            rtn = 0
            for i in range(h):
                rtn = max(rtn, max(visited[i]))
            return rtn

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

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int,input().split())
s = [input() for _ in range(h)]
ans=0
for i in range(h):
  for j in range(w):
    if s[i][j] =='#':
      continue
    visited=[[-1]*w for _ in range(h)]
    visited[i][j] = 0
    cnt=0
    q = deque([[i,j]])
    while q:
      x,y = q.popleft()
      for k,l in [[0,-1],[0,1],[1,0],[-1,0]]:
        nx,ny = k+x,l+y
        if nx<0 or ny<0 or nx>=h or ny>=w:
          continue
        if s[nx][ny]=='.' and visited[nx][ny]==-1:
          visited[nx][ny] = visited[x][y] + 1
          q.append([nx,ny])
          ans = max(ans,visited[nx][ny])
print(ans)

Submission status: Accepted

Solution code:
import itertools
import collections

n, m = map(int, input().split(" "))
t = [ [-1] * m for i in range(n) ]

NG='#'
OK='.'

ok_list = []
for i in range(n):
    for j,s in enumerate(input()):
        t[i][j] = s
        if s == OK:
            ok_list.append( (i, j ) )


def depth(t, src):
    q = collections.deque()
    deadlist = { src: 0 }
    q.append( (src[0], src[1], 0) )

    while len(q) != 0:
        x, y, cost = q.popleft()
        for _x, _y in [(x+1, y), (x-1,y), (x,y+1),(x,y-1)]:
            if ((_x,_y) not in deadlist ) and \
                ( 0 <= _x < n) and (0 <= _y < m) and t[_x][_y] == OK:
                deadlist[(_x, _y)] = cost+1
                q.append((_x, _y, cost+1))

    return max(deadlist.values())


ans = 0
for src in ok_list:
    tmp = depth(t, src)
    if ans < tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
from queue import Queue
import copy

R, C = map(int, input().split(' '))
M = [[s for s in input()] for _ in range(R)]
trial = 0

for i in range(R):
  for j in range(C):
    Sy = i+1
    Sx = j+1
    L = copy.deepcopy(M)
    if L[Sy-1][Sx-1] == '.':
      move = [(0, -1), (0, 1), (1, 0), (-1, 0)]
      q = Queue()
      ans = 0

      q.put([(Sy, Sx)])
      L[Sy-1][Sx-1] = '#'

      while not q.empty():
          pos = q.get()
          valid_pos = []
          for p in pos:
              for m in move:
                  y, x = p[0]+m[0], p[1]+m[1]
                  if 1<= y  <= R and 1<= x <= C:
                    if L[y-1][x-1] == '.':
                      L[y-1][x-1] = '#'
                      valid_pos.append((y, x))
          if len(valid_pos) != 0:
              q.put(valid_pos)
          ans += 1
      trial = max(ans, trial)
    
print(trial-1)

Submission status: Accepted

Solution code:
from collections import deque

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

maze = [input() for i in range(h)]

ans = 0
INF = 20 * 20 + 1
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[INF] * w for _ in range(h)] 
            cnt[j][i] = 0
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    by += y
                    bx += x 
                    if 0 <= by < h and 0 <= bx < w:
                        ct = cnt[y][x] + 1
                        if maze[by][bx] == "." and ct < cnt[by][bx]:
                            q += [(by,bx)] 
                            cnt[by][bx] = ct
                            ans = max(ans, cnt[by][bx])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

maze = [input() for i in range(h)]

ans = 0
for j in range(h):
    for i in range(w):
        if maze[j][i] == ".":
            cnt = [[0] * w for _ in range(h)] 
            q = deque([(j,i)])
            while q:
                y,x = q.popleft()
                for by,bx in ((0,1),(0,-1),(1,0),(-1,0)):
                    ny = y + by
                    nx = x + bx
                    if 0 <= ny < h and 0 <= nx < w:
                        if maze[ny][nx] == "." and cnt[ny][nx] == 0:
                            q += [(ny,nx)]
                            cnt[ny][nx] += cnt[y][x] + 1
                            ans = max(ans, cnt[ny][nx])
                if y == j and x == i:
                    cnt[y][x] = -1


print(ans)

Submission status: Accepted

Solution code:
from collections import deque

# N, W = 3, 5
# ARR = [
#     ['.', '.', '.', '#', '.'],
#     ['.', '#', '.', '#', '.'],
#     ['.', '#', '.', '.', '.']
# ]

N, W, = 3, 3
ARR = [
    ['.', '.', '.'],
    ['.', '.', '.'],
    ['.', '.', '.'],
]

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

ARR = []

for i in range(N):
    ARR.append(list(map(str, input())))


def dfs(start, n, w, arr):
    d = deque()
    d.append(start)

    states = [[0 for j in range(w)] for i in range(n)]

    maxDistance = start[2]
    while len(d) > 0:
        coordinate = d.popleft()
        coorY = coordinate[0]
        coorX = coordinate[1]
        distance = coordinate[2]
        if states[coorY][coorX] == 1:
            continue
        maxDistance = max(distance, maxDistance)

        states[coorY][coorX] = 1
        leftX, leftY = coorX - 1, coorY
        rightX, rightY = coorX + 1, coorY
        topX, topY = coorX, coorY - 1
        bottomX, bottomY = coorX, coorY + 1

        if leftX >= 0 and leftY >= 0:
            if arr[leftY][leftX] == ".":
                d.append([leftY, leftX, distance + 1])

        if rightX <= w - 1 and rightY <= n - 1:
            if arr[rightY][rightX] == ".":
                d.append([rightY, rightX, distance + 1])

        if topY >= 0:
            if arr[topY][topX] == ".":
                d.append([topY, topX, distance + 1])

        if bottomY <= n - 1:
            if arr[bottomY][bottomX] == ".":
                d.append([bottomY, bottomX, distance + 1])

    return maxDistance


def calculate(n, w, arr):
    distances = []

    for i in range(n):
        for j in range(w):
            if arr[i][j] == ".":
                distance = dfs([i, j, 0], n, w, arr)
                distances.append(distance)

    maxDistance = max(distances)
    print(maxDistance)


# dfs([0, 0, 0], N, W, ARR)

calculate(N, W, ARR)

Submission status: Accepted

Solution code:
import collections
h,w = map(int, raw_input().split(' '))
mat = [raw_input() for _ in range(h)]


def bfs(cur, mat):
	q = collections.deque([(cur,0)])
	vis =  set([])
	temp = 0
	while(q):
		u, dis = q.popleft()
		vis.add(u)
		i,j = u
		temp = max(temp, dis)
		for nei in [(i+1, j), (i-1,j), (i,j-1), (i,j+1)]:
			if 0 <= nei[0]< len(mat) and 0<= nei[1] < len(mat[nei[0]]) and (nei not in vis) and (mat[nei[0]][nei[1]] == '.'):
				vis.add(nei)
				q.append((nei, dis +1))
		

	return temp


m = 0
for i in range(len(mat)):
	for j in range(len(mat[i])):
		if mat[i][j] == '.': 
			m = max(m, bfs((i,j), mat))
print m

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = []
for i in range(n):
    s.append(input())
ans = 0
def bfs(x,y):
    visit = set()
    queue = [[(x, y)]]
    res = -1
    cnt = 0
    while queue != [[]]:
        tmp = queue.pop(0)
        temp = []
        for i in range(len(tmp)):
            a = tmp[i][0]
            b = tmp[i][1]
            if tmp[i] in visit:
                continue
            visit.add(tmp[i])
            if a > 0 and s[a - 1][b] != "#" and (a-1, b) not in visit:
                temp.append((a-1, b))
            if a < n - 1 and s[a + 1][b] != "#" and (a + 1, b) not in visit:
                temp.append((a + 1, b))
            if b > 0 and s[a][b - 1] != "#" and (a, b-1) not in visit:
                temp.append((a, b-1))
            if b < m-1 and s[a][b + 1] != "#" and (a, b+ 1) not in visit:
                temp.append((a, b + 1))
            if not temp:
                res = max(res, cnt)
        queue.append(temp)
        cnt += 1
    return res
for i in range(n):
    for j in range(m):
        if s[i][j] != ".":
            continue
        else:
            ans = max(ans, bfs(i,j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(s_i, s_j):
    q = deque([(s_i, s_j)])
    dists = {(s_i, s_j): 0}
    max_dist = 0
    while q:
        i, j = q.popleft()
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni = i + di
            nj = j + dj
            if 0 <= ni < H and 0 <= nj < W and field[ni][nj] == '.' and (ni, nj) not in dists:
                dists[(ni, nj)] = dists[(i, j)] + 1
                max_dist = max(max_dist, dists[(ni, nj)])
                q.append((ni, nj))
    return max_dist


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] == '#':
            continue
        ans = max(ans, bfs(i, j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sx, sy):
    d = [[-1 * float("inf")] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(sx, sy)])
    d[sx][sy] = 0
    while que:
        p = que.popleft()
        for i in range(4):
            nx = p[0] - dx[i]
            ny = p[1] - dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and d[nx][ny] == -1 * float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
    return max(map(max, d))
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
l = []
for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            continue
        l.append(bfs(i, j))
print(max(l))

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[input() for _ in range(h)]
from collections import deque
def bfs(i,j):
    if s[i][j]=='#':
        return 0
    ret=-1
    todo=[]
    next_todo=[(i,j)]
    seen=[[0]*w for _ in range(h)]
    seen[i][j]=1
    while next_todo:
        ret+=1
        todo=deque(next_todo)
        next_todo=[]
        while todo:
            hi,wi=todo.popleft()
            if hi>0 and seen[hi-1][wi]==0 and s[hi-1][wi]=='.':
                seen[hi-1][wi]=1
                next_todo.append((hi-1,wi))
            if hi<h-1 and seen[hi+1][wi]==0 and s[hi+1][wi]=='.':
                seen[hi+1][wi]=1
                next_todo.append((hi+1,wi))
            if wi>0 and seen[hi][wi-1]==0 and s[hi][wi-1]=='.':
                seen[hi][wi-1]=1
                next_todo.append((hi,wi-1))
            if wi<w-1 and seen[hi][wi+1]==0 and s[hi][wi+1]=='.':
                seen[hi][wi+1]=1
                next_todo.append((hi,wi+1))
    return ret
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:
import sys
from collections import deque

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

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


def bfs(grid, start):
    distance = [[-1] * W for _ in range(H)]
    queue = deque([start])
    distance[start[0]][start[1]] = 0
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and distance[new_x][new_y] == -1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    queue.append((new_x, new_y))
    return max(map(max, distance))


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        tmp = bfs(S, (i, j))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Accepted

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

from collections import deque

que=deque()
maxx=0

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            continue
        ans=[[-1]*W for _ in range(H)]
        ans[i][j]=0
        que.append((i,j))
        while que:
            h,w=que.popleft()
            if h!=0 and S[h-1][w]==".":
                if ans[h-1][w]==-1:
                    ans[h-1][w]=ans[h][w]+1
                    que.append((h-1,w))
            if h!=H-1 and S[h+1][w]==".":
                if ans[h+1][w]==-1:
                    ans[h+1][w]=ans[h][w]+1
                    que.append((h+1,w))
            if w!=0 and S[h][w-1]==".":
                if ans[h][w-1]==-1:
                    ans[h][w-1]=ans[h][w]+1
                    que.append((h,w-1))
            if w!=W-1 and S[h][w+1]==".":
                if ans[h][w+1]==-1:
                    ans[h][w+1]=ans[h][w]+1
                    que.append((h,w+1))
            maxx=max(maxx,ans[h][w])
print(maxx)

Submission status: Accepted

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

from collections import deque

que=deque()
maxx=0

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            continue
        ans=[[500]*W for _ in range(H)]
        ans[i][j]=0
        que.append((i,j))
        while que:
            h,w=que.popleft()
            if h!=0 and S[h-1][w]==".":
                if ans[h-1][w]==500:
                    ans[h-1][w]=ans[h][w]+1
                    que.append((h-1,w))
            if h!=H-1 and S[h+1][w]==".":
                if ans[h+1][w]==500:
                    ans[h+1][w]=ans[h][w]+1
                    que.append((h+1,w))
            if w!=0 and S[h][w-1]==".":
                if ans[h][w-1]==500:
                    ans[h][w-1]=ans[h][w]+1
                    que.append((h,w-1))
            if w!=W-1 and S[h][w+1]==".":
                if ans[h][w+1]==500:
                    ans[h][w+1]=ans[h][w]+1
                    que.append((h,w+1))
            maxx=max(maxx,ans[h][w])
print(maxx)

Submission status: Accepted

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

from collections import deque

que=deque()
maxx=0

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            continue
        ans=[[500]*W for _ in range(H)]
        ans[i][j]=0
        que.append((i,j))
        while que:
            h,w=que.popleft()
            if h!=0 and S[h-1][w]==".":
                if ans[h-1][w]==500:
                    ans[h-1][w]=min(ans[h-1][w],ans[h][w]+1)
                    que.append((h-1,w))
            if h!=H-1 and S[h+1][w]==".":
                if ans[h+1][w]==500:
                    ans[h+1][w]=min(ans[h+1][w],ans[h][w]+1)
                    que.append((h+1,w))
            if w!=0 and S[h][w-1]==".":
                if ans[h][w-1]==500:
                    ans[h][w-1]=min(ans[h][w-1],ans[h][w]+1)
                    que.append((h,w-1))
            if w!=W-1 and S[h][w+1]==".":
                if ans[h][w+1]==500:
                    ans[h][w+1]=min(ans[h][w+1],ans[h][w]+1)
                    que.append((h,w+1))
            maxx=max(maxx,ans[h][w])
print(maxx)

Submission status: Accepted

Solution code:
import copy
h,w = map(int,input().split())

s = [['#' for _ in range(w+2)]]
for i in range(h):
    si = ['#']
    sij = list(input())
    si.extend(sij)
    si.append('#')
    s.append(si)
s.append(['#' for _ in range(w+2)])

def bfs(i,j):
    root = copy.deepcopy(s)
    q = []
    q.append([i,j])
    root[i][j] = 0
    while q:
        ij = q.pop(0)
        i = ij[0]
        j = ij[1]
        
        if root[i-1][j] == '.': #左
            q.append([i-1,j])
            root[i-1][j] = root[i][j] + 1
        if root[i+1][j] == '.': #右
            q.append([i+1,j])
            root[i+1][j] = root[i][j] + 1
        if root[i][j+1] == '.': #上
            q.append([i,j+1])
            root[i][j+1] = root[i][j] + 1
        if root[i][j-1] == '.': #下
            q.append([i,j-1])
            root[i][j-1] = root[i][j] + 1
    max = 0
    for i in range(1,h+1):
        for j in range(1,w+1):
            if root[i][j] != '#' and root[i][j] > max:
                max = root[i][j]
    return max

ans = -1
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j] == '.':
            k = bfs(i,j)
            if ans < k:
                ans = k
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
 
ans = 0
for sh in range(H):
    for sw in range(W):
        # 通れないマスはスタートになり得ない
        if G[sh][sw] == '#':
            continue
 
        # BFS
        dist = [[-1] * W for i in range(H)]
        dist[sh][sw] = 0
        que = deque([[sh, sw]])
 
        while que:
            nh, nw = que.pop()
            for dh, dw in directions:
                # 迷路からはみ出す
                if not ((0 <= nh + dh < H) and (0 <= nw + dw < W)):
                    continue
 
                # 移動先が通れないマス
                if G[nh + dh][nw + dw] == '#':
                    continue
 
                # 探索済み
                if dist[nh + dh][nw + dw] != -1:
                    continue
 
                dist[nh + dh][nw + dw] = dist[nh][nw] + 1
                que.appendleft([nh + dh, nw + dw])
 
        ans = max(ans, max([max(d) for d in dist]))
 
print(ans)

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 
dir = ((-1, 0), (1, 0), (0, -1), (0, 1))
def main():
    h, w = map(int, readline().split())
    grid = []
    for _ in range(h):
        grid.append(readline().rstrip().decode())

    INF = int(1e9)
    mx = 0
    for si in range(h):
        for sj in range(w):
            if grid[si][sj] == '#':
                continue            
            dq = deque()
            dq.append((si, sj))
            dist = [[-1 for _ in range(w)] for _ in range(h)]
            dist[si][sj] = 0
            while len(dq) > 0:
                ni, nj = dq.popleft()
                for d in dir:
                    x, y = ni+d[0], nj+d[1]
                    if (x < 0) or (y < 0) or (x >= h) or (y >= w):
                        continue
                    if grid[x][y] == '#':
                        continue
                    if dist[x][y] != -1:
                        continue 
                    dist[x][y] = dist[ni][nj]+1 
                    dq.append((x, y))

            for i in range(h):
                for j in range(w):
                    if dist[i][j] == -1: 
                        continue
                    mx = max(mx, dist[i][j])
    print(mx)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

grid = [input() for _ in range(h)]

ans = 0

for i in range(h):
    for j in range(w):
        visited = [[-1] * w for _ in range(h)]
        visited[i][j] = 0
        if grid[i][j] == '#':
            continue
        queue = deque([[i,j]])
        while queue:
            x,y = queue.popleft()
            for k,l in ([-1,0],[1,0],[0,-1],[0,1]):
                nx,ny = x+k,y+l
                if nx < 0 or ny < 0 or nx >= h or ny >= w:
                    continue
                if grid[nx][ny] == '.' and visited[nx][ny] == -1:
                    visited[nx][ny] = visited[x][y] + 1
                    ans = max(ans,visited[nx][ny])
                    queue.append([nx,ny])
                    
print(ans)