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 sys
sys.setrecursionlimit(1000000)
from collections import deque


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

def bfs(sx,sy):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    d = [[-1]*w for i in range(h)]
    q = deque()
    q.append((sx,sy))
    d[sx][sy] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if  0<= nx < h and 0 <= ny < w and d[nx][ny]==-1 and s[nx][ny]=='.':
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return max([max(i) for i in d])

count = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            count  = max(count, bfs(i,j))
print(count)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in directions:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '#':
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(start, maze, H, W):
    max_step = 0
    used = [[False for _ in range(W)] for _ in range(H)]
    start_x, start_y = start
    used[start_x][start_y] = True
    stack = deque([[start, 0]])
    while stack:
        (i, j), step = stack.popleft()
        if maze[i][j] == '#':
            continue
        max_step = max(max_step, step)
        for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= x < H and 0 <= y < W and not used[x][y]:
                stack.append([(x, y), step + 1])
                used[x][y] = True
    return max_step

if __name__ == '__main__':
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        S.append(list(input()))
    ret = 0
    for i in range(H):
        for j in range(W):
            ret = max(ret, bfs((i, j), S, H, W))
    print(ret)

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]
    directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in directions:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '#':
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                continue

            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '#':
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            ans = max(ans, max([max(l) for l in goal_dists]))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                continue
            goal_dists = [[-1] * W for _ in range(H)]
            goal_dists[h][w] = 0
            d = deque([[h, w]])

            while d:
                ht, wt = d.popleft()
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if not (0 <= ht+dh < H and 0 <= wt+dw < W):
                        continue
                    if maze[ht+dh][wt+dw] == '#':
                        continue
                    if goal_dists[ht+dh][wt+dw] == -1:
                        goal_dists[ht+dh][wt+dw] = goal_dists[ht][wt] + 1
                        d.append([ht+dh, wt+dw])
            
            max_dist = [max(goal_dists[h]) for h in range(H)]
            ans = max(ans, max(max_dist))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
INF = 20 * 20 + 1

def main():
    H, W = map(int, input().split())
    maze = [list(input()) for _ in range(H)]

    ans = 0
    goal_base = [[-1 for _ in range(W+2)] for _ in range(H)]
    goal_base = [[-1 for _ in range(W+2)]] + goal_base + [[-1 for _ in range(W+2)]]
    for h in range(H):
        for w in range(W):
            if maze[h][w] == '#':
                goal_base[h+1][w+1] = -1
            else:
                goal_base[h+1][w+1] = INF

    for hs in range(H):
        for ws in range(W):
            if maze[hs][ws] == '#':
                continue

            goal_dists = copy.deepcopy(goal_base)
            goal_dists[hs+1][ws+1] = 0
            d = deque([[hs+1, ws+1]])
            while len(d) > 0:
                ht, wt = d.popleft()
                dist = goal_dists[ht][wt]
                for dh, dw in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
                    if goal_dists[ht+dh][wt+dw] == INF:
                        goal_dists[ht+dh][wt+dw] = dist + 1
                        d.append([ht+dh, wt+dw])
            
            max_dist = [goal_dists[h][w] for w in range(1, W+2) for h in range(1, H+2) if goal_dists[h][w] != INF]
            ans = max(ans, max(max_dist))

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

def f(h,w): #スタートが(h,w)
  if S[h][w] == '#':
    return 0
  else:
    d = [[-1]*W for i in range(H)]
    d[h][w] = 0
    
    q = deque([[h,w]])
    
    while q:
      nh,nw = q.pop()
      
      for dh,dw in directions:
        if not (0<=nh+dh<H and 0<=nw+dw<W):
          continue
        if S[nh+dh][nw+dw] == '#':
          continue
        if d[nh+dh][nw+dw] != -1:
          continue
        d[nh+dh][nw+dw] = d[nh][nw]+1
        q.appendleft([nh+dh,nw+dw])
     
    return max([max(i) for i in d])

a = 0
for h in range(H):
  for w in range(W):
    a = max(a,f(h,w))
    
print(a)

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int,input().split())
S=[]
pos=[]
for i in range(h):
  l=input()
  L=[]
  for j in range(w):
    if l[j]=='.':
      L.append('.')
      pos.append((i,j))
    else:
      L.append('#')
  S.append(L)
Maze=[[float('inf')]*w for i in range(h)]
def bfs(h,w,S,Maze,sy,sx):
    maze=Maze
    maze=[[float('inf')]*w for i in range(h)]
    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que: #キューの中に入っているということはまだ調べる余地有り
        y,x=que.popleft()
        for (i,j) in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+i,x+j
            if 0<=nexty<=h-1 and 0<=nextx<=w-1:
              dist=maze[nexty][nextx]
              if S[nexty][nextx]!='#':
                if dist>maze[y][x]+1: #今の経路から(nexty,nextx)に進む方が距離が短くなるなら
                    maze[nexty][nextx]=maze[y][x]+1
                    que.append([nexty,nextx])
    m=0
    for i in range(h):
      for j in range(w):
        if maze[i][j]!=float('inf'):
          if m<maze[i][j]:
            m=maze[i][j]
            
    return m
        
M=0
for (sy,sx) in pos:
  if bfs(h,w,S,Maze,sy,sx)>M:
    M=bfs(h,w,S,Maze,sy,sx)

print(M)

Submission status: Accepted

Solution code:
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
from itertools import product

h, w = map(int, input().split())
s = np.full((h, w), 'x', dtype='U1')
for i in range(h):
    s[i] = list(input())

d = np.identity(h * w, dtype='i1')
for i, k in product(range(h), range(w)):
    if s[i, k] == '#':
        continue
    for dy, dx in ((-1, 0), (0, -1), (0, 1), (1, 0)):
        y, x = i + dy, k + dx
        if y < 0 or h <= y or x < 0 or w <= x or s[y, x] == '#':
            continue
        d[i*w+k, y*w+x] = 1
        d[y*w+x, i*w+k] = 1

print(floyd_warshall(d).astype('i8').max())

Submission status: Accepted

Solution code:
import queue

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

ans = 0

move = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            d = [[-1 for j in range(w)] for i in range(h)]
            q = queue.Queue()
            q.put([i,j])
            d[i][j]=0
            while 1:
                y,x = q.get()
                for dy,dx in move:
                    if 0<=y+dy<h and 0<=x+dx<w:
                        if a[y+dy][x+dx]=='.' and d[y+dy][x+dx]==-1:
                            q.put([y+dy,x+dx])
                            d[y+dy][x+dx]=d[y][x]+1
                if q.empty():
                    ans = max(ans,d[y][x])
                    break

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
from itertools import product

H, W = map(int, input().split())
S = np.full((H, W), 'x', dtype='U1')
for i in range(H):
    S[i] = list(input())

def bfs(x, y):
    dist = np.full((H, W), -1, dtype='i8')
    que = deque()

    dist[x, y] = 0
    que.append((x, y))

    while que:
        h, w = que.popleft()
        d = dist[h, w]
        for dx, dy in ((0, -1), (-1, 0), (1, 0), (0, 1)):
            hh, ww = h + dx, w + dy
            if hh < 0 or H <= hh or ww < 0 or W <= ww or S[hh, ww] == '#' or dist[hh, ww] != -1:
                continue
            dist[hh, ww] = d + 1
            que.append((hh, ww))

    return d

res = 0
for i, k in product(range(H), range(W)):
    if S[i, k] == '#':
        continue
    d = bfs(i, k)
    if d > res:
        res = d
print(res)

Submission status: Accepted

Solution code:
import numpy as np
H, W = map(int, input().split())
mp = np.array([list(input()) for _ in range(H)], dtype=str)

import queue
q = queue.Queue()
visit = (mp == "#")

def can_visit(x, y):
    """訪問可能ならTrue。壁、既訪問、世界外ならFalse"""
    if x < 0 or y < 0 or x >= W or y >= H:
        return False
    return not visit[y, x]

def push_neighbor(x, y, d):
    """隣接マスをキューにpush"""
    lis = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
    for nx, ny in lis:
        if can_visit(nx, ny):
            q.put((nx, ny, d+1))
            visit[ny, nx] = True

def furthest(sx, sy):
    """位置(sx, sy)から見て一番遠い場所までの距離"""
    # 初期化
    global visit
    visit = (mp == "#")
    if visit[sy, sx]:# 例外処理(スタート地点が壁の中)
        return 0
    visit[sy, sx] = True# 初期位置は訪問済み
    # 計算
    q.put((sx, sy, 0))
    while not q.empty():
        x, y, d = q.get()
        push_neighbor(x, y, d)
    return d

dist = max([furthest(sx, sy) for sx in range(W) for sy in range(H)])
print(dist)

Submission status: Accepted

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

q = Queue()
searched = [[False for _ in range(W)] for __ in range(H)]
dist = [[-1 for _ in range(W)] for __ in range(H)]

def bfs(x, y, d):
    if not (0 <= x < W and 0 <= y < H):
        return
    if S[y][x] == '#':
        return
    if searched[y][x]:
        return
    searched[y][x] = True
    dist[y][x] = d
    q.put([x, y, d])
    return

ans = 0
for s_y in range(H):
    for s_x in range(W):
        if S[s_y][s_x] == '#':
            continue
        
        q = Queue()
        searched = [[False for _ in range(W)] for __ in range(H)]
        dist = [[-1 for _ in range(W)] for __ in range(H)]
        
        dist[s_y][s_x] = 0
        searched[s_y][s_x] = True
        
        q.put([s_x, s_y, 0])
        
        while not q.empty():
            x, y, d = q.get()
            bfs(x-1, y, d+1)
            bfs(x+1, y, d+1)
            bfs(x, y-1, d+1)
            bfs(x, y+1, d+1)
        
        dist_max = max(list(map(lambda x: max(x), dist)))
        ans = max(ans, dist_max)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

S = [['#'] * (W + 2)]
for _ in range(H):
    tmp = ['#'] + list(input()) + ['#']
    S.append(tmp)
S.append(['#'] * (W + 2))

move = [[1, 0], [-1, 0], [0, 1], [0, -1]]

ans = 0
# スタート位置を変えながら全探索
for X in range(1, H + 1):
    for Y in range(1, W + 1):
        if S[X][Y] == '#':
            continue
        check = [[-1] * (W + 2) for _ in range(H + 2)]
        check[X][Y] = 0
        que = deque()
        que.append([X, Y])
        while que:
            tmp = que.popleft()
            x = tmp[0]
            y = tmp[1]
            flag = True
            for dx, dy in move:
                nx = x + dx
                ny = y + dy
                if S[nx][ny] == '.' and check[nx][ny] == -1:
                    que.append([nx, ny])
                    check[nx][ny] = check[x][y] + 1
                    flag = False
            if flag:
                ans = max(ans, check[x][y])


print (ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
Maze = [list(input()) for _ in range(H)]
ans = 0
sy = 0
while sy < H:
  sx = 0
  while sx < W:
    if Maze[sy][sx] == ".":
      M_cnt = 0
      q = deque()
      memo = [[-1]*(W) for _ in range((H))]
      memo[sy][sx] = 0
      q.append([sy, sx])
      while q:
        cy, cx = q.popleft()
        for ny, nx in zip((cy, cy, cy+1, cy-1) , (cx+1, cx-1, cx, cx)):
          if ny >= 0 and ny < H and nx >= 0 and nx < W and Maze[ny][nx] == "." and memo[ny][nx] < 0:
            q.append([ny, nx])
            memo[ny][nx] = memo[cy][cx] + 1
      ans = max(ans, max([max(m)  for m in memo]))
    sx += 1
  sy += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    d = [[10**3] * w for i in range(h)]

    # 移動4方向のベクトル
    dh = [1, 0, -1, 0]
    dw = [0, 1, 0, -1]

    global sh
    global sw
    que = deque([])
    que.append((sh, sw))
    d[sh][sw] = 0
    chk = []
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nh = p[0] + dh[i]
            nw = p[1] + dw[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            if 0 <= nh < h and 0 <= nw < w and maze[nh][nw] != "#" and d[nh][nw] == float(10**3):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nh, nw))
                d[nh][nw] = d[p[0]][p[1]] + 1
                
    return d[p[0]][p[1]]

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
maze = [list(input()) for i in range(h)]
maze = tuple(maze)

res = set()
# スタート地点をキューに入れ、その点の距離を0にする
for i in range(h):
  for j in range(w):
      if maze[i][j] == ".":
          sh = i
          sw = j
          res.add(bfs())
          
print(max(res))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
ans = 0
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            start.append([i, j])
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while start:
    check = deepcopy(dist)
    s_y, s_x = start.pop()
    check[s_y][s_x] = True
    q = [(s_y, s_x)]
    cnt = -1
    while q:
        cnt += 1
        qq = []
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            start.append([i, j])
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = 0
while start:
    check = deepcopy(dist)
    q = [start.pop()]
    check[q[0][0]][q[0][1]] = True
    q[0] = tuple(q[0])
    cnt = -1
    while q:
        cnt += 1
        qq = []
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans = max(ans, cnt)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from copy import deepcopy

h, w = map(int, readline().split())
s = [input() for i in range(h)]
q = []
start = []
dist = [[False] * w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            start.append((i, j))
        else:
            dist[i][j] = True
test = [(0, 1), (0, -1), (1, 0), (-1, 0)]
ans = []
while start:
    check = deepcopy(dist)
    q = [start.pop()]
    check[list(q)[0][0]][list(q)[0][1]] = True
    cnt = -1
    while q:
        cnt += 1
        qq = []
        memo = len(q)
        memo_cnt = 0
        for y, x in q:
            for dy, dx in test:
                yy, xx = y + dy, x + dx
                if xx < 0 or yy < 0 or xx > w - 1 or yy > h - 1 or check[yy][xx]:
                    memo_cnt += 1
                    continue
                else:
                    check[yy][xx] = True
                    qq.append((yy, xx))
        q = qq
    ans.append(cnt)
else:
    print(max(ans))

Submission status: Accepted

Solution code:
def warshal_floyd(d, n):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


H, W = list(map(int, input().split()))
maze = [[0 for _ in range(W)] for _ in range(H)]
location = []
for i in range(H):
    for j, s in enumerate(list(input())):
        s = 1 if s == '.' else 0
        maze[i][j] = s
        location.append((i,j))

# 隣接行列
d = [[float('inf') for _ in range(H*W)] for _ in range(H*W)]

# 隣接行列の作成
for i in range(H*W):
    for j in range(H*W):
        # iからjへ行けたら1とする
                 
        # i == j は0とする
        if i == j:
            d[i][j] = 0

        # i, jの情報
        x_i, y_i = location[i]
        x_j, y_j = location[j]
        # 上下左右以外は考慮しない
        if abs(x_i - x_j) + abs(y_i - y_j) == 1 and abs(x_i - x_j) * abs(y_i - y_j) == 0:
            # どちらも.であればOK
            if maze[x_i][y_i] == 1 and maze[x_j][y_j] == 1:
                d[i][j] = 1

d = warshal_floyd(d, H*W)

m = 0
for i in range(H * W):
    for j in range(H * W):
        if d[i][j] != float('inf'):
            m = max(m, d[i][j])

print(m)

Submission status: Accepted

Solution code:
from collections import deque
d = [(-1,0),(1,0),(0,1),(0,-1)]

def bfs(y,x,c):
    q =  deque()
    q.append((y,x,c))
    ma = 0
    visit[y][x] = 1
    while q:
        y,x,c = q.popleft()
        ma = max(ma,c)
        for dy,dx in d:
            if 0<=y+dy<h and 0<=x+dx<w:
                if area[y+dy][x+dx] =="." and visit[y+dy][x+dx] == 0:
                    q.append((y+dy,x+dx,c+1))
                    visit[y+dy][x+dx] = 1
    return ma

h,w = map(int,input().split())
area = []
for i in range(h):
    area.append(list(input()))
ans = 0
for i in range(h):
    for j in range(w):
        if area[i][j] ==".":
            visit = [[0]*w for i in range(h)]
            ans = max(ans,bfs(i,j,0))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = -np.ones((H+2, W+2), dtype=np.int64)
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = np.full((H+2, W+2), -1, dtype=np.int)
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if depth[ny][nx] == -1 and S[ny][nx] == '.':
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
maze = [list(input()) for i in range(n)]

from collections import deque


# 辿り着けないと INF
def bfs(i,k):
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

#最短経路を探す再はコメントin
#     for i in range(n):
#         for j in range(m):
#             # スタートとゴールの座標を探す
#             if maze[i][j] == "S":
#                 sx = i
#                 sy = j
#             if maze[i][j] == "G":
#                 gx = i
#                 gy = j

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((i, k))
    d[i][k] = 0

    # キューが空になるまでループ
    ans = 0
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
#         # 取り出してきた状態がゴールなら探索をやめる
#         if p[0] == gx and p[1] == gy:
#             break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1
                ans = max(ans, d[p[0]][p[1]] + 1)

    return ans

result = 0
for i, row in enumerate(maze):
    for k, element in enumerate(row):
        if element =='.':
            result = max(result, bfs(i,k))
print(result)

Submission status: Accepted

Solution code:
from collections import deque

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

max_move = 0
for start_i in range(h):
  for start_j in range(w):
    if maze[start_i][start_j] == '.':
      queue = deque([(0, start_i, start_j)])
      yet = [[True] * w for _ in range(h)]
      yet[start_i][start_j] = False
      while queue:
        move, i, j = queue.popleft()
        if i != 0 and maze[i-1][j] == '.' and yet[i-1][j]:
          queue.append((move + 1, i - 1, j))
          yet[i-1][j] = False
        if i != h - 1 and maze[i+1][j] == '.' and yet[i+1][j]:
          queue.append((move + 1, i + 1, j))
          yet[i+1][j] = False
        if j != 0 and maze[i][j-1] == '.' and yet[i][j-1]:
          queue.append((move + 1, i, j - 1))
          yet[i][j-1] = False
        if j != w - 1 and maze[i][j+1] == '.' and yet[i][j+1]:
          queue.append((move + 1, i, j + 1))
          yet[i][j+1] = False
      if move > max_move:
        max_move = move

print(max_move)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
work = [[[] for j in range(w)] for i in range(h)]
result = 0
for i in range(h):
    for j in range(w):
        append = work[i][j].append
        if i<h-1 and s[i+1][j] == ".":
            append([i+1,j])
        if i>0 and s[i-1][j] == ".":
            append([i-1,j])
        if j<w-1 and s[i][j+1] == ".":
            append([i,j+1])
        if j>0 and s[i][j-1] == ".":
            append([i,j-1])
q = deque()
popleft = q.popleft
append = q.append
for i in range(h):
    for j in range(w):
        if s[i][j] != ".":
            continue
        q.clear()
        q.append([i, j])
        temp = [[i, j]]
        tempappend = temp.append
        d = -1
        count = 1
        counter = 0
        for k in range(w*h):
            x, y = popleft()
            count -= 1
            for el in work[x][y]:
                if el not in temp:
                    counter += 1
                    append(el)
                    tempappend(el)
            if count == 0:
                d += 1
                count = counter
                counter = 0
            if len(q) == 0:
                break
        result = result if result>d else d
    if result == h+w-2:
        break
print(result)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    ans=0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if maze[new_y][new_x] == "." and visited[new_y][new_x]==-1:
                visited[new_y][new_x]=visited[y][x]+1
                ans=max(ans,visited[new_y][new_x])
                queue.append([new_y,new_x])
    return ans
    
def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="#"+maze[i]+"#"
    maze.appendleft("#"*(w+2))
    maze.append("#"*(w+2))
    return list(maze)
    
h,w=map(int,input().split())
maze=[input() for _ in range(h)]
maze=make_wall(maze,h,w)
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if maze[i][j]=="#":
            continue
        visited=[[-1]*(w+2) for _ in range(h+2)]
        tmp=bfs(maze, visited, i, j)
        ans=max(ans,tmp)
print(ans)