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:
# from collections import deque

INF = float('inf')

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

point_list = []
for i in range(w*h):
    point_list.append([w*h]*w*h)
maze = []

Q = []

for i in range(h):
    tmp = list(input())
    maze.append(tmp)

for s_y in range(h):
    for s_x in range(w):
        if maze[s_y][s_x] == "#":
            continue
        check = []
        Q.append((s_y,s_x))
        check.append((s_y,s_x))
        point_list[s_x+s_y*w][s_x+s_y*w] = 0
        while Q:
            y, x = Q.pop(0)
            if y == 0:
                pass
            elif maze[y-1][x]=="#":
                pass
            else:
                point_list[s_x+s_y*w][x+(y-1)*w] = min(point_list[s_x+s_y*w][x+(y-1)*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y-1,x) in check:
                    pass
                else:
                    check.append((y-1,x))
                    Q.append((y-1,x))
                    

            if y == h-1 :
                pass
            elif maze[y+1][x]=="#":
                pass
            else:
                point_list[s_x+s_y*w][x+(y+1)*w] = min(point_list[s_x+s_y*w][x+(y+1)*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y+1,x) in check:
                    pass
                else:
                    check.append((y+1,x))
                    Q.append((y+1,x))
                    

            if x==0:
                pass
            elif maze[y][x-1]=="#":
                pass
            else:
                point_list[s_x+s_y*w][(x-1)+y*w] = min(point_list[s_x+s_y*w][(x-1)+y*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y,x-1) in check:
                    pass
                else:
                    check.append((y,x-1))
                    Q.append((y,x-1))
                    

            if x==w-1:
                pass
            elif maze[y][x+1]=="#":
                pass
            else:
                point_list[s_x+s_y*w][(x+1)+y*w] = min(point_list[s_x+s_y*w][(x+1)+y*w],point_list[s_x+s_y*w][x+y*w]+1)
                if (y,x+1) in check:
                    pass
                else:
                    check.append((y,x+1))
                    Q.append((y,x+1))
                    
max_list = []
for i in range(w*h):
    tmp = set(point_list[i])
    if min(tmp)==w*h:
        continue
    if w*h in tmp:
        tmp.remove(w*h)
    max_list.append(max(tmp))

ans = max(max_list)
print(ans)

Submission status: Accepted

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

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

for s_i in range(h):
    for s_j in range(w):
        if meiro[s_i][s_j] == "#":
            continue
        max_d = max(bfs(s_i,s_j), max_d)
print(max_d)

Submission status: Accepted

Solution code:
from collections import deque    
H,W = map(int, input().split())
maze = []
ans = 0
dist =[]
q = deque([])
tmp = 0

for i in range(H):
    maze.append(input())

for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        dist = [[-1]*W for i in range(H)] # 配列の初期化
        q.append([i,j]) #初期値挿入
        dist[i][j] = 0
        while(q):
            a,b = q.popleft()
            if a + 1 < H:
                if maze[a+1][b] == '.' and dist[a+1][b] == -1:
                    q.append([a+1, b])
                    dist[a+1][b] = dist[a][b] + 1
                    tmp = dist[a+1][b] 
            if a > 0:
                if maze[a-1][b] == '.' and dist[a-1][b] == -1:
                    q.append([a-1, b])
                    dist[a-1][b] = dist[a][b] + 1
                    tmp = dist[a-1][b]
            if b + 1 < W:
                if maze[a][b+1] == '.' and dist[a][b+1] == -1:
                    q.append([a, b+1])
                    dist[a][b+1] = dist[a][b] + 1
                    tmp = dist[a][b+1]
            if b > 0:
                if maze[a][b-1] == '.' and dist[a][b-1] == -1:
                    q.append([a, b-1])
                    dist[a][b-1] = dist[a][b] + 1
                    tmp = dist[a][b-1]
        ans = max(ans,tmp)


print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
S = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      maze[i][j] = float("inf")
      S.append([i, j])
    else:
      maze[i][j] = -1
def bfs(H, W, maze, S):
  ans = 0
  for sy, sx in S:
    maze1 = copy.deepcopy(maze)
    maze1[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]+1:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs(H, W, maze, S)

Submission status: Accepted

Solution code:
from collections import deque
import copy
def bfs():
  H, W = map(int, input().split())
  maze = [list(input()) for i in range(H)]
  S = []
  for i in range(H):
    for j in range(W):
      if maze[i][j] == ".":
        maze[i][j] = float("inf")
        S.append([i, j])
      else:
        maze[i][j] = -1
  ans = 0
  for k in range(len(S)):
    maze1 = copy.deepcopy(maze)
    maze1[S[k][0]][S[k][1]] = 0
    q = deque([[S[k][0],S[k][1]]])
    while q:
      y, x = q.popleft()
      for i, j in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
        nexty, nextx = y+i, x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        dist1 = maze1[nexty][nextx]
        if dist1 != -1:
          if dist1 > maze1[y][x]+1:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs()

Submission status: Accepted

Solution code:
import queue
import copy
 
H,W= map(int,input().split())
 
dy = [1,0,-1,0]
dx = [0,1,0,-1]

MAX_N = 0


L = [list(input()) for _ in range(H)]

for k in range(1,H+1):
    for l in range(1,W+1): 
        sy = k
        sx = l
        A = copy.deepcopy(L)
        # ↓だと、id(A)とid(L)は異なるが、id(A[0])とid(L[0])は同じになってしまう
        # A = copy.copy(L)
        # print(L)
        # print(id(A[0]),id(L[0]))

        if A[sy-1][sx-1] == '.':

            # FIFOキューの作成
            q = queue.Queue()
            q.put([sy-1,sx-1])
            
            # スタートを　0 にする
            A[sy-1][sx-1] = 0
            
            while not q.empty():
                # キューの先頭を取り出す
                tem = q.get()

                for i in range(4):
                    # 移動した後の座標をny,nxとおく
                    ny = tem[0] + dy[i]
                    nx = tem[1] + dx[i]
            
                    if (0<= ny < H) and (0<= nx < W) and A[ny][nx] == '.':
                        A[ny][nx] = A[tem[0]][tem[1]] + 1
                        if A[ny][nx] > MAX_N:
                            MAX_N = A[ny][nx]
                        q.put([ny,nx])

print(MAX_N)

Submission status: Accepted

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

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

def bfs(sy, sx):
    visited = [[-1]*w for i in range(h)]
    visited[sy][sx] = 0
    que = deque([[sy, sx]])
    while que:
        
        y,x = que.popleft()
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            next_y, next_x = y+i, x+j
            # print(visited)
            if next_y < 0 or next_x < 0 or next_y > h-1 or next_x > w-1:
                continue
            if SHWs[next_y][next_x] == '.' and (visited[next_y][next_x] == -1 or visited[next_y][next_x] > visited[y][x]+1):
                visited[next_y][next_x] = visited[y][x] + 1
                que.append([next_y, next_x])
    
    return np.amax(np.array(visited))

            
ans = 0
for sy in range(h):
    for sx in range(w):
        if SHWs[sy][sx] == '#':
            continue
        count = bfs(sy=sy, sx=sx)

        if count > ans:
            ans = count


print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()

Submission status: Accepted

Solution code:
from collections import deque


def solve(S, s):
    if S[s[0]][s[1]] != ".":
        return -1
    queue = deque([s])
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    visited[s[0]][s[1]] = 0
    while queue:
        y, x = queue.popleft()
        for j, k in ([1,0], [-1,0], [0,1], [0,-1]):
            new_y, new_x = y+j, x+k
            if new_x in range(W) and new_y in range(H) and S[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])
    res = -1
    for v in visited:
        for u in v:
            res = max(res, u)
    return res


H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = -1
for i in range(H):
    for l in range(W):
        ans = max(ans, solve(S, [i, l]))
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    visited[start[0]][start[1]] = True
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
    return distance


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    visited[start[0]][start[1]] = True
    while queue:
        x, y = queue.popleft()

        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
    return distance


answer = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp

print(answer)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [list(input()) for _ in range(H)]
from collections import deque
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          A[h][w]=0
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
        
    A = [a for b in A for a in b if a!=inf]
    ans = max(ans,max(A))
    
print(ans)

Submission status: Accepted

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

for i in range(h):
  for j in range(w):
    if l[i][j]=='.':
      if i!=0:
        if l[i-1][j]!='#':
          connection[i*w+j].append((i-1)*w+j)
      if i!=h-1:
        if l[i+1][j]!='#':
          connection[i*w+j].append((i+1)*w+j)
      if j!=0:
        if l[i][j-1]!='#':
          connection[i*w+j].append(i*w+j-1)
      if j!=w-1:
        if l[i][j+1]!='#':
          connection[i*w+j].append(i*w+j+1)

n=h*w
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
  return distance

ans=[]
for i in range(h*w):
  ans.append(max(bfs(i)))
print(max(ans))

Submission status: Accepted

Solution code:
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        """迷路の (start_row, start_col) マスから最も遠いマスへの移動回数"""
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        ret = -1
        for row in range(H):
            for col in range(W):
                if dist[row][col] != INF:
                    ret = max(ret, dist[row][col])
        return ret

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] != '#':
                ans = max(ans, bfs(start_row, start_col))
    return ans

print(d_maze_master())

Submission status: Accepted

Solution code:
from collections import deque


def adjacents(r, c):
    if r > 0:
        yield r - 1, c
    if r < h - 1:
        yield r + 1, c
    if c > 0:
        yield r, c - 1
    if c < w - 1:
        yield r, c + 1


def is_road(r, c):
    return s[r][c] == '.'


def bfs(r, c):
    inf = h * w

    q = deque()
    q.append((r, c))

    dist = [[inf] * w for _ in range(h)]
    dist[r][c] = 0

    while q:
        r, c = q.popleft()
        d = dist[r][c]
        for nr, nc in ((nr, nc) for nr, nc in adjacents(r, c) if is_road(nr, nc)):
            if dist[nr][nc] < inf:
                continue
            nd = d + 1
            dist[nr][nc] = nd
            q.append((nr, nc))

    return d


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

print(max(bfs(r, c) for r in range(h) for c in range(w) if is_road(r, c)))

Submission status: Accepted

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

def bfs(h,w):
  checked = [[False for i in range(W)] for j in range(H)]
  q = [(h,w,0)] if maze[h][w]=="." else []
  checked[h][w] = True
  g_n = 0
  while q:
    h_,w_,n = q.pop(0)
    g_n = max(n, g_n)
    for i,j in zip([0,0,-1,1],[-1,1,0,0]):
      if (0<=h_+i<H) and (0<=w_+j<W):
        if checked[h_+i][w_+j]: continue
        checked[h_+i][w_+j] = True
        if maze[h_+i][w_+j]==".": q.append((h_+i,w_+j,n+1))
  return g_n

n = 0
for i in range(H):
  for j in range(W):
    n = max(n, bfs(i,j))
print(n)

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
INF = -1
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[INF for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "#" and visited[nx][ny] == INF:
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist
ans = -1
for x in range(H):
    for y in range(W):
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x, y))
print(ans)

Submission status: Accepted

Solution code:
def d_maze_master():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[-1 for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == -1:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '#':
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '#':
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline

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


def bfs(grid, start):
    distance = [[0] * W for _ in range(H)]
    queue = deque([start])
    visited = [[False] * W for _ in range(H)]
    visited[start[0]][start[1]] = True
    while queue:
        x, y = queue.popleft()

        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + j, x + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if grid[new_x][new_y] == '.' and not visited[new_x][new_y]:
                    distance[new_x][new_y] = distance[x][y] + 1
                    visited[new_x][new_y] = True
                    queue.append((new_x, new_y))
    return distance


answer = 0
limit = H - 1 + W - 1
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue

        cnt = 0
        for dx, dy in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = dy + j, dx + i
            if 0 <= new_y < W and 0 <= new_x < H:
                if S[new_x][new_y] == '.':
                    cnt += 1

        if cnt > 2:
            continue

        tmp = max(map(max, bfs(S, (i, j))))
        if tmp > answer:
            answer = tmp
        if answer == limit:
            print(answer)
            exit()

print(answer)

Submission status: Accepted

Solution code:
def d_maze_master(INF=float('inf')):
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Maze = [list(input()) for _ in range(H)]

    def bfs(start_row, start_col):
        diff = ((-1, 0), (0, 1), (1, 0), (0, -1))

        def is_inside(row, col):
            return 0 <= row < H and 0 <= col < W

        queue = deque([(start_row, start_col)])
        dist = [[INF for _ in range(W)] for _ in range(H)]
        dist[start_row][start_col] = 0
        while queue:
            row, col = queue.pop()
            for dr, dc in diff:
                nr, nc = row + dr, col + dc
                if is_inside(nr, nc) and Maze[nr][nc] != '#' and dist[nr][nc] == INF:
                    queue.appendleft((nr, nc))
                    dist[nr][nc] = dist[row][col] + 1
        return dist

    ans = 0
    for start_row in range(H):
        for start_col in range(W):
            if Maze[start_row][start_col] == '#':
                continue
            dist = bfs(start_row, start_col)
            for row in range(H):
                for col in range(W):
                    if Maze[row][col] != '#':
                        ans = max(ans, dist[row][col])
    return ans

print(d_maze_master())

Submission status: Accepted

Solution code:
import math
import sys

def f(s):
    return -2 \
        if s=='#' else -1


def dfs(s_x,s_y):
    tmp=[[s[i][j] for j in range(w)] for i in range(h)]
    tmp[s_x][s_y]=0
    que=[[s_x,s_y]]
    que_next=[]
    level=-1
    while que!=[]:
        level+=1
        for p in que:

            px,py=p[0],p[1]

            for q in [[px+1,py],[px-1,py],[px,py+1],[px,py-1]]:
                qx,qy=q[0],q[1]
                if (qx>=0 and qx<h) and (qy>=0 and qy<w) and tmp[qx][qy]==-1:
                    tmp[qx][qy]=0
                    que_next.append(q)


        que=[que_next[i] for i in range(len(que_next))]
        que_next=[]
    return level



h,w=map(int,input().split())
s=[[] for i in range(h)]
for i in range(h):
    p=input()
    s[i]=[f(p[j]) for j in range(w)]

ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==-1:
            ans=max(ans,dfs(i,j))

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 numpy as np
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j]=='#':
      continue
    inf = 10**5
    A = [[inf]*W for _ in range(H)]
    A[i][j]=0
    q = deque([[i,j]])
    while q:
      a = q.popleft()
      x=a[0]
      y=a[1]
      b = A[x][y]
      for m in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]]:
        h = m[0]
        w = m[1]
        if (h<0)or(h>H-1)or(w<0)or(w>W-1):
          continue
        if S[h][w]=='#':
          continue
        c = b+1
        if c>=A[h][w]:
          continue
        A[h][w]=c
        q.append([h,w])
      
    A = np.array(A)
    ans = max(ans,max(A[A<10**5]))
    
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
from collections import deque
H, W = map(int, input().split())
INF = -1
maze = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp[:])

def bfs(sx, sy):
    visited = [[INF for _ in range(W)] for _ in range(H)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    q = deque()
    q.append([sx, sy])
    visited[sx][sy] = 0
    while q:
        p = q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W:
                if maze[nx][ny] != "#" and visited[nx][ny] == INF:
                    q.append([nx, ny])
                    visited[nx][ny] = visited[p[0]][p[1]] + 1
        dist = -1
        for i in range(H):
            dist = max(dist, max(visited[i]))
    return dist
ans = -1
for i in range(H):
    for j in range(W):
        x, y = i, j
        if maze[x][y] == "#":
            continue
        ans = max(ans, bfs(x, y))
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

H, W = map(int, readline().split())
S = [list(readline().decode('utf-8').rstrip()) for _ in range(H)]


def adjacent_4(h, w):
    ret = []
    for (dh, dw) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        h_ = h + dh
        w_ = w + dw

        if (0 <= h_) & (h_ < H) & (0 <= w_) & (w_ < W):
            ret.append((h_, w_))
    return ret


def bfs(S, h, w):

    visited = [[10**9] * W for _ in range(H)]
    visited[h][w] = 1

    que = deque()
    que.append((h, w))

    while len(que) != 0:
        h_, w_ = que.popleft()
        acc = visited[h_][w_]

        for adj_h, adj_w in adjacent_4(h_, w_):
            if S[adj_h][adj_w] == '#':
                continue
            acc_ = acc + 1
            if acc_ >= visited[adj_h][adj_w]:
                continue
            visited[adj_h][adj_w] = acc_
            que.append((adj_h, adj_w))

    return max(visited[h][w] for h in range(H)
               for w in range(W) if visited[h][w] != 10**9) - 1


"""
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        ans = max(ans, bfs(S, h, w))
"""
ans = max(bfs(S, h, w) for h in range(H) for w in range(W) if S[h][w] != '#')
print(int(ans))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

H,W = map(int,input().split(' '))
MAP = [None]*H
for i in range(H):
    MAP[i] = list(input())

ANS = 0

dxy = [(0,1),(1,0),(0,-1),(-1,0)]

import queue
q = queue.Queue()

for i in range(H):
    for j in range(W):
        st = MAP[i][j]
        if st=='#': continue
        dist = [[0]*W for i in range(H)]
        visited = [[0]*W for i in range(H)]
        visited[i][j] = 1
        q.put([i,j])
        while not q.empty():
            y,x = q.get()
            for dy,dx in dxy:
                ny,nx = y+dy,x+dx
                if not (0<=nx<W): continue
                if not (0<=ny<H): continue
                if visited[ny][nx]: continue
                if MAP[ny][nx] == '#': continue
                visited[ny][nx] = 1
                dist[ny][nx] = dist[y][x] + 1
                q.put([ny,nx])
        ANS = max(ANS, max(max(row) for row in dist))
print(ANS)

Submission status: Accepted

Solution code:
# D - Maze Master

from collections import deque

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

# ある地点を渡すと、その地点から到達可能かつ距離未計算の地点のリストを返す
def not_investigated_positions(current_position):
    output = []
    for udrl in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
        y = current_position[0]+udrl[0]
        x = current_position[1]+udrl[1]
        if 0 <= y <= H-1 and 0 <= x <= W-1:
            if S[y][x] == "." and distance[y][x] == -1:
                output.append([y, x])
    return output

ans = 0

for sy in range(H):
    for sx in range(W):
        if S[sy][sx] == "#":
            continue
        distance = [[-1]*W for _ in range(H)]
        current_position = [sy, sx]
        distance[sy][sx] = 0
        next_positions = deque()
        next_positions.append(current_position)

        while next_positions:
            current_position = next_positions.popleft()
            for q in not_investigated_positions(current_position):
                distance[q[0]][q[1]] = distance[current_position[0]][current_position[1]] + 1
                next_positions.append(q)

        ans = max(ans, max(map(max,distance)))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
maze = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]
ls = []
for i in range(H):
    tmp = list(input())
    maze.append(tmp)
    for j in range(W):
        if tmp[j] != "#":
            ls.append([i,j])
def bfs(sx,sy):
    INF = -1
    cost = [[INF]*W for _ in range(H)]
    P = deque()
    P.append([sx,sy])
    cost[sx][sy] = 0
    while len(P) != 0:
        p = P.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "#" and cost[nx][ny] == INF:
                P.append([nx,ny])
                cost[nx][ny] = cost[p[0]][p[1]]+1
    return cost
def solve():
    ans = 0
    for i in ls:
        sx,sy = i[0],i[1]
        cs = bfs(sx,sy)
        for k in range(len(cs)):
            if max(cs[k]) > ans:
                ans = max(cs[k])
    return ans
print(solve())