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 numpy as np
h, w = list(map(int, input().split()))
ss = []
for _ in range(h):
    s = input()
#     s = s.replace(".", "0").replace("#", "1")
#     s = list(map(int, list(s)))
    ss.append(s)
# ss = np.array(ss)
    

from collections import deque
def find(now_h, now_w):
    dp = np.zeros([h, w], dtype = np.int32) + 9999
    dp[now_h, now_w] = 0
    que = deque()
    que.append((now_h, now_w))
    while len(que) > 0:
        now_h, now_w = que.popleft()
        if (now_h, now_w) in que:
            continue
        for mh, mw in ([0,1], [0,-1], [1,0], [-1,0]):
            next_h = now_h + mh
            next_w = now_w + mw
            if next_h < 0 or next_h >= h or next_w < 0 or next_w >= w:
                continue
            if ss[next_h][next_w] == "#":
                continue
            a = dp[now_h, now_w] + 1
            if dp[next_h, next_w] > a:
                dp[next_h, next_w] = a
                que.append((next_h, next_w))
#             print(que)
    score = np.max(dp[dp != 9999])
    return score

maximum = 0
for sh in range(h):
    for sw in range(w):
        if ss[sh][sw] == ".":
            if sh > 0 and sh < h - 1 and sw > 0 and sw < w - 1:
                if 0 + (ss[sh + 1][sw] == ".") + (ss[sh - 1][sw] == ".") + (ss[sh][sw + 1] == ".") + (ss[sh][sw - 1] == ".") >= 3:
                    continue
            score = find(sh, sw)
            if maximum < score:
                maximum = score

print(maximum)

Submission status: Accepted

Solution code:


def read_input():
    h, w = map(int, input().split())
    maze = [list(input()) for _ in range(h)]
    cell = lambda x, y : x * w + y

    edges = {}
    for hi in range(h):
        for wi in range(w):
            edges[cell(hi, wi)] = []

            if maze[hi][wi] == "#":
                continue
            if 0 <= hi - 1:
                if maze[hi - 1][wi] == '.':
                    edges[cell(hi, wi)].append(cell(hi - 1, wi))
            if hi + 1 < h:
                if maze[hi + 1][wi] == '.':
                    edges[cell(hi, wi)].append(cell(hi + 1, wi))
            if 0 <= wi - 1:
                if maze[hi][wi - 1] == '.':
                    edges[cell(hi, wi)].append(cell(hi, wi - 1))
            if wi + 1 < w:
                if maze[hi][wi + 1] == '.':
                    edges[cell(hi, wi)].append(cell(hi, wi + 1))

    return h, w, edges, maze


def warshall_floyd(h, w, edges):
    v = h * w
    d = [[v + 1 for _ in range(v)] for _ in range(v)]

    for i in range(v):
        d[i][i] = 0

    for f, tlist in edges.items():
        for t in tlist:
            d[f][t] = 1

    for k in range(v):
        for i in range(v):
            for j in range(v):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    return d   
    

def submit():
    h, w, edges, maze = read_input()
    dist = warshall_floyd(h, w, edges)

    max_dist = 0
    v = h * w
    for i in range(v):
        for j in range(v):
            d = dist[i][j]
            if d > v:
                continue
            if d > max_dist:
                max_dist = d
    print(max_dist)


if __name__ == "__main__":
    submit()

Submission status: Accepted

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

def next(pos):
    x, y = pos
    ret = []
    for dx, dy in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        i = x + dx
        j = y + dy
        if 0 <= i < h and 0 <= j < w and f[i][j] != '#':
            ret.append((i, j))
    return ret

ans = 0
for i in range(h):
    for j in range(w):
        if f[i][j] != '#':
            s = {(i, j)}
            ng = set()
            dis = 0
            while s:
                t = set()
                for p in s:
                    ng.add(p)
                    for x, y in next(p):
                        if (x, y) not in ng:
                            t.add((x, y))
                s = t
                dis += 1
            ans = max(ans, dis - 1)
print(ans)

Submission status: Accepted

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

def dfs(sy, sx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if S[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
    return dist
ans = 0
for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == '#':
            continue
        d = dfs(sy,sx)
        for i in range(H):
            for k in range(W):
                ans = max(ans,d[i][k])
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys
buf = sys.stdin.buffer

h, w = map(int, buf.readline().split())
map = ""
for _ in range(h):
    map += input() + "#"
#print(map)

n = h * (w + 1)
periods = [[] for _ in range(n)]
dir = [-w - 1, 1, -1, w + 1]
for i in range(n):
    if map[i] == "#":
        continue
    for d in dir:
        next_i = i + d
        if next_i < 0 or next_i >= n or map[next_i] == "#":
            continue
        periods[i].append(next_i)
#print(periods)

q = deque()
def bfs(now_i):
    for next_i in periods[now_i]:
        if con_cnt[next_i] == -1:
            con_cnt[next_i] = con_cnt[now_i] + 1
            q.append(next_i)
    #まだスタックが残っている場合、左から抜き出す
    if q:
        bfs(q.popleft())

start_points = [i for i, j in enumerate(periods) if len(j) > 0]
ans = 0
for start_point in start_points:
    con_cnt = [-1] * n
    con_cnt[start_point] = 0
    bfs(start_point)
    #print(con_cnt)
    ans = max(ans, max(con_cnt))

print(ans)

Submission status: Accepted

Solution code:
import queue

def bfs(h,w,sx,sy,maze):
    dx = (1,0,-1,0)
    dy = (0,1,0,-1)
    fal = -1
    mx = -1
    #距離の配列の初期化
    d = [[fal for i in range(w)] for j in range(h)]
    que = queue.Queue()
    #初期状態の代入
    que.put((sx,sy))
    d[sx][sy] = 0
    #キューが空になるまでループ
    while que.empty() == False:
        p = que.get()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                if maze[nx][ny] != "#" and d[nx][ny] == fal:
                    que.put((nx,ny))
                    d[nx][ny] = d[p[0]][p[1]] + 1
                    if d[nx][ny] > mx:
                        mx = d[nx][ny]
    return mx

def main():
    h,w = map(int,input().split())
    maze = []
    mx = -1
    for i in range(h):
        maze.append(list(input()))
    for i in range(h):
        for j in range(w):
            if maze[i][j] != "#":
                ans = bfs(h,w,i,j,maze)
                if ans > mx:
                    mx = ans
    print(mx)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#151_D
import queue
h, w = map(int, input().split())
c = [input() for _ in range(h)]
inf = 10 ** 4
 
def bfs(sx,sy):
    d = [[-inf]*w for _ in range(h)]
    que = queue.Queue()
    que.put([sx,sy])
    d[sx][sy] = 0
    res = 0
    while not que.empty():
        qx, qy = que.get()
        for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
            px, py = qx+dx, qy+dy
            if 0<=px<h and 0<=py<w and c[px][py]=='.' and d[px][py]== -inf:
                que.put([px,py])
                d[px][py] = d[qx][qy]+1
                res = max(d[px][py], res)
    return res            

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

Submission status: Accepted

Solution code:
import numpy as np
H, W=map(int, input().split())
S=np.array([list(input()) for _ in range(H)])
INF=-1
#print(S)
def bfs(sx,sy):
  #dx, dy 四方向に対応したベクトルのリスト
  dx=[1,0,-1,0]
  dy=[0,1,0,-1]
  #P: (x, y)のキュー
  P=[]
  #d: スタートから各点までの最小距離の配列
  d=np.ones((H, W))*INF
  #スタート地点をキューに入れ、その点の距離を0にする
  P.append([sx, sy])
  d[sx,sy]=0
    
  #キューがからになるまでループ
  while len(P)>0:
    #キューの先頭を取り出す
    p=P.pop(0)
    #取り出してきた状態がゴールなら探索をやめる
    """
    if (p[0]==gx and p[1]==gy):
      break
    """
        
    #移動四方向をループ
    for i in range(4):
      #移動した後の点をnx, nyとする
      nx=p[0]+dx[i]
      ny=p[1]+dy[i]
            
      #移動が可能かどうかの判定とすでに訪れたことがあるかどうかの判定（d[nx, ny]!=INFならおtpずれたことがある）
      if 0<=nx and nx<H and 0<=ny and ny<W and S[nx, ny]!="#" and d[nx, ny]==INF:
        #移動できるならキューに入れ、その点の距離をpからの距離＋１で確定する
        P.append([nx, ny])
        d[nx, ny]=d[p[0], p[1]]+1
  """
  #print(d)
  if d[gx,gy]!=INF:
    result=d[gx, gy]
  else:
    result=0
  """
  result=d.max()
  return result
ans=0
Tlen=H*W
for sx in range(H):
  for sy in range(W):
    if S[sx,sy]=="#":
      continue
    res=bfs(sx,sy)
    ans=max(ans, res)
"""
for i in range(Tlen):
  for j in range(i,Tlen):
    sx,sy=i%H, int(i//H)
    gx,gy=j%H, int(j//H)
    
    if S[sx,sy]=="#" or S[gx,gy]=="#":
      continue
    res=bfs(sx,sy,gx,gy)
    ans=max(ans, res)
"""
"""
for sx in range(H):
  for sy in range(W):
    for gx in range(H):
      for gy in range(W):
        if S[sx,sy]=="#" or S[gx,gy]=="#":
          continue
        res=bfs(sx,sy,gx,gy)
        ans=max(ans, res)
"""
print(int(ans))

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
maze = [input() for _ in range(h)]
from collections import deque
D = [(0,1),(1,0),(-1,0),(0,-1)]
ans = 0
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      continue
    queue  = deque([(i,j,0)])
    checked = [[0 for _ in range(w)] for _ in range(h)]
    checked[i][j] = 1
    while queue:
      j,k,d = queue.popleft()
      for dx,dy in D:
        x,y = j+dx,k+dy
        if not(0<=x<h) or not(0<=y<w):
          continue
        if maze[x][y] == '#':
          continue
        if checked[x][y]:
          continue
        checked[x][y] = d+1
        queue.append((x,y,d+1))
    for j in range(h):
      for k in range(w):
        if checked:
          ans = max(ans,checked[j][k])

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  #　返り値
  va = 0
  while queue:
    y,x = queue.popleft()
    #　返り値に関する条件
    if visited[y][x] > va :
      va = visited[y][x]
    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])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1,w+1):
    if maze[sy][sx] == '#' :
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  #　返り値
  va = 0
  while queue:
    y,x = queue.popleft()
    #　返り値に関する条件
    if visited[y][x] > va :
      va = visited[y][x]
    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])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    if maze[sy][sx] == '#' :
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque

def bfs(maze, visited, sy, sx):
  queue = deque([[sy, sx]])
  visited[sy][sx] = 0
  va = 0
  while queue:
    y,x = queue.popleft()
    if visited[y][x] > va :
      va = visited[y][x]
    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])
  return va

h,w = map(int,input().split())
wall = ''
for i in range(w+2):
  wall += '#'
maze = [wall]
for i in range(h) :
  m1 = input()
  maze.append('#'+m1+'#')
maze .append(wall)

ans = []
for sy in range(1,h+1) :
  for sx in range(1+w+1):
    if maze[sy][sx] == '#' :
      continue
    visited = [[-1]*(w+2) for _ in range(h+2)]
    ans.append(bfs(maze, visited, sy, sx))

print(max(ans))

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input()for _ in range(h)]
inf=float("inf")
ans=0
for i in range(h):
      for j in range(w):
            if S[i][j]==".":
                  dp=[[inf for _ in range(w)]for _ in range(h)]
                  dp[i][j]=0
                  que=deque([(i,j)])
                  while que:
                        si,sj=que.popleft()
                        for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                              if 0<=ni<h and 0<=nj<w and S[ni][nj]!='#':
                                    if dp[ni][nj]>dp[si][sj]+1:
                                          dp[ni][nj]=dp[si][sj]+1
                                          que.append((ni,nj))
                                          ans=max(ans,dp[si][sj]+1)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy

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


# h x w のマップのリストを整形
t_tmp = []
for i in range(h):
    tmp = []
    for j in range(w):
        tmp.append(s[i][j])
    t_tmp.append(tmp)

minmax = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        
        # 現在地とその距離
        q = deque([(i,j,0)])

        # スタートを設定してsをコピー
        t = copy.deepcopy(t_tmp)
        #print(t)
        t[i][j] = '#'
        while q:
            x,y,c = q.popleft()
            for dx, dy in [(1,0),(0,1),(-1,0),(0,-1)]:
                # 壁を超えるか否か
                nx, ny = x+dx, y+dy
                if 0<=nx<h and 0<=ny<w and t[nx][ny] == '.':
                    t[nx][ny] = '#'
                    q.append((nx,ny,c+1))

        #print(mx)
        minmax = max(minmax,c)

print(minmax)

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
m = nsn(h)

dist = [[inf] * (h * w) for _ in range(h * w)]
dx, dy = [0, 1, -1, 0], [1, 0, 0, -1]
for i in range(h):
    for j in range(w):
        for k in range(4):
            ni, nj = i + dy[k], j + dx[k]
            if ni >= 0 and ni < h and nj >= 0 and nj < w and m[ni][nj] != '#' and m[i][j] != '#':
                dist[i * w + j][ni * w + nj] = 1
        dist[i * w + j][i * w + j] = 0

def floyd_warshall(n, dist):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k])

floyd_warshall(h * w, dist)

ans = 0
for i in range(h * w):
    for j in range(h * w):
        if dist[i][j] != inf:
            ans = max(ans, dist[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)]
inf=float('inf')
ans=0
for i in range(h):
      for j in range(w):
            if S[i][j]!='#':
                  dp=[[inf for _ in range(w)]for _ in range(h)]
                  dp[i][j]=0
                  que=deque([(i,j)])
                  while que:
                        si,sj=que.popleft()
                        for ni,nj in [(si+1,sj),(si-1,sj),(si,sj+1),(si,sj-1)]:
                              if 0<=ni<h and 0<=nj<w and S[ni][nj]!='#':
                                    if dp[ni][nj]>dp[si][sj]+1:
                                          dp[ni][nj]=dp[si][sj]+1
                                          ans=max(ans,dp[si][sj]+1)
                                          que.append((ni,nj))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
INF = 5000
vx = [-1,0,1,0]
vy = [0,-1,0,1]

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

d = [-1] * (H*W)
xy = lambda x,y: x + y*W

ds = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '#': continue
        q = deque([(sx,sy)])
        tmpd = d.copy()
        tmpd[xy(sx,sy)] = 0
        while(q):
            x,y = q.popleft()
            for i in range(4):
                nx = x + vx[i]
                ny = y + vy[i]
                if 0 <= nx and nx < W and 0 <= ny and ny < H and S[ny][nx] != '#' and tmpd[xy(nx,ny)] == -1:
                    q.append((nx,ny))
                    tmpd[xy(nx,ny)] = tmpd[xy(x,y)] + 1
        ds.append(max(tmpd))
print(max(ds))

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
S = list()
for i in range(H):
    S.append(list(input()))
mx = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "#":
            continue
        q = deque([(i,j,0)])
        T = [[S[k][l] for l in range(W)] for k in range(H)]
        T[i][j] = "#"
        while q:
            x,y,c = q.popleft()
            for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                nx,ny = x+dx,y+dy
                if 0 <= nx < H and 0 <= ny < W and T[nx][ny] == ".":
                    T[nx][ny] = "#"
                    q.append((nx,ny,c+1))
        mx = max(mx,c)
print(mx)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
INF = 1000000
def bfs(sx, sy):
    reached = [[INF for _ in range(w)] for _ in range(h)]
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    d = deque()
    d.append([sx, sy])
    reached[sx][sy] = 0
    while d:
        x, y = d.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx > h - 1 or ny < 0 or ny > w - 1 or maze[nx][ny] =="#" or reached[nx][ny] != INF:
                continue
            d.append([nx, ny])
            reached[nx][ny] = reached[x][y] + 1
    
    gl = 0
    for i in range(h):
        for j in range(w):
            if reached[i][j] != INF:
                gl = max(gl, reached[i][j])
    return gl

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

Submission status: Accepted

Solution code:
from collections import deque

h,w = [int(x) for x in input().split()]
m = []
for _ in range(h):
    m.append(list(input()))

def bfs(sy,sx):
    res = [[-1]*(w) for i in range(h)]
    res[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    dis = 0
    while q:
        z = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny = z[0] + dy
            nx = z[1] + dx
            if 0<=ny<h and 0<=nx<w and m[ny][nx]=="." and res[ny][nx]==-1:
                q.append([ny,nx])
                res[ny][nx] = res[z[0]][z[1]] + 1
                dis = res[ny][nx]
    return dis

ans = -1
for i in range(h):
    for j in range(w):
        if m[i][j] == ".":
            ret = bfs(i,j)
            if ret > ans:
                ans = ret
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from scipy.sparse.csgraph import floyd_warshall

def solve():
  h,w = (int(i) for i in input().split())
  maze = ["#"*(w+2)]
  for i in range(h):
    maze.append("#" + input() + "#")
  maze.append("#"*(w+2))

  dist = [(1,0),(0,1),(-1,0),(0,-1)]
  d = [[0]*500 for _ in range(500)]
  for y in range(1,h+1):
    for x in range(1,w+1):
      if maze[y][x] == ".":
        for dy,dx in dist:
          if maze[y+dy][x+dx] == ".":
            oldy = x + w*y
            inty = x+dx + w*(y+dy)
            d[inty][oldy] = 1
            d[oldy][inty] = 1
  ans = 0
  d = floyd_warshall(d)
  for i in range(500):
    for j in range(500):
      if d[i][j] < 10**15:
              ans = max(d[i][j],ans)
  print(int(ans))




solve()

Submission status: Accepted

Solution code:
import queue


def get_longest(s_tmx, i, j, h, w):
    q = queue.Queue()
    q.put((i, j))
    dist_mtx = [[-1] * w for a in range(h)]
    dist_mtx[i][j] = 0
    while not q.empty():
        pnt = q.get()
        y = pnt[0]
        x = pnt[1]
        if x - 1 >= 0 and dist_mtx[y][x-1] == -1 and s_mtx[y][x-1] == 1:
            dist_mtx[y][x-1] = dist_mtx[y][x] + 1
            q.put((y, x-1))
        if y - 1 >= 0 and dist_mtx[y-1][x] == -1 and s_mtx[y-1][x] == 1:
            dist_mtx[y-1][x] = dist_mtx[y][x] + 1
            q.put((y-1, x))
        if x < w - 1 and dist_mtx[y][x+1] == -1 and s_mtx[y][x+1] == 1:
            dist_mtx[y][x+1] = dist_mtx[y][x] + 1
            q.put((y, x+1))
        if y < h - 1 and dist_mtx[y+1][x] == -1 and s_mtx[y+1][x] == 1:
            dist_mtx[y+1][x] = dist_mtx[y][x] + 1
            q.put((y+1, x))
    ret = 0
    for item in dist_mtx:
        for item_item in item:
            if item_item > ret:
                ret = item_item
    return ret


h, w = map(int, input().split())
s_mtx = []

for i in range(h):
    s_list = [0] * w
    tmp = input()
    for j in range(len(tmp)):
        if tmp[j] == ".":
            s_list[j] = 1
        else:
            s_list[j] = 0
    s_mtx.append(s_list)

ret = 0

for i in range(h):
    for j in range(w):
        if s_mtx[i][j] == 1:
            tmp = get_longest(s_mtx, i, j, h, w)
            if tmp > ret:
                ret = tmp

print(ret)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

h,w = mi()
meiro = []
meiro.append("#"*(w+2))
for i in range(h):
    lis = "#" + input() + "#"
    meiro.append(lis)
#print(meiro[1][1])
meiro.append("#"*(w+2))

inf = 10 **4
aa = [1,0,-1,0]
ab = [0,1,0,-1]
ans = 0

from collections import deque
for i in range(1,h+1):
    for k in range(1,w+1):
        if meiro[i][k] == "#":
            continue
        dp = [[inf]*(w+2) for _ in range(h+2)]
        dp[i][k] = 0
        que = deque()
        que.append((i,k,0))
        while que:
            hh, ww,num = que.popleft()
            for l in range(4):
                hnext = hh + aa[l]
                wnext = ww + ab[l]
                if meiro[hnext][wnext] != "#" and dp[hnext][wnext] > (num +1):
                    dp[hnext][wnext] = num+1
                    que.append((hnext,wnext,num+1))
        ans = max(ans,num)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def dfs(field, s):
    MOVE = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    q = deque([(0, s)])
    dist = [[-1] * w for _ in range(h)]

    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '#':
                continue
            if dist[ni][nj] != -1:  #既に訪問済みの場合はスルー
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j


h, w = map(int, input().split())
field = [input() for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '.':
            d, i, j = dfs(field, (i, j))
            ans = max(ans, d)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque

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

# 方針
# まずはスタート地点を固定し、移動回数を最小にして歩いたときの最大移動回数をbfs関数で求める
# ついでスタート地点を動かして、当の最大移動回数の最大値をとる
def bfs(maze, visited, sy, sx):

    visited[sy][sx] = 0
    # queueの要素について、そこから周囲4方向を模索する
    # queueには、これから周囲4方向を模索すべき地点が格納されている
    queue = deque([[sy, sx]])

    while queue:
        y, x = queue.popleft()
        for dy, dx in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            ny, nx = y + dy, x + dx
            if 0 <= ny < H and 0 <= nx < W and \
                    maze[ny][nx] == "." and visited[ny][nx] == -1:
                visited[ny][nx] = visited[y][x] + 1
                queue.append([ny, nx])

    return np.amax(visited)

ans = -1
for i in range(H):
    for j in range(W):
        sy, sx = i, j
        # (i,j)地点に到達するのにかかった歩数を(i,j)成分に記録する用のリストvisited
        visited = [[-1] * W for _ in range(H)]
        if maze[sy][sx] == '.':
            ans = max(ans, bfs(maze, visited, sy, sx))

print(ans)

Submission status: Accepted

Solution code:
# import bisect
# import copy
# import fractions
# import math
import numpy as np
from collections import Counter, deque
# from itertools import accumulate,permutations, combinations,combinations_with_replacement,product

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

    def bfs(maze, visited, sy, sx):
        queue = deque([[sy, sx]])

        visited[sy][sx] = 0
        while queue:
            y, x = queue.popleft()
            for dy, dx in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y + dy, x + dx
                if 0<=ny<H and 0<=nx<W and \
                        maze[ny][nx] == "." and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x] + 1
                    queue.append([ny, nx])
        return np.amax(visited)

    ans=-1
    for i in range(H):
        for j in range(W):
            visited = [[-1] * W for _ in range(H)]

            sy,sx=i,j
            if maze[sy][sx]=='.':
                ans = max(ans,bfs(maze, visited, sy, sx))


    print(ans)
resolve()

Submission status: Accepted

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

maze = [['#']*(W+2)]
for i in range(H):
    maze.append(list('#'+input()+'#'))
maze.append(['#']*(W+2))
ans = 0

for ii in range(1,H+1):
    for jj in range(1,W+1):
        if maze[ii][jj]=='#':continue
        temp = deque()
        temp.append([ii,jj])
        mazenum = [[0]*(W+2) for _ in range(H+2)]
        mazenum[ii][jj] = 0
        visited = [[False]*(W+2) for _ in range(H+2)]
        visited[ii][jj] = True


        while temp:
            p = temp.popleft()
            m = mazenum[p[0]][p[1]]
            for i, j in [[p[0]-1,p[1]], [p[0]+1, p[1]], [p[0],p[1]-1],[p[0],p[1]+1]]:
                if maze[i][j]=='.':
                    if not visited[i][j]:
                        temp.append([i, j])
                        mazenum[i][j] = m + 1
                        visited[i][j]= True        
        ans = max(ans, max(max(x) for x in mazenum))

print(ans)

Submission status: Accepted

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

from collections import deque

def bfs(sy, sx):
    q = deque([[sy, sx]])
    visited = [[-1]*W for _ in range(H)]
    visited[sy][sx] = 0
    while q:
        y, x = q.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+i, x+j
            if not 0 <= new_y < H or not 0 <= new_x < W:
                continue
            if S[new_y][new_x] ==  "." and visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x]+1
                q.append([new_y, new_x])
    return max(max(l) for l in visited)

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

Submission status: Accepted

Solution code:
from collections import deque

def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    ans = 0
    dh = [0,1,0,-1]
    dw = [1,0,-1,0]
    for h in range(H):
        for w in range(W):
            if S[h][w] == '#':
                continue
            dist = [[-1] * W for _ in range(H)]
            dist[h][w] = 0
            Q = deque([(h,w)])
            while Q:
                y, x = Q.popleft()
                for i in range(4):
                    nh = y + dh[i]
                    nw = x + dw[i]
                    if 0 <= nh < H and 0 <= nw < W and dist[nh][nw] == -1 and S[nh][nw] == '.':
                        dist[nh][nw] = dist[y][x] + 1
                        Q.append((nh,nw))
            for i in range(H):
                ans = max(ans, max(dist[i]))
                
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import queue
 
H, W = map(int,input().split())
MAP = []
INF = 10 ** 8
x = 0
y = 1
dx = [1,0,-1,0]
dy = [0,1,0,-1]
 
 
for _ in range(H):
    MAP.append(list(input()))
 
def bfs(S):
    que = queue.Queue()
    d = [[INF for i in range(W)] for j in range(H)]
    que.put(S)
    d[S[x]][S[y]] = 0
    
    while not que.empty():
        p = que.get()
        for i in range(4):
            nx = p[x] + dx[i]
            ny = p[y] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] != "#" and d[nx][ny] == INF:
                que.put([nx,ny])
                d[nx][ny] = d[p[x]][p[y]] + 1
    
    MAX = -1
    for i in range(H):
        for j in range(W):
            if d[i][j] != INF and MAX < d[i][j]:
                MAX = d[i][j]
    return MAX

ans = -1

for i in range(H):
    for j in range(W):
        if MAP[i][j] != "#":
            tmp = bfs([i,j])
            if ans < tmp:
                ans = tmp

print(ans)