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
import copy
import queue

# 再帰上限
sys.setrecursionlimit(10 ** 6)


# 最短距離メモ
# 0#4#
# 123
# 23#のような最終結果のためのメモ
# スタートからの最短距離が格納

def answer_sheet(meiro):
    return copy.deepcopy(meiro)


# 【周りの点の取得）
# 座標が与えられると、上下左右の4点を得る。
# 境界を超えた場合はカットされる。
def get_around_point(point, h, w):
    around_points = []

    for ij in [(-1,0),(0,1),(1,0),(0,-1)]:
        i,j=ij
        new_i = point[0] + i
        new_j = point[1] + j
        if 0 <= new_i < h and 0 <= new_j < w:
            around_points.append([new_i, new_j])
    return around_points


# ある点が道かどうかを判別する
def walkable(point, meiro):
    i = point[0]
    j = point[1]
    if meiro[i][j] == ".":
        return True
    return False


# ある点が行ったことあるかどうか
def never_had_been(point, sheet):
    if sheet[point[0]][point[1]] == ".":
        return True
    else:
        return False


# キューに、ある点の周りの行ったことのない道を追加し、シートに距離を記入
def add_load_2_queue(point, h, w, meiro, sheet, que):
    around_points = get_around_point(point, h, w)
    for around_point in around_points:
        if walkable(around_point, meiro) and never_had_been(around_point, sheet):
            que.put(around_point)
            sheet[around_point[0]][around_point[1]] = sheet[point[0]][point[1]] + 1
    return sheet, que


# ポイントが与えられたとき、その周りの道をキューに追加し、シートに記入、次のキューを取り出し同様の処理を行う。キューがなくなるまで続け、シートを返す。
def step(point, h, w, meiro, sheet, que):
    sheet, que = add_load_2_queue(point, h, w, meiro, sheet, que)
    if que.empty():
        return sheet
    next_point = que.get()
    return step(next_point, h, w, meiro, sheet, que)


# シートは、行けない場所の場合は"#"が含まれているため-1に変換
def hash2minus(sheet):
    new_sheet = []
    for gyou in sheet:
        new_gyou = []
        for item in gyou:
            if item == "#":
                new_gyou.append(-1)
            else:
                new_gyou.append(item)
        new_sheet.append(new_gyou)
    return new_sheet


# -------メイン関数---------
# スタートを決めた場合の、各場所までの最短距離を表すシートを出力
# 行けない場所の場合は-1
# 入力
# start 開始座標のリスト(例：[1,2])
# h 迷路の高さ
# w 迷路の幅
# meiro 迷路の文字列リスト
def min_dis(start, h, w, meiro):
    sheet = answer_sheet(meiro)
    que = queue.Queue()
    sheet[start[0]][start[1]] = 0
    return hash2minus(step(start, h, w, meiro, sheet, que))


import numpy as np

h, w = [int(i) for i in input().split()]
meiro = []

for i in range(h):
    meiro.append(list(input()))

ans = 0
for i in range(h):
    for j in range(w):
        if meiro[i][j] == ".":
            ans = max(ans, np.max(np.array(min_dis([i,j], h, w, meiro))))

print(ans)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
S =[list(input()) for _ in range(H)]
N=H*W
INF=float('inf')
L=[[INF]*N for _ in range(N)]
for i in range(N):
    h=i//W
    w=i%W
    # print(i,h,w)
    if S[h][w]=='.':
        L[i][i]=0
    if w>0 and S[h][w-1]=='.':
        L[i][i-1]=1
    if w<W-1 and S[h][w+1]=='.':
        L[i][i+1]=1
    if h>0 and S[h-1][w]=='.':
        L[i][i-W]=1
    if h<H-1 and S[h+1][w]=='.':
        L[i][i+W]=1
# print(L)

for i in range(N):
    via=L[i]
    if via[i]==INF:
        continue
    for j in range(N):
        st=L[j]
        if st[j]==INF:
            continue
        for k in range(N):
            L[j][k]=min(st[i]+via[k], st[k])
# print(L)
ans=0
for i in range(N):
    for j in range(N):
        if L[i][j]!=INF:
            ans=max(ans,L[i][j])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

@njit(cache=True)
def pos(W,h,w):
    return h*W+w

def solve(H,W,G):
    N = H*W+W
    INF=10**18

    dp = np.full((N,N),INF)
    for i in range(N):
        dp[i][i] = 0

    for h in range(H):
        for w in range(W):
            if G[h][w]: continue

            for i in range(4):
                dh = [0,1,0,-1][i]
                dw = [1,0,-1,0][i]
                if 0<=h+dh<H and 0<=w+dw<W:
                    if G[h+dh][w+dw]: continue
                    dp[pos(W,h,w)][pos(W,h+dh,w+dw)] = 1
                    dp[pos(W,h+dh,w+dw)][pos(W,h,w)] = 1


    ans = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j])


    for i in range(N):
        for j in range(N):
            if dp[i][j] != INF:
                ans = max(ans,dp[i][j])
    

    return ans





def main():
    H,W=mi()
    G = [[0] * W for _ in range(H)]
    for h in range(H):
        S = list(input())
        for w in range(W):
            G[h][w] = S[w] == "#"

    print(solve(H,W,np.array(G,bool)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,b1[:,:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

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

from collections import deque
def bfs(h,w,sy,sx,S):
    maze=[[10**9]*(W)for _ in range(H)]
    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    count=0
    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 and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    count=max(count,maze[nexty][nextx])
                    que.append([nexty,nextx])
    return count

ans=0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx]=='.':
            now=bfs(H,W,sy+1,sx+1,S)
            ans=max(ans,now)

print(ans)

Submission status: Accepted

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

from collections import deque
import math


def bfs(h,w,sy,sx,S):
    maze=[[10**9]*(W)for _ in range(H)]

    maze[sy-1][sx-1]=0
    que=deque([[sy-1,sx-1]])
    count=0
    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 and 0<=nextx<w:
                dist1=S[nexty][nextx]
                dist2=maze[nexty][nextx]
            else:
                continue
            if dist1!='#':
                if dist2>maze[y][x]+1:
                    maze[nexty][nextx]=maze[y][x]+1
                    count=max(count,maze[nexty][nextx])
                    que.append([nexty,nextx])
    return count

ans=0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx]=='.':
            now=bfs(H,W,sy+1,sx+1,S)
            ans=max(ans,now)

print(ans)

Submission status: Accepted

Solution code:
import queue

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

h,w=map(int,input().split())
a=[input() for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
for sy in range(h):
    for sx in range(w):
        if a[sy][sx]!='#':
            ans=max(ans,bfs(a,h,w,sy,sx))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque

h, w = map(int, input().split())
tizu = [input() for _ in range(h)]
ans = 0
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
for i in range(h):
    for j in range(w):
        if tizu[i][j] == "#":
            continue
        check = [[False for _ in range(w)] for _ in range(h)]
        check[i][j] = True
        queue = deque()
        queue.append([i, j])
        queue.append(0)
        while queue:
            pos = queue.popleft()
            ans_sub = queue.popleft()
            for dh, dw in directions:
                nh = pos[0] + dh
                nw = pos[1] + dw
                if nh == -1 or nh == h or nw == -1 or nw == w:
                    continue
                if tizu[nh][nw] == "#":
                    continue
                if check[nh][nw]:
                    continue
                check[nh][nw] = True
                queue.append([nh, nw])
                queue.append(ans_sub + 1)
        ans = max(ans, ans_sub)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
yudlr = [-1, 1, 0, 0]
xudlr = [0, 0, -1, 1]
D = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        d = [[-1] * W for _ in range(H)]
        d[i][j] = 0
        Q = deque()
        Q.append([i, j])
        while len(Q) > 0:
            q = Q.popleft()
            y, x = q[0], q[1]
            for k in range(4):
                y1 = y + yudlr[k]
                x1 = x + xudlr[k]
                if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                    continue
                if S[y1][x1] == '#':
                    continue
                if d[y1][x1] != -1:
                    continue
                d[y1][x1] = d[y][x] + 1
                Q.append([y1, x1])
        Dij = max(list(map(lambda x: max(x), d)))
        D = max(D, Dij)
print(D)

Submission status: Accepted

Solution code:
import copy
H, W = map(int, input().split())
s = []
wall=[]
maze = [0] * (H * W)
path = dict()
leaf = []

for i in range(H):
  temp = list(input())
  for j, var in enumerate(temp):
    idx = i*W + j
    maze[idx] = var
    if var == ".":
      s.append(idx)

for i in range(H):
  for j in range(W):
    idx = i*W + j
    temp = []
    if j != 0 and maze[idx-1] != "#":
      temp.append(idx - 1)
    if j != W - 1 and maze[idx+1] != "#":
      temp.append(idx + 1)
    if i != 0 and maze[idx-W] != "#":
      temp.append(idx - W)
    if i != H - 1 and maze[idx + W] != "#":
      temp.append(idx + W)
    path[idx] = temp

ans = 0
start = copy.copy(s)

for st in start:
  dp = [float('inf')] * (H * W)
  prev = [-1] * (H*W)
  dp[st] = 0
  s2 = copy.copy(s)
  while len(s2) > 0:
    dpmin = float('inf')
    idx = 0
    for i in s2:
      if dpmin > dp[i]:
        idx = i
        dpmin = dp[i]
    now = s2.pop(s2.index(idx))
    flag = 0
    for i in path[now]:
      if dp[i] > 1 + dp[now]:
        dp[i] = 1 + dp[now]
        prev[i] = now
        flag = 1
    if flag == 0:
      leaf.append(now)
  dp = [i for i in dp if i != float('inf')]
  if ans < max(dp):
    ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
import collections
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

H, W, *S = open(0).read().split()
H, W = [int(_) for _ in [H, W]]
A = []
B = []
C = []
for i in range(H * W):
    x, y = divmod(i, W)
    if S[x][y] == '.':
        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 S[nx][ny] == '.':
                A += [i]
                B += [nx * W + ny]
                C += [1]
F = floyd_warshall(csr_matrix((C, (A, B)), shape=(H*W, H*W)))
print(int(np.max(F[F!=np.inf])))

Submission status: Accepted

Solution code:
from collections import deque


def LI():
    return list(map(int, input().split()))


def LSH(h):
    return [input() for _ in range(h)]


H, W = LI()
Fi = LSH(H)
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
ans = 0
for sh in range(H):  # スタート位置全部試します
    for sw in range(W):
        if Fi[sh][sw] == "#":
            continue
        d = deque()
        d.append([sh, sw])
        looked = [[0 for i in range(W)]for j in range(H)]
        looked[sh][sw] = 1
        while d:
            h, w = d.popleft()
            for i in move:
                a = h+i[0]
                b = w+i[1]
                if not(0 <= a < H) or not(0 <= b < W) or Fi[a][b] == "#" or looked[a][b] != 0:
                    continue
                d.append([a, b])
                looked[a][b] = looked[h][w]+1
            if len(d) == 0:
                ans = max(ans, looked[h][w]-1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy

h,w=map(int,input().split())
Inf=float('inf')
maze1=[]
for _ in range(h):
  s=list(input())
  for u in range(w):
    if s[u]=='.':
      s[u]=Inf
  maze1.append(s)
  
def maze_solve(maze,sy,sx):
  qu=deque([[sy,sx]])
  maze[sy][sx]=0
  
  while qu:
    y,x=qu.popleft()
    
    T=maze[y][x]
    for i in ([1,0],[-1,0],[0,1],[0,-1]):
      ny=y+i[0]
      nx=x+i[1]
      if 0<=ny<=h-1 and 0<=nx<=w-1 and maze[ny][nx]!='#':
        
        if maze[ny][nx]>T+1:
          maze[ny][nx]=T+1
          qu.append([ny,nx])
          
  ans=-Inf
  for i in range(h):
    for j in range(w):
      if maze[i][j]!='#' and maze[i][j]!=Inf:
        ans=max(ans,maze[i][j])
  return ans
  

ans=-Inf
for i in range(h):
  for j in range(w):
    if maze1[i][j]!='#':
      maze2=copy.deepcopy(maze1)
      ans=max(ans,maze_solve(maze2,i,j))
            
            
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
s=[input() for _ in range(h)] #マップ
vi=[ [-1 for _ in range(w)] for _ in range(h)]#visit
st=deque()

d=[[0,1],[-1,0],[1,0],[0,-1]]

mx=0

for i in range(h):
  for j in range(w):
    vi=[ [-1 for _ in range(w)] for _ in range(h)]
    st.append([i,j,0])
    
    while st:
      h1,w1,k=st.popleft()

      if 0<=h1<h and 0<=w1<w and vi[h1][w1]==-1 and s[h1][w1]==".":
        vi[h1][w1]=k
        for m in d:
          st.append([h1+m[0],w1+m[1],k+1])
    for m in vi:
      mx=max(mx,max(m))

print(mx)

Submission status: Accepted

Solution code:
H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_count=[[0]*W for i in range(H)]
from collections import deque
def answer(st_X,st_Y):#X,Y座標を指定してそこからの距離を考える
   tmp_X,tmp_Y=st_X,st_Y
   que=deque([[tmp_X,tmp_Y]])
   after=set()
   while que:#スタート地点からの距離を数えながら行ったことのない場所を探索する
      tmp_X,tmp_Y=que.popleft()
      nu=l_count[tmp_Y][tmp_X]
      after.add((tmp_X,tmp_Y))
      if tmp_X>0 and l[tmp_Y][tmp_X-1]=="." and (tmp_X-1,tmp_Y) not in after and [tmp_X-1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X-1]=nu+1
         que.append([tmp_X-1,tmp_Y])
      if tmp_Y>0 and l[tmp_Y-1][tmp_X]=="." and (tmp_X,tmp_Y-1) not in after and [tmp_X,tmp_Y-1] not in que:
         l_count[tmp_Y-1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y-1])
      if tmp_X<W-1 and l[tmp_Y][tmp_X+1]=="." and (tmp_X+1,tmp_Y) not in after and [tmp_X+1,tmp_Y] not in que:
         l_count[tmp_Y][tmp_X+1]=nu+1
         que.append([tmp_X+1,tmp_Y])
      if tmp_Y<H-1 and l[tmp_Y+1][tmp_X]=="." and (tmp_X,tmp_Y+1) not in after and [tmp_X,tmp_Y+1] not in que:
         l_count[tmp_Y+1][tmp_X]=nu+1
         que.append([tmp_X,tmp_Y+1])
ans=0
for i in range(H):
   for j in range(W):
      if l[i][j]==".":
         l_count=[[0]*W for i in range(H)]
         answer(j,i)
         tmp=max(sum(l_count,[]))
         ans=max(ans,tmp)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
S=[input() for _ in range(H)]
ans=0
d=deque([])
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    d.append((i,j,0))
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while d:
      x,y,c=d.popleft()
      for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
        nx,ny=x+dx,y+dy
        if 0<=nx<H and 0<=ny<W and visited[nx][ny]==-1 and S[nx][ny]=='.':
          visited[nx][ny]=c+1
          d.append((nx,ny,c+1))
    ans=max(ans,c)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np
def main():
    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])

            distance[x][y] = 0
            ans = max(ans, np.max(distance))

    print(ans)

main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start):
    s = start + (0,)
    queue = deque([s])
    max_count = 0
    seen = set()
    seen.add(start)
    while queue:
        y,x,count = queue.popleft()
        max_count = max(max_count, count)
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            #print(next_y, next_x)
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                queue.append((next_y, next_x, count+1))
                seen.add((next_y, next_x))
    return max_count


def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    #for m in MAZE:
    #    print(m)

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for s_i, s_j in ways:
        min_count = bfs(MAZE, (s_i, s_j))
        #print((s_i, s_j), '->', (g_i, g_j))
        #print(min_count)
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
from collections import deque
#from decimal import Decimal
#from numba import jit

INF = 1 << 50

def bfs(MAZE, start, seen):
    queue = deque([start + (0 ,)])
    max_count = 0
    while queue:
        y,x,count = queue.popleft()
        max_count = max(max_count, count)
        if (y,x) in seen:
            continue
        seen.add((y, x))
        for i,j in ((0,1), (0,-1), (1,0), (-1, 0)):
            next_y, next_x = y + i, x + j
            #print(next_y, next_x)
            if not (next_y, next_x) in seen and MAZE[next_y][next_x] == '.':
                queue.append((next_y, next_x, count+1))
                #seen.add((next_y, next_x))
    return max_count


def run():
    H, W = map(int, input().split())
    MAZE = ['#' * (W+2)]
    for _ in range(H):
        s = input()
        s = '#' + s + '#'
        MAZE.append(s)
    MAZE.append('#' * (W+2))

    #for m in MAZE:
    #    print(m)

    ways = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if MAZE[i][j] == '.':
                ways.append((i, j))

    max_count = 0
    for s_i, s_j in ways:
        seen = set((s_i, s_j))
        min_count = bfs(MAZE, (s_i, s_j), seen)
        #print((s_i, s_j), '->', (g_i, g_j))
        #print(min_count)
        max_count = max(max_count, min_count)

    print(max_count)

if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import copy
h,w = map(int, input().split()) 
map=[[-1]*w for i in range(h)]

for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            map[i][j]=-2

zanteisaidai=0

def saidaikyori(saisyo_gyou,saisyo_retu,saidaiti):
    map_copy=copy.deepcopy(map)
    map_copy[saisyo_gyou][saisyo_retu]=0
    kyori=0
    while kyori<300:
        for gyou in range(h):
            for retu in range(w):
                if map_copy[gyou][retu]==kyori:
                    if gyou+1<h:
                        if map_copy[gyou+1][retu]==-1:
                            map_copy[gyou+1][retu]=kyori+1
                    if 0<=gyou-1:
                        if map_copy[gyou-1][retu]==-1:
                            map_copy[gyou-1][retu]=kyori+1
                    if retu+1<w:
                        if map_copy[gyou][retu+1]==-1:
                            map_copy[gyou][retu+1]=kyori+1
                    if 0<=retu-1:
                        if map_copy[gyou][retu-1]==-1:
                            map_copy[gyou][retu-1]=kyori+1

        kyori+=1
    
    for gyou in range(h):
        for retu in range(w):
            saidaiti=max(saidaiti,map_copy[gyou][retu])
    return saidaiti

for gyou in range(h):
    for retu in range(w):
        if map[gyou][retu]==-1:
            zanteisaidai=saidaikyori(gyou,retu,zanteisaidai)

print(zanteisaidai)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
g = []
for _ in range(h):
    S = input()
    tmp = [str(i) for i in S]
    g.append(tmp)
from collections import deque
# print(g)
dp = [[0]*w for _ in range(h)]
def dfs(i,j):
    seen = [[False]*w for _ in range(h)]
    seen[i][j] = True
    q = deque([])
    q.append((i,j,0))
    dist=[(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        x,y,cnt = q.popleft()
        for dx,dy in dist:
            if 0 <=x+dx<h and 0<=y+dy<w and seen[x+dx][y+dy]==False and g[x+dx][y+dy]=='.':
                seen[x+dx][y+dy] = True
                q.append((x+dx,y+dy,cnt+1))
    return cnt
ans = 0
for i in range(h):
    for j in range(w):
        if g[i][j] =='.':
            ans =max(ans,dfs(i,j))
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

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

def bfs(u):
    stack = deque([u])
    visited = set()
    seen = set()
    p = [[INF for j in range(W)] for i in range(H)]
    p[u[0]][u[1]] = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == "#":
                p[i][j] = -1

    while len(stack) > 0:
        v = stack.popleft()
        ###
        visited.add(v)
        ###

        a = (v[0] + 1, v[1])
        b = (v[0]    , v[1] + 1)
        c = (v[0] - 1, v[1])
        d = (v[0]    , v[1] - 1)

        e = [a, b, c, d]

        for ee in e:
            if ee[0] >= 0 and ee[0] <= H-1 and ee[1] >= 0 and ee[1] <= W-1:
                if S[ee[0]][ee[1]] == ".":
                    if ee not in visited:
                        p[ee[0]][ee[1]] = min(p[ee[0]][ee[1]], p[v[0]][v[1]] + 1)
                        if ee not in seen:
                            stack.append(ee)
                            seen.add(ee)

    ans = 0
    for i in range(H):
        ans = max(ans, max(p[i]))
    return ans

sol = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            sol = max(sol, bfs((i,j)))

print(sol)

Submission status: Accepted

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

S = []
for i in range(H):
    S.append(list(input()))
# print('S:',*S,sep='\n')

out=0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
#スタート・ゴール全探索
for i_s in range(H):
    for j_s in range(W):
        if S[i_s][j_s]!='#':
            # print('S,G:',i_s,j_s,i_g,j_g)
            #BFS
            init = 10**9
            d = [[init] * W for i in range(H)]  #これを更新していく
            # print('d:',*d, sep='\n')
            que = deque([])
            que.append((i_s,j_s))
            d[i_s][j_s] = 0
            while que:
                p = que.popleft()
                for i in range(4):  #四方をチェック
                    nx = p[0] + dx[i]
                    ny = p[1] + dy[i]
                    # print('p,nx,ny,S[nx][ny]:',p,nx,ny,S[nx][ny])
                    if (0<=nx<H)and(0<=ny<W)and(S[nx][ny]!="#")and(d[nx][ny]==init):
                        # print('yahhoooo')
                        que.append((nx, ny))  #後で(nx,ny)の四方みていくよ
                        # print(d[p[0]][p[1]])
                        d[nx][ny] = d[p[0]][p[1]] + 1  #d更新しておくよ
                        out=max(out,d[p[0]][p[1]] + 1)
            # print('d:',*d, sep='\n')
            # print('ゴール',d[i_g][j_g])
# print(out)
print(out)

Submission status: Accepted

Solution code:
import queue

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

s=[]
for _ in range(h):
    s.append(input())

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            seen=[[0 for _ in range(w)] for _ in range(h)]
            length=[[0 for _ in range(w)] for _ in range(h)]
            q=queue.Queue()
            q.put([i,j])
            seen[i][j]=1
            while not q.empty():
                ci,cj=q.get()
                for ni,nj in [[ci-1,cj],[ci+1,cj],[ci,cj-1],[ci,cj+1]]:
                    if 0<=ni<h and 0<=nj<w and s[ni][nj]=="." and seen[ni][nj]==0:
                        q.put([ni,nj])
                        length[ni][nj]=length[ci][cj]+1
                        seen[ni][nj]=1
            ans=max(ans,length[ci][cj])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


from collections import deque


# In[2]:


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


# In[3]:


def bfs(sx,sy):
    dx = [1,0,-1,0]
    dy = [0,1,0,-1]
    d = [[-1]*W for _ in range(H)]
    q = deque([])
    q.append([sx,sy])
    d[sx][sy] = 0
    ans = 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 S[nx][ny] != "#" and d[nx][ny] == -1:
                q.append([nx,ny])
                d[nx][ny] = d[x][y] + 1
                ans = max(ans,d[nx][ny])
    return ans


# In[5]:


ans = 0
for sh in range(H):
    if "." in S[sh]:
        for sw in range(W):
            if S[sh][sw] == ".":
                ans = max(ans,bfs(sh,sw))
print(ans)


# In[ ]:

Submission status: Accepted

Solution code:
import queue
import copy
q = queue.Queue()
h, w = map(int, input().split())
a = [list('#'+input()+'#') for _ in range(h)]
a = [['#']*(w+2)]+a+[['#']*(w+2)]
a1 = copy.deepcopy(a)
ans = []
        
for i in range(1, h+1):
    for j in range(1, w+1):
        a = copy.deepcopy(a1)
        if a[i][j] == '#':
            continue        
        q.put([i, j, 0])
        while not q.empty():
            now = q.get()
            
            if a[now[0]][now[1]] == '.':
                ans.append(now[2])
                a[now[0]][now[1]] = '#'
            else:
                continue
                
            if a[now[0]+1][now[1]] != '#':
                q.put([now[0]+1, now[1], now[2]+1])
            if a[now[0]-1][now[1]] != '#':
                q.put([now[0]-1, now[1], now[2]+1])
            if a[now[0]][now[1]+1] != '#':
                q.put([now[0], now[1]+1, now[2]+1])
            if a[now[0]][now[1]-1] != '#':
                q.put([now[0], now[1]-1, now[2]+1])
        a1[i][j] == '#'
print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
L = []
for _ in range(H):
    s = input()
    a = []
    for i in range(len(s)):
        a.append(s[i])
    L.append(a)

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


def bfs(x, y):
    dp = [[10000000] * W for _ in range(H)]
    dp[y][x] = 0
    if L[y][x] == '#':
        return dp
    else:
        d = deque()
        d.append([x, y])
        while len(d) > 0:
            s = d.popleft()
            for i in range(4):
                if (s[1] +
                    dy[i] >= 0 and s[1] +
                    dy[i] < H and s[0] +
                    dx[i] >= 0 and s[0] +
                        dx[i] < W):
                    if L[s[1] +
                         dy[i]][s[0] +
                                dx[i]] == '.' and dp[s[1] +
                                                     dy[i]][s[0] +
                                                            dx[i]] == 10000000:
                        d.append([s[0] + dx[i], s[1] + dy[i]])
                        dp[s[1] + dy[i]][s[0] + dx[i]] = dp[s[1]][s[0]] + 1

        return dp


max_num = 0
for i in range(H):
    for j in range(W):
        dp = bfs(j, i)
        for k in dp:
            for p in k:
                if (p == 10000000):
                    continue
                max_num = max(max_num, p)
print(max_num)