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:
h,w=map(int,input().split())
M=[]


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

def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop()
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='#':
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.insert(0,(px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0

    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans

ans=0
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            continue
        ans=max(bfs(i,j),ans)

print(ans)

Submission status: Accepted

Solution code:
H, W = [int(i) for i in input().split()]
S = [input() for _ in range(H)]
inf = 1000000
dist = [[-1]*(W*H) for _ in range(W*H)]

def bfs(s):
    seen = set()
    stk = [(s, 0)]
    while stk:
        pt, dst = stk.pop()
        ph, pw = pt//W, pt%W
        if(pt in seen):
            continue
        seen.add(pt)

        if(S[ph][pw]=='#'):
            dist[s][pt] = 0
            continue

        for x,y in ((1,0), (-1,0), (0, 1), (0,-1)):
            if((not(0<=pw+x<W))or (not(0<=ph+y<H))):
                continue
            else:
                ns = (ph+y)*W + (pw+x)
                stk.insert(0, (ns, dst+1))
        dist[s][pt] = dst
        
ans = 0
for s in range(H*W):
    h, w = s//W, s%W
    if(S[h][w]=='#'):
        continue
    bfs(s)
    
    ans = max(ans, max(dist[s]))

print(ans)

Submission status: Accepted

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

  
already = [[False]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    if mapping[i][j] == "#":
      already[i][j] = True


ans = 0

for i in range(h):
  for j in range(w):
    if already[i][j]:
      continue
    
    yet = copy.deepcopy(already)
    yet[i][j] = True
    not_yet = deque([])
    
    depth = [[0]*w for i in range(h)]
    
    if i != 0 and not yet[i-1][j]:
        not_yet.append([i-1, j])
        depth[i-1][j] = 1
        yet[i-1][j] = True
    if i != h-1 and not yet[i+1][j]:
        not_yet.append([i+1, j])
        depth[i+1][j] = 1
        yet[i+1][j] = True
    if j != 0 and not yet[i][j-1]:
        not_yet.append([i, j-1])
        depth[i][j-1] = 1
        yet[i][j-1] = True
    if j != w-1 and not yet[i][j+1]:
        not_yet.append([i, j+1])
        depth[i][j+1] = 1
        yet[i][j+1] = True
    
    while len(not_yet) > 0:
        key = not_yet.popleft()
        a, b = key[0], key[1]
        
        if a != 0 and not yet[a-1][b]:
            not_yet.append([a-1, b])
            yet[a-1][b] = True
            depth[a-1][b] = depth[a][b]+1
            
        if a != h-1 and not yet[a+1][b]:
            not_yet.append([a+1, b])
            yet[a+1][b] = True
            depth[a+1][b] = depth[a][b]+1
            
        if b != 0 and not yet[a][b-1]:
            not_yet.append([a, b-1])
            yet[a][b-1] = True
            depth[a][b-1] = depth[a][b]+1
            
        if b != w-1 and not yet[a][b+1]:
            not_yet.append([a, b+1])
            yet[a][b+1] = True
            depth[a][b+1] = depth[a][b]+1
            
    for x in range(h):
        for y in range(w):
            if ans < depth[x][y]:
                ans = depth[x][y]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
#探索
def bfs(Sy,Sx):

    dis=[[-1]*W for i in range(H)]
    dis[Sy][Sx]=0
    q=deque()
    q.append([Sy,Sx])#pairとして入れる
    nun=0

    #qの中身が無くなるまで続ける(bfsのメイン部分)
    while(len(q)!=0):
        y=q[0][0]
        x=q[0][1]
        q.popleft()
        
        #四方向それぞれ条件を満たせるか調べていく
        for dy,dx in ([0, 1], [1, 0], [0, -1], [-1, 0]):
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if field[ny][nx]=="#":
                continue
            if dis[ny][nx]!=-1:
                continue
            dis[ny][nx]=dis[y][x]+1
            nun=max(nun,dis[ny][nx])
            q.append([ny,nx])
    return nun
  
#入力
H,W=map(int,input().split())
field=[input() for i in range(H)]

#各開始地点からの距離をそれぞれ求め最大のものを出力
ans=-1
for y in range(H):
    for x in range(W):
        if field[y][x]=="#":
            continue
        ans=max(ans,bfs(y,x))
print(ans)

Submission status: Accepted

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

def max_distance(board, H, W, x, y):
    check = [[False] * W for i in range(H)]
    ans = 0
    q = deque()
    q.append((x, y, 0))
    check[y][x] = True
    while len(q) > 0:
        x, y, cost = q.popleft()
        ans = max(ans, cost)
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if not check[ny][nx] and board[ny][nx] == ".":
                    q.append((nx, ny, cost + 1))
                    check[ny][nx] = True
    return ans

    

def main():
    H, W = map(int, input().split())
    board = [input().strip() for i in range(H)]

    ans = 0
    for y in range(H):
        for x in range(W):
            if board[y][x] == ".":
                tmp = max_distance(board, H, W, x, y)
                # print(x, y, tmp)
                ans = max(ans, tmp)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

ans = 0
for i in range(H):
  for j in range(W):

    if S[i][j]=='#':
      continue
    
    # A[i][j]をスタート位置に設定
    # スタート以外は一旦無限数に設定
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0

    # スタート位置をキューに追加
    q = deque([[i, j]])

    # 全てのマスを探索するまでwhile
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for h, w in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:
        
        # マスが範囲外の場合
        if (h<0) or (h>H-1) or (w<0) or (w>W-1):
          continue
        # マスが障害物の場合
        if S[h][w]=='#':
          continue

        # すでに距離が確定しているマスに＋１を追加した数
        c = b+1

        # cが無限大（未探索）より大きい場合、continue
        if c>=A[h][w]:
          continue

        A[h][w]=c
        # 探索済みのマスをキューに追加
        q.append([h,w])
      
    A = np.array(A)

    # 未到達のマス以外で最も距離が長いマスの距離
    # 前回までのansと上記の数を比べて大きい方をansに代入
    ans = max(ans, max(A[A<10**5]))
    
print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
ls = [input() for _ in range(h)]
from collections import deque
a = 0
for i in range(h):
  for j in range(w):
    if ls[i][j]=='#': continue
    d = [[-1]*w for _ in range(h)]
    d[i][j] = 0
    q = deque([(i,j)])
    while q:
      x,y = q.popleft()
      for dx,dy in ((1,0),(0,1),(-1,0),(0,-1)):
        nx,ny = x+dx,y+dy
        if not (0<=nx<h and 0<=ny<w): continue
        if ls[nx][ny]=='.' and d[nx][ny]==-1:
          d[nx][ny] = d[x][y]+1
          q.append((nx,ny))
    a = max(a,max(max(j for j in i) for i in d))
print(a)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
maze = [0] * h
for i in range(h):
    maze[i] = list(input())
# print(maze)
INF = int(1e10 + 7)
d = [[INF] * w for i in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# que = deque([('x', 'y')])
# print(que)
# print(que[0])

def bfs(x, y):
    d = [[INF] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([(x, y)])
    d[x][y] = 0

    while len(que) != 0:
        val = que.popleft()

        for i in range(4):
            nx = val[0] + dx[i]
            ny = (val[1] + dy[i])
            if (0 <= nx < h and 0 <= ny < w and maze[nx][ny] != '#' and d[nx][ny] == INF):
                que.append((nx, ny))
                d[nx][ny] = d[val[0]][val[1]] + 1
    maxval = 0
    for i in range(h):
        for j in range(w):
            if d[i][j] > maxval and d[i][j] != INF:
                maxval = d[i][j]
    return maxval

maxans = 0
cnt = []
for i in range(h):
    for j in range(w):
        if maze[i][j] != '#':
            if bfs(i, j) > maxans:
                maxans = bfs(i, j)
print(maxans)

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sy,sx):
    d = [[-float("inf")] * (2+w) for i in range(h+2)]

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

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()
        #if p[0] == gy and p[1] == gx:
        #    break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if maze[nx][ny] != "#" and d[nx][ny] == -float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    ans = 0
    for i in range(2+w):
        for j in range(h+2):
            ans = max(ans,d[j][i])
    return ans
h,w = map(int, input().split())
maze = [["#"]*(w+2)] + [list("#" + input() + "#") for i in range(h)] + [["#"]*(w+2)]
ans = 0
for x in range(1,w+1):
    for y in range(1,h+1):
        if maze[y][x] == ".":
            ans = max(bfs(y,x),ans)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from itertools import product
H,W = map(int,input().split())

S = ["#"*(W+2)]
for i in range(H):
    S.append("#"+ input() + "#")
S.append("#"*(W+2))

H += 2
W += 2

max_dist = 0
for sy,sx in product(range(1,H),range(1,W)):
    dist = [[H*W+1]*W for i in range(H)]
    if S[sy][sx] == "#":
        continue
    dq = deque([(sy,sx)])
    dist[sy][sx] = 0
    while dq:
        py,px = dq.popleft()
        for ny, nx in [(py+1,px),(py-1,px),(py,px+1),(py,px-1)]:
            if S[ny][nx] == "#":
                continue
            if dist[ny][nx] > dist[py][px] + 1:
                dist[ny][nx] = dist[py][px] + 1
                max_dist = max(max_dist, dist[ny][nx])
                dq.append((ny,nx))
    #list(map(lambda x:print(x), dist))
    #print()

print(max_dist)

Submission status: Accepted

Solution code:
import queue

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


def srch(h,w):
    ans = 0
    cnt = [[-1 for _ in range(W)] for _ in range(H)]
    que = queue.Queue()
    li1 = [1,0,-1,0]
    li2 = [0,1,0,-1]
    ans = 0
    res = 0

    que.put([h,w,0])
    cnt[h][w]=0

    while not(que.empty()):
        plc = que.get()
        y = plc[0]
        x = plc[1]
        ans = plc[2]

        for i in range(4):
            ny,nx = y+li1[i], x+li2[i]
            # print(ny,nx)
            if ny>=0 and ny<H and nx>=0 and nx<W and cnt[ny][nx]==-1 and S[ny][nx]==".":
                cnt[ny][nx]= ans+1
                que.put([ny,nx,ans+1])
                res = ans +1
    # if h==4 and w==6:
    #     for h in range(H):
    #         for j in range(W):
    #             print("{:>3}".format(cnt[h][j]),end="")
    #         print()
            

    return res


ans = 0

for h in range(H):
    for w in range(W):
        if S[h][w]==".":
            ans = max(ans,srch(h,w))

print(ans)

Submission status: Accepted

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

def cango(now,h,w):
    ans = []
    if now[0]>0:
        ans.append( (now[0]-1,now[1]) )
    if now[0]<h-1:
        ans.append( (now[0]+1,now[1]) )
    if now[1]>0:
        ans.append( (now[0],now[1]-1) )
    if now[1]<w-1:
        ans.append( (now[0],now[1]+1) )
    return ans

from collections import deque

ans=0
for hh in range(h):
    for ww in range(w):
        if s[hh][ww]==".":
            start = (hh,ww)
            q = deque( [] )
            q.append( ((-1,-1),start,0) )
            visit = [[0]*w for _ in range(h)]
            visit[hh][ww]=1
            while q:
                old,now,dist = q.popleft()
#                 print(old,now,dist)
                if ans<dist:
                    ans=dist
                for new in cango(now,h,w):
                    if s[new[0]][new[1]]=="." and visit[new[0]][new[1]]==0:
                        q.append( (now,new,dist+1) )
                        visit[new[0]][new[1]] = 1
print(ans )

Submission status: Accepted

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

from collections import deque
import numpy as np
def bfs(sy, sx):
    d = [[-1] * w for _ in range(h)]
    que = deque([[sy, sx]])
    d[sy][sx] = 0
    while que:
        y, x = que.popleft()
        #if y == gy and x == gx:
            #break
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            ny, nx = y + j, x + k
            if 0 <= nx < w and 0 <= ny < h and d[ny][nx] == -1 and maze[ny][nx] != "#":
                d[ny][nx] = d[y][x] + 1
                que.append([ny, nx])
    d = np.array(d)
    return np.max(d)

ans = 0
for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] != "#":  
              ans = max(ans, bfs(sy, sx))
print(ans)

Submission status: Accepted

Solution code:
#D
from collections import deque
h,w=map(int,input().split())
s=[]

for i in range(h):
    s.append(list(input()))
dx=[1,0,-1,0]#東南西北
dy=[0,-1,0,1]
ans=0
def search(i,j):
    if s[i][j]=="#":
        return 0
    max_step=0
    que=deque()
    que.append([i,j])#1現在地
    dist=[[-1 for _ in range(w)] for _ in range (h)]
    #(h,w)
    dist[i][j]=0#現在地は0
    while que:#行き先が無くなるまで
        y,x=que.popleft()#現在地を取り出す(y,x)
        for dir in range(4):
            nx=x+dx[dir]#行き先(nx,xy)
            ny=y+dy[dir]
            if ny<0 or ny>=h or nx<0 or nx>=w or s[ny][nx]=="#":#壁の中
                pass#何もしない
            elif dist[ny][nx]!=-1:#捜索済み
                pass
            elif s[ny][nx]==".":
            #未捜索地点"."
                dist[ny][nx]=dist[y][x]+1#1進む
                que.append([ny,nx])
    out=0
    for i in range(h):
        for j in range(w):
            if dist[i][j]==-1:
                pass
            out=max(out,dist[i][j])
    return out

for i in range(h):
    for j in range(w):
        step=search(i,j)#(j,i)の時の最大移動数を求める
        if ans<step:
            ans=step
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

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

ans = 0
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])
        
        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])
        
        #start位置は0で初期化
        distance[x][y] = 0
        #print(distance[0])
        #print(distance[1])
        #print(distance[2])
        #print()
        ans = max(ans, np.max(distance))
        
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

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

board = []
for row in range(h):
    board.append(list(input()))

def bfs(row, col):
    if board[row][col] == "#":
        return 0
    max_path = 0
    queue = deque([(row, col)])
    visited[row][col] = 0
    while queue:
        next = queue.popleft()
        if next[0] < h-1 and visited[next[0]+1][next[1]] == -1 and board[next[0]+1][next[1]] == ".":
            visited[next[0]+1][next[1]] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0]+1, next[1]))
        if next[0] > 0 and visited[next[0]-1][next[1]] == -1 and board[next[0]-1][next[1]] == ".":
            visited[next[0]-1][next[1]] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0]-1, next[1]))
        if next[1] < w-1 and visited[next[0]][next[1]+1] == -1 and board[next[0]][next[1]+1] == ".":
            visited[next[0]][next[1]+1] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0], next[1]+1))
        if next[1] > 0 and visited[next[0]][next[1]-1] == -1 and board[next[0]][next[1]-1] == ".":
            visited[next[0]][next[1]-1] = visited[next[0]][next[1]] + 1
            if visited[next[0]][next[1]] + 1 > max_path:
                max_path = visited[next[0]][next[1]] + 1
            queue.append((next[0], next[1]-1))
    return max_path

result = 0
for i in range(h):
    for j in range(w):
        visited = [[-1]*w for _ in range(h)]
        max_path = bfs(i, j)
        if result < max_path:
            result = max_path

print(result)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np

def bfs(maze, visited, sx, sy):
    if s[sx][sy] == "#":
        return 0
    queue = deque([[sx, sy]])
    visited[sx][sy] = 0
    while queue:
        x, y = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_x, new_y = x + j, y + k
            if (new_x < 0 or new_x >= H or new_y < 0 or new_y >= W or 
            visited[new_x][new_y] != -1 or s[new_x][new_y] == "#"):
                continue
            else:
                visited[new_x][new_y] = visited[x][y] + 1
                queue.append([new_x, new_y])
    return max(np.array(visited).flatten())

H, W = map(int, input().split())
s = []
for _ in range(H):
    s.append([i for i in input()])
ans = 0
for i in range(H):
    for k in range(W):
        visited = [[-1 for _ in range(W)] for _ in range(H)]
        ans = max(ans, bfs(s, visited, i, k))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = list(map(int,input().split()))
s = [list(input()) for _ in range(h)]
dyx = [(1, 0), (-1, 0), (0, 1), (0, -1)]

q = deque()
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        q.append((i, j))
        d = [ [0] * w for _ in range(h) ]
        while q:
            y, x = q.popleft()
            for dy, dx in dyx:
                ny = y + dy
                nx = x + dx
                if ny == i and nx == j:
                    continue
                if 0 <= ny < h and 0 <= nx < w and d[ny][nx]==0 and s[ny][nx]==".":
                    d[ny][nx] = d[y][x] + 1
                    q.append((ny, nx))

        # (i, j)からスタートできるとき，最大遠いところを計算する
        for k in range(h):
            ans = max(ans, max(d[k]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input()) for _ in range(h)]
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    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
n=h*w
INF=1<<20
d = [[float("inf") for i in range(n)] for i in range(n)]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
dyx=[(1,0),(-1,0),(0,1),(0,-1)]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            continue
        for dy,dx in dyx:
            if 0<=i+dy<h and 0<=j+dx<w and s[i+dy][j+dx]==".":
                d[i*w+j][(i+dy)*w+j+dx]=1
                d[(i+dy)*w+j+dx][i*w+j]=1



for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

x=warshall_floyd(d)
for i in range(n):
    for j in range(n):
        if x[i][j]==float("inf"):
            x[i][j]=-1

ans=0
for i in range(n):
    ans=max(ans,max(x[i]))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * (w+2) for _ in range(h+2)]
    step_cnt[y0][x0] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1

    
    return step_cnt[y][x]

h, w = map(int, input().split())
maze = [['#'] * (w+2)]
maze += [['#']+[x for x in input()]+['#'] for _ in range(h)]
maze += [['#'] * (w+2)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(1, h+1):
    for x0 in range(1, w+1):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Submission status: Accepted

Solution code:
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0-1][x0-1] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 1 <= y_next < h+1 and 1 <= x_next < w+1\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next-1][x_next-1] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next-1][x_next-1] = step_cnt[y-1][x-1] + 1

    return step_cnt[y-1][x-1]

h, w = map(int, input().split())
maze = [['#'] * (w+2)]
maze += [['#']+[x for x in input()]+['#'] for _ in range(h)]
maze += [['#'] * (w+2)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(1, h+1):
    for x0 in range(1, w+1):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Submission status: Accepted

Solution code:
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * (w+2) for _ in range(h+2)]
    step_cnt[y0][x0] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 1 <= y_next < h+1 and 1 <= x_next < w+1\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1

    return step_cnt[y][x]

h, w = map(int, input().split())
maze = [['#'] * (w+2)]
maze += [['#']+[x for x in input()]+['#'] for _ in range(h)]
maze += [['#'] * (w+2)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(1, h+1):
    for x0 in range(1, w+1):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Submission status: Accepted

Solution code:
from collections import deque

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q.append((y0, x0))
    while q:
        y, x = q.popleft()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.append((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = deque()

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Submission status: Accepted

Solution code:
import queue

def shortestpath(y0, x0):
    step_cnt = [[-1] * w for _ in range(h)]
    step_cnt[y0][x0] = 0
    q.put((y0, x0))
    while not q.empty():
        y, x = q.get()
        for i in range(4):
            y_next = y + dy[i]
            x_next = x + dx[i]
            if 0 <= y_next < h and 0 <= x_next < w\
            and maze[y_next][x_next] == '.'\
            and step_cnt[y_next][x_next] == -1:
                q.put((y_next, x_next))
                step_cnt[y_next][x_next] = step_cnt[y][x] + 1
                    
    return step_cnt[y][x]

h, w = map(int, input().split())      
maze = [[x for x in input()] for _ in range(h)]
dy = [-1, 0, 1, 0]
dx = [0, -1, 0, 1]
q = queue.Queue()

max_steps = -1
for y0 in range(h):
    for x0 in range(w):
        if maze[y0][x0] != '#':
            max_steps = max(max_steps, shortestpath(y0, x0))

print(max_steps)

Submission status: Accepted

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

h, w = map(int, input().split())
S = [input() for _ in range(h)] # #.のグリッドの場合

starts = []
for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            starts.append((i,j))

step = [(1, 0), (-1, 0), (0, 1), (0, -1)]
ans = 0
for si in starts:
    maxlen = 0
    seen = [[0] * w for _ in range(h)]
    que = deque()
    que.append(si)
    #seen[si[0]][si[1]] = 1
    while len(que) > 0:
        x, y = que.popleft()
        for xs, ys in step:
            xi, yi = x + xs, y + ys
            if xi < 0 or yi < 0 or xi >= h or yi >= w:
                continue
            if xi == si[0] and yi == si[1]:
                continue
            if S[xi][yi] == '#':
                continue
            if seen[xi][yi] != 0:
                continue
            else:
                seen[xi][yi] = seen[x][y] + 1
                que.append((xi, yi))
                maxlen = max(maxlen, seen[xi][yi])
    #print(np.array(seen))
    ans = max(ans, maxlen)
print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy


def solve(maze, i, j, h, w, count):
    distance = 0
    if maze[i][j] == ".":
        distance = 0
        next_search = [(i, j)]
        while not next_search == []:
            now = next_search.pop(0)
            if maze[now[0]][now[1]] == ".":
                maze[now[0]][now[1]] = "#"
                for direction in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    search = [direction[0] + now[0], direction[1] + now[1]]
                    if search[0] < 0 or h <= search[0] or search[1] < 0 or w <= search[1] or \
                            maze[search[0]][search[1]] == "#":
                        continue
                    else:
                        count[search[0]][search[1]] = count[now[0]][now[1]] + 1
                        next_search.append(tuple(search))
                        distance = max(distance, count[search[0]][search[1]])
    return distance


def main():
    height, width = map(int, input().split(" "))
    maze = []
    answer = 0
    for _ in range(height):
        maze.append(list(input()))
    count = [[0 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            answer = max(answer, solve(deepcopy(maze), i, j, height, width, deepcopy(count)))
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from copy import deepcopy


def solve(maze, i, j, h, w, count):
    # 左上から縦i, 横j進んだマス(i, j)を起点としたBFS
    if maze[i][j] == "#":
        return 0
    else:
        distance = 0
        next_search = [(i, j)]
        while not next_search == []:
            now = next_search.pop(0)
            if maze[now[0]][now[1]] == ".":
                maze[now[0]][now[1]] = "#"
                for direction in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    search = [direction[0] + now[0], direction[1] + now[1]]
                    if search[0] < 0 or h <= search[0] or search[1] < 0 or w <= search[1] or \
                            maze[search[0]][search[1]] == "#":
                        continue
                    else:
                        count[search[0]][search[1]] = count[now[0]][now[1]] + 1
                        next_search.append(tuple(search))
                        distance = max(distance, count[search[0]][search[1]])
        return distance


def main():
    height, width = map(int, input().split(" "))
    maze = []
    answer = 0
    for _ in range(height):
        maze.append(list(input()))
    count = [[0 for _ in range(width)] for _ in range(height)]
    for i in range(height):
        for j in range(width):
            answer = max(answer, solve(deepcopy(maze), i, j, height, width, deepcopy(count)))
    print(answer)


if __name__ == '__main__':
    main()