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:
# D - Maze Master
from collections import deque, defaultdict

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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque, defaultdict

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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque, defaultdict

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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Maze Master
from collections import deque, defaultdict

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


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


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

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

# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sy, sx):
    # すべての点を INF で初期化
    d = [[float("inf")] * W for i in range(H)]

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

    # 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((sy, sx))
    d[sy][sx] = 0
    
    max_root = 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[1] + dx[i]
            ny = p[0] + dy[i]

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



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

# print(ans)
# print(bfs())

Submission status: Accepted

Solution code:
#python3
from collections import deque

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

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

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

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

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

main()

Submission status: Accepted

Solution code:
#python3
from collections import deque
from collections import namedtuple

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

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

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

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


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

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

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

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import pprint
from collections import deque
import itertools

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

#現在地が壁の中のときスキップ
        if maze[x][y] == '#':
            continue

#四方へ移動したときに壁の中、もしくは探索済ならスキップ
        for a,b in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_x, new_y = x+a, y+b
            if maze[new_x][new_y] == '#' or depth[new_x][new_y] >= 0:
                pass

#そうでなければ深さを１足してキューへ保存
            else:
                depth[new_x][new_y] = depth[x][y] + 1
                queue.append([new_x, new_y])

#深さマップを平坦化して最大値を出力
    return max(list(itertools.chain.from_iterable(depth)))


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

#外側を壁で囲った迷路入力
    for m in range(1,H+1):
        maze[m][1:W+1] = list(input())

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

#深さマップの初期化
            depth = [[-1] * (W+2) for __ in range(H+2)]
            ans.append(bfs(i,j,maze,depth))

    print(max(ans))

main()

Submission status: Accepted

Solution code:
import sys
import pprint
from collections import deque
import itertools

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

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

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

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

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

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

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

    print(max(ans))

main()

Submission status: Accepted

Solution code:

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

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

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

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

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

    return longest

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

longest_longest = 0

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

        if longest_longest < longest:
            longest_longest = longest  

print(longest_longest)

Submission status: Accepted

Solution code:
from collections import deque


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

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

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

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

            if maze[ni][nj] == "#" or dist[ni][nj] != -1:
                continue

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

    return depth, i, j


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

maze = []

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

answer = 0

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

print(answer)

Submission status: Accepted

Solution code:
r,c=map(int,input().split())
meiro=[list(input()) for i in range(r)]
#迷路の白マスを数える作業
white=[]
for i in range(r):
    for j in range(c):
        if meiro[i][j]==".":
            white.append([i+1,j+1])
#迷路の外を＃で囲む
for i in range(r):
    meiro[i].insert(c,"#")
    meiro[i].insert(0,"#")
meiro.insert(0,["#"]*(c+2))
meiro.append(["#"]*(c+2))
#print(meiro)
def bfs(sx,sy):
    idou=[[0,1],[0,-1],[1,0],[-1,0]]
    tesuu=[[-1]*(c+2) for i in range(r+2)]
    from collections import deque
    tesuu[sx][sy]=0
    #print(tesuu)
    quest=deque([[sx,sy]])#最初に見る場所
    while len(quest)!=0:
        see=quest.popleft()
        for i in idou:
            if meiro[see[0]+i[0]][see[1]+i[1]]=="#":
                continue
            if tesuu[see[0]+i[0]][see[1]+i[1]]!=-1:
                continue
            quest.append([see[0]+i[0],see[1]+i[1]])
            tesuu[see[0]+i[0]][see[1]+i[1]]=tesuu[see[0]][see[1]]+1
    import itertools
    tesuu=list(itertools.chain.from_iterable(tesuu))
    return max(tesuu)
tesuu_=[]
for i in range(len(white)):
    tesuu_.append(bfs(white[i][0],white[i][1]))
print(max(tesuu_))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

ans = 0

for si in range(H):   #スタート位置の設定
    for sj in range(W):
        if S[si][sj] == '#':
            continue       # continue はスキップ
        q = deque([(si, sj)])
        dist = [[INF] * W for _ in range(H)]
        dist[si][sj] = 0
        while q:
            i, j = q.popleft()
            for d in range(4):
                ni = i + di[d]      # 右　左　上　下　入力
                nj = j + dj[d]
                if (ni < 0 or ni >= H or nj < 0 or nj >= W):
                    continue
                if S[ni][nj] == '#':     #壁があったらスキップ
                    continue
                if dist[ni][nj] != INF:  #探索済みかどうか
                    continue
                q.append((ni, nj))
                dist[ni][nj] = dist[i][j] + 1

        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    ans = max(ans, dist[i][j])
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

Submission status: Accepted

Solution code:
from collections import deque
import sys

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

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

Submission status: Accepted

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

# 隣接のマスをループで表すために必要
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

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

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

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  # スタート地点からの距離が入る
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  # スタート地点は0

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

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

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

    max_cost = count(m)
    return max_cost

ans = -1
# 壁以外のすべてのマスをスタートにして探索
for i in range(H):
    for j in range(W):
        if not is_street(i, j):
            continue
        c = bfs(i, j)
        ans = max(ans, c)

print(ans)

Submission status: Accepted

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

# 隣接のマスをループで表すために必要
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

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

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

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  # スタート地点からの距離が入る
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  # スタート地点は0

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

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

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

    max_cost = count(m)
    return max_cost

ans = -1
# 壁以外のすべてのマスをスタートにして探索
for i in range(H):
    for j in range(W):
        if not is_street(i, j):
            continue
        c = bfs(i, j)
        ans = max(ans, c)

print(ans)

Submission status: Accepted

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

# 隣接のマスをループで表すために必要
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]

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

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

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  # スタート地点からの距離が入る
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  # スタート地点は0

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

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

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

    max_cost = count(m)
    return max_cost

ans = -1
# 壁以外のすべてのマスをスタートにして探索
for i in range(H):
    for j in range(W):
        if is_street(i, j):
            c = bfs(i, j)
            ans = max(ans, c)

print(ans)

Submission status: Accepted

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

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

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

def bfs(h, w):
    """
    h: スタート位置（高さ）
    w: スタート位置（横）
    """
    m = []  # スタート地点からの距離が入る
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0  # スタート地点は0

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

        # 上
        uh = t-1
        uw = u
        if uh >= 0 and m[uh][uw] == -1 and is_street(uh, uw):
            m[uh][uw] = cost + 1
            q.append([uh, uw])

        # 下
        sh = t+1
        sw = u
        if sh < H and m[sh][sw] == -1 and is_street(sh, sw):
            m[sh][sw] = cost + 1
            q.append([sh, sw])

        # 左
        lh = t
        lw = u-1
        if lw >= 0 and m[lh][lw] == -1 and is_street(lh, lw):
            m[lh][lw] = cost + 1
            q.append([lh, lw])


        rh = t
        rw = u+1
        if rw < W and m[rh][rw] == -1 and is_street(rh, rw):
            m[rh][rw] = cost + 1
            q.append([rh, rw])

    max_cost = count(m)
    return max_cost

ans = -1
# 壁以外のすべてのマスをスタートにして探索
for i in range(H):
    for j in range(W):
        if is_street(i, j):
            c = bfs(i, j)
            ans = max(ans, c)

print(ans)

Submission status: Accepted

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

def is_street(s, t):
    return S[s][t] == '.'

def count(maze):
    r = -1
    for i in range(H):
        for j in range(W):
            r = max(r, maze[i][j])
    return r

def bfs(h, w):
    m = []
    for i in range(H):
        s = [-1] * W
        m.append(s)
    m[h][w] = 0

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

        # 上
        ue = [t-1, u]
        if ue[0] >= 0 and m[ue[0]][ue[1]] == -1 and is_street(ue[0], ue[1]):
            m[ue[0]][ue[1]] = cost + 1
            q.append(ue)

        shita = [t+1, u]
        if shita[0] < H and m[shita[0]][shita[1]] == -1 and is_street(shita[0], shita[1]) :
            m[shita[0]][shita[1]] = cost + 1
            q.append(shita)

        hidari = [t, u-1]
        if hidari[1] >= 0 and m[hidari[0]][hidari[1]] == -1 and is_street(hidari[0], hidari[1]):
            m[hidari[0]][hidari[1]] = cost + 1
            q.append(hidari)

        migi = [t, u+1]
        if migi[1] < W and m[migi[0]][migi[1]] == -1 and is_street(migi[0], migi[1]):
            m[migi[0]][migi[1]] = cost + 1
            q.append(migi)
    # print(m)
    max_cost = count(m)
    return max_cost

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

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = (int(x) for x in input().split())
C = [list(input()) for i in range(H)]
walk = [[1,0],[0,1],[-1,0],[0,-1]]
que = deque()
ans = -1
for sx in range(W):
    for sy in range(H):
        if C[sy][sx] == "#":
            continue
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        
        que.append((sy,sx))
        dist[sy][sx] = 0
        while que:
            y,x = que.popleft()
            for tmp in walk:
                nx = x + tmp[0]
                ny = y + tmp[1]
                if 0 <= nx < W and 0 <= ny < H and C[ny][nx] == ".":
                    if dist[ny][nx] == -1:
                        dist[ny][nx] = dist[y][x] + 1
                        que.append((ny,nx))
        for tmp in dist:
            t = max(tmp)
            ans = max(ans,t)
print(ans)