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 queue
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

H,W = LI()
S = [list(input()) for _ in range(H)]

def bfs(s):
    dist = [[-1]*W for _ in range(H)]
    h,w = s
    dist[h][w] = 0
    que = queue.Queue()
    que.put(s)
    while(not(que.empty())):
        h,w = que.get_nowait()
        for dh,dw in d:
            nh,nw = h+dh,w+dw
            if 0<=nh<H and 0<=nw<W and dist[nh][nw]==-1 and S[nh][nw]=='.':
                dist[nh][nw] = dist[h][w] + 1
                que.put([nh,nw])
    return dist[h][w]

def main():
    ans = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == '.':
                ans = max(ans,bfs([h,w]))
#                if (((h==0 or S[h-1][w]=='#') or (h==H-1 or S[h+1][w]=='#')) and 
#                        ((w==0 or S[h][w-1]=='#') or (w==W-1 or S[h][w+1]=='#'))):
#                    ans = max(ans,bfs([h,w]))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


ans = 0
for i in range(h):
    maze[i] = input()

INF = 1000
ans = 0


for sy in range(h):
    for sx in range(w):
        if maze[sy][sx] == '#':
            continue
        else:
            distance = [[-1 for i in range(w)] for j in range(h)]


        queue = []

        queue.insert(0, (sy, sx))

        distance[sy][sx] = 0

        while len(queue):
            y, x = queue.pop()

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '#' and distance[ny][nx] == -1:
                        queue.insert(0, (ny, nx))
                        distance[ny][nx] = distance[y][x] + 1

                        ans = max(ans, distance[ny][nx])

print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())

def clear_maze(sx, sy, maze):
    INF = -1
    field_x_length = len(maze[0])
    field_y_length = len(maze)
    distance = [[INF for i in range(field_x_length)]
                for j in range(field_y_length)]
    for i in range(field_y_length):
        for j in range(field_x_length):
            if maze[i][j] == '#':
                distance[i][j] = -100

    def bfs():
        queue = []
        queue.insert(0, (sx, sy))
        distance[sy][sx] = 0

        while len(queue):
            x, y = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1
        
        return distance
    return bfs()


S = [list(input()) for _ in range(h)]
ans = 0
cnt = 1
for i in range(h):
    for j in range(w):
        start = S[i][j]
        if start == '#':
            continue
            
        num = clear_maze(j, i, S)
        # print(num,cnt,j,i,S[i][j])
        cnt += 1
        for k in range(h):
            ans = max(ans, max(num[k]))
print(ans)

Submission status: Accepted

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


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# このグラフ構造の中で一番遠い連結成分では？
H, W = read_ints()
S = read_map(H)

# おとなしく深さ優先探索

mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)

from itertools import product, combinations
from collections import deque


def ret_shortest(si, sj):
    visited = [[False] * W for _ in range(H)]
    que = deque([(si, sj, 0)])
    visited[si][sj] = True

    ans = 0
    while que:
        i, j, cost = que.popleft()
        ans = max(ans, cost)
        for di, dj in zip(mvy, mvx):
            ni, nj = i + di, j + dj
            if not (-1 < ni < H) or not (-1 < nj < W):
                continue
            if S[ni][nj] == '.' and not visited[ni][nj]:
                que.append((ni, nj, cost + 1))
                visited[ni][nj] = True

    return ans


ans = 0

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

Submission status: Accepted

Solution code:

from itertools import chain

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
inf = float('inf')

def flatten(list_of_lists):
    "Flatten one level of nesting"
    return chain.from_iterable(list_of_lists)


def bfs(start, end):
    distance = [[inf for i in range(W)] for j in range(H)]
    queue = [(end, start)]
    distance[end][start] = 0

    while queue:
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if 0 <= nx < W and 0 <= ny < H and M[ny][nx] != '#' and distance[ny][nx] == inf:
                queue.insert(0, (ny, nx))
                distance[ny][nx] = distance[y][x] + 1
    return distance


m = 0
for i in range(W):
    for j in range(H):
        if M[j][i] != "#":

            for length in list(flatten(bfs(i, j))):
                if length != inf and m < length:
                    m = length

print(m)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import floyd_warshall


def main():
    H, W = map(int, input().split())
    S = []

    def get_index(h, w):
        return h * W + w

    for _ in range(H):
        S.append(input())

    l = [[0 for _ in range(H * W)] for _ in range(H * W)]
    for h in range(H):
        for w in range(W):
            if not S[h][w] == "#":
                if 0 <= h - 1 and S[h - 1][w] == ".":
                    l[get_index(h, w)][get_index(h - 1, w)] = 1
                if h + 1 < H and S[h + 1][w] == ".":
                    l[get_index(h, w)][get_index(h + 1, w)] = 1
                if 0 <= w - 1 and S[h][w - 1] == ".":
                    l[get_index(h, w)][get_index(h, w - 1)] = 1
                if w + 1 < W and S[h][w + 1] == ".":
                    l[get_index(h, w)][get_index(h, w + 1)] = 1

    #print(l)

    fw = floyd_warshall(l)
    #print(fw[0][3])
    ans = 0
    for i in range(H * W):
        for j in range(H * W):
            ans = max(ans, fw[i][j] if fw[i][j] < float("inf") else 0)
            # if ans == 7:
            #     print(i, j)

    print(int(ans))


main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
H,W=map(int,input().split())


def bfs(h,w,n):
    yoyaku=[]
    if h>0:
        if lis[h-1][w]>n+1 and mp[h-1][w]!="#":
            yoyaku.append([h-1,w,n+1])
    if w>0:
        if lis[h][w-1]>n+1 and mp[h][w-1]!="#":
            yoyaku.append([h,w-1,n+1])
    if h<H-1:
        if lis[h+1][w]>n+1 and mp[h+1][w]!="#":
            yoyaku.append([h+1,w,n+1])
    if w<W-1:
        if lis[h][w+1]>n+1 and mp[h][w+1]!="#":
            yoyaku.append([h,w+1,n+1])
    
    lis[h][w]=min(n,lis[h][w])
    return yoyaku

    

mp=[]
for _ in range(H):
    mp.append(list(input()))

ans=[]

for h in range(H):
    for w in range(W):
        lis=[[1000]*W for i in range(H)]
        que=[[[h,w,0]]] if mp[h][w]!="#" else []
        while True:
            if len(que)==0:
                break
            else:
                temp=que.pop(-1)
                #print(temp)
                for tem in temp:
                    
                    que.append(bfs(tem[0],tem[1],tem[2]))
        
        pre=0
        for item in lis:
            for tem in item:
                if tem==1000:
                    continue
                pre=max(pre,tem)    
        ans.append(pre)

    
print(max(ans))

Submission status: Accepted

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

town = []
visited = [[0 for i in range(W)] for j in range(H)]
 
for i in range(H): 
    c = input().strip()
    w = list(c)
    town.append(w)
            
def bfs(x,y) :
    q = deque()
    q.append([x,y,0])
    max_dist=0
    s=x
    t=y
    while q : #キューが空でない場合
        tx,ty,dist = q.popleft()
        if visited[ty][tx] == 0 :
            visited[ty][tx] = 1
            if town[ty][tx] == '#' :
                pass
            else :
                #周辺4マスを調べる
                for r in range (4):
                    nx = tx + dx[r]
                    ny = ty + dy[r]
                    count=0
                    if 0 <= nx < W and 0 <= ny < H and visited[ny][nx] == 0:
                        q.append([nx,ny,dist+1])
                        count+=1
                    if count==0 and dist>max_dist:
                        max_dist=dist
    return max_dist
                        
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
max_dist=0
for k in range(H):
    for l in range(W):
        max_dist=max(max_dist,bfs(l,k))
        visited = [[0 for i in range(W)] for j in range(H)]
print(max_dist)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())

S = list()
for i in range(H):
  S.append(list(map(lambda x: int(x == '.'), input())))

for i in range(H):
  S[i].append(0)
  S[i].append(0)
S.append([0 for _ in range(W + 2)])


def wfs(loc):
  moved = [
    [
      False for w in range(W + 2)
    ]
    for h in range(H + 2)
  ]
  queue = [(loc, 0)]
  ans = 0
  moved[loc[0]][loc[1]] = True
  while (queue):
    (h, w), move = queue.pop(0)
    for i, j in zip((1, -1, 0, 0), (0, 0, -1, 1)):
      _h, _w = h + i, w + j
      if not moved[_h][_w] and S[_h][_w] == 1:
        moved[_h][_w] = True
        queue.append(((_h, _w), move + 1))
    ans = max(ans, move)
  return ans

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

Submission status: Accepted

Solution code:

H, W = map(int, input().split())
edges = [[None for i in range(W)] for i in range(H)]

for i in range(H):
  s = list(map(str, input()))
  for j in range(W):
    edges[i][j] = s[j] 


def find_next(i, j):
  next = []
  if i > 0 and edges[i-1][j] == ".":
    next.append((i-1, j))
  if i < H - 1 and edges[i+1][j] == ".":
    next.append((i+1, j))
  if j > 0 and edges[i][j-1] == ".":
    next.append((i, j-1))
  if j < W - 1 and edges[i][j+1] == ".":
    next.append((i, j+1))
  return next

inf = 9999999999999999999

from collections import deque

def dfs(i, j):
  colors = [["white" for i in range(W)] for j in range(H)]
  queue = deque()
  queue.append((i, j))
  distance = [[inf for i in range(W)] for j in range(H)]
  distance[i][j] = 0

  result = -1
  while queue:
    i, j = map(int, queue.popleft())
    colors[i][j] = "black"
    for (x, y) in find_next(i, j):
      if colors[x][y] == "white":
        colors[x][y] = "gray"
        d = min(distance[i][j] + 1, distance[x][y])
        distance[x][y] = d
        result = max(result, d)
        queue.append((x, y))
  return result


ans = -1
for i in range(H):
  for j in range(W):
    if edges[i][j] == "#": 
      continue
    
    ans = max(ans, dfs(i, j))

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import deque
# h, w = map(int,input().split())
# maze = [list(input()) for i in range(h)]
# seen = [[-1]*w for _ in range(h)]
# move = [[1,0],[-1,0],[0,1],[0,-1]]
# # start = [0,0]
# start = [2,2]
# g = [4,5]
# que = [start]
# seen[start[0]][start[1]] = 0
# que.append(start)
# while que:
#     y,x = que.pop(0)
#     if (y == g[0]) and (x == g[1]):
#         break
#     for i in range(len(move)):
#         ny,nx = y+move[i][0], x+move[i][1]
#         if (0 <= ny < h) and (0 <= nx < w):
#             if maze[ny][nx] == '.':
#                 if seen[ny][nx] == -1:
#                     seen[ny][nx] = seen[y][x]+1
#                     que.append([ny,nx])

# print(seen[])

def bfs(maze, visited, sy, sx):
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        # if [y, x] == [gy, gx]:
            # return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if (0<=new_y<len(maze)) and (0<=new_x<len(maze[0])):
                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 visited

h, w = map(int, input().split())
maze = [input() for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if (maze[i][j] == '.'):
            sy,sx = i,j
            visited = [[-1]*w for j in range(h)]
            vi = bfs(maze,visited,sy,sx)
            a = np.array(vi).flatten().max()
            ans = max(ans, a)
# sy,sx = 0,0
# visited = [[-1]*w for j in range(h)]
# r = bfs(maze, visited, sy, sx)
print(ans)

Submission status: Accepted

Solution code:
def dijkstra(si, sj):
  d=[[1000 for _ in range(W)] for _ in range(H)]
  d[si][sj]=0
  color=[]
  for i in range(H):
    tmp=[]
    for j in range(W):
      if S[i][j]=="#":
        tmp.append("BLACK")
      else:
        tmp.append("WHITE")
    color.append(tmp)
  pi, pj=0, 0
  while True:
    mincost=1000
    for i in range(H):
      for j in range(W):
        if color[i][j]!="BLACK" and d[i][j]<mincost:
          mincost=d[i][j]
          pi, pj=i, j
    if mincost==1000:
      break
    color[pi][pj]="BLACK"
    if pi>0 and S[pi-1][pj]=="." and color[pi-1][pj]!="BLACK" and d[pi][pj]+1<d[pi-1][pj]:
      d[pi-1][pj]=d[pi][pj]+1
      color[pi-1][pj]="GRAY"
    if pi<H-1 and S[pi+1][pj]=="." and color[pi+1][pj]!="BLACK" and d[pi][pj]+1<d[pi+1][pj]:
      d[pi+1][pj]=d[pi][pj]+1
      color[pi+1][pj]="GRAY"
    if pj>0 and S[pi][pj-1]=="." and color[pi][pj-1]!="BLACK" and d[pi][pj]+1<d[pi][pj-1]:
      d[pi][pj-1]=d[pi][pj]+1
      color[pi][pj-1]="GRAY"
    if pj<W-1 and S[pi][pj+1]=="." and color[pi][pj+1]!="BLACK" and d[pi][pj]+1<d[pi][pj+1]:
      d[pi][pj+1]=d[pi][pj]+1
      color[pi][pj+1]="GRAY"
  maxV=0
  for i in range(H):
    for j in range(W):
      if d[i][j]<1000:
        maxV=max(maxV, d[i][j])
  return maxV
  
H, W=map(int, input().split())
S=[input() for _ in range(H)]
ans=0
for i in range(H):
  for j in range(W):
    if S[i][j]==".":
      ans=max(ans, dijkstra(i, j))
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from itertools import product
import numpy as np
def solve():
    H, W = map(int, input().split())
    M = np.zeros((H,W), dtype=int)
    for h in range(H):
        M[h] = np.array(list(int(x=='.') for x in input()))

    Dist = float('inf')*np.ones((H*W, H*W))
    
    u = M&np.roll(M, 1, axis=0)&np.concatenate((np.zeros((1,W), dtype=int),np.ones((H-1,W), dtype=int)), axis=0)
    d = M&np.roll(M, -1, axis=0)&np.concatenate((np.ones((H-1,W), dtype=int),np.zeros((1,W), dtype=int)), axis=0)
    l = M&np.roll(M, 1, axis=1)&np.concatenate((np.zeros((H,1), dtype=int),np.ones((H,W-1), dtype=int)), axis=1)
    r = M&np.roll(M, -1, axis=1)&np.concatenate((np.ones((H,W-1), dtype=int),np.zeros((H,1), dtype=int)), axis=1)

    hu, wu = np.where(u)
    Dist[hu*W+wu, (hu-1)*W+wu] = 1
    hd, wd = np.where(d)
    Dist[hd*W+wd, (hd+1)*W+wd] = 1
    hl, wl = np.where(l)
    Dist[hl*W+wl, hl*W+wl-1] = 1
    hr, wr = np.where(r)
    Dist[hr*W+wr, hr*W+wr+1] = 1
    for v3 in range(H*W):
        Dist = np.minimum(Dist, Dist[:,v3:v3+1] + Dist[v3:v3+1,:])
    
    Dist[Dist==float('inf')] = -1
    Dist[np.arange(H*W),np.arange(H*W)] = -1

    return str(int(Dist.max()))

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
H,W=map(int, input().split())
S = [input() for i in range(H)]
m=H*W
l=[[None]*m for i in range(m)]
L=[0]*m
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            L[i*W+j]=1
for i in range(m):
    for j in range(m):
        if L[i] and L[j]:
            if i==j:
                l[i][j]=0
            elif abs(i-j)==W:
                l[i][j]=1
            elif i-j==1 and i%W!=0:
                l[i][j]=1
            elif j-i==1 and j%W!=0:
                l[i][j]=1
            else:
                l[i][j]=400
for i in range(m):
    if L[i]:
        for j in range(m):
            if L[j]:
                for k in range(m):
                    if L[k]:
                        if l[i][j]+l[i][k]<l[j][k]:
                            l[j][k]=l[i][j]+l[i][k]
M=0
for i in l:
    for j in i:
        if j:
            if M<j:
                M=j
print(M)

Submission status: Accepted

Solution code:
def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        dist_max = 0 
        while len(queue):
            y, x = queue.pop()
#             if x == gx and y == gy:
#                 # ゴール座標と一致するなら
#                 break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist_max
 
    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]
 
    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

R , C = [int(i) for i in input().split()]
c = [input() for _ in range(R)]

ans = 0
for sy in range(1, R+1):
    for sx in range(1, C+1):
        if c[sy-1][sx-1] != '#':
            count_tmp = C_BFS(R, C, sy, sx, 1, 1, c)
            if ans < count_tmp:
                ans = count_tmp
print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = False
def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]
    MOD = 10**9+7

    H,W = LMIIS()
    S = [input() for _ in range(H)]
    # print(S)

    def tansaku(S,V,y,x,length):

        
        if  x >= 1 and S[y][x-1] == '.' and V[y][x-1] > length+1:
            V[y][x-1] = length+1
            tansaku(S,V,y,x-1,length+1)


        if x < W-1 and S[y][x+1] == '.' and V[y][x+1] > length+1:
            V[y][x+1] = length+1
            tansaku(S,V,y,x+1,length+1)


        if y >= 1 and S[y-1][x] == '.' and V[y-1][x] > length+1:
            V[y-1][x] = length+1
            tansaku(S,V,y-1,x,length+1)


        if y < H-1 and S[y+1][x] == '.' and V[y+1][x]> length+1:
            V[y+1][x] = length+1
            tansaku(S,V,y+1,x,length+1)

        return
    
    def getmax():
        max_length = 0
        for h in range(H):
            for w in range(W):
                V = [[MOD] * W for _ in range(H)]
                if S[h][w] == '.':
                    V[h][w] = 0
                    tansaku(S,V,h,w,0) 
                for v in V:
                    v = list(map(lambda x:x%MOD,v))
                    max_length = max(v+[max_length])
                    # print(V)
        return max_length
    
    print(getmax())
    






if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
import copy
import sys
#import numpy as np
sys.setrecursionlimit(410000)

INF = 10**6

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

def solve(sy,sx):
  d = [[INF]*w for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if maze[i][j] == '#':
        d[i][j] = -INF          
  
  que = deque()
  que.append([sx,sy])
  d[sy][sx]=0

  while len(que)>0:
    px,py = que.popleft()

    for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
      nx = px + dx
      ny = py + dy

      if (0 <= nx and nx < w and 0<=ny and ny < h) \
          and maze[ny][nx] != '#' \
          and (d[ny][nx] == INF or d[ny][nx] > d[py][px] +1):              
        que.append((nx,ny))
        d[ny][nx] = d[py][px] +1

  return d

ans = 0
for sy in range(h):
  for sx in range(w):
    maze = copy.deepcopy(org_maze)
    if maze[sy][sx] == '.':      
      f = solve(sy,sx)      
      for i in range(h):        
        ans = max(ans,max(f[i]))
          
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
ans=0
for y in range(h):
    for x in range(w):
        b=[[0]*w for _ in range(h)]
        if a[y][x]==".":
            now=deque([(y,x)])
            while len(now)!=0:
                Y,X=now.popleft()
                for i,j in [[0,1],[0,-1],[1,0],[-1,0]]:
                    if 0<=Y+i<=h-1 and 0<=X+j<=w-1:
                        if a[Y+i][X+j]=="." and b[Y+i][X+j]==0 and (Y+i!=y or X+j!=x):
                            b[Y+i][X+j]=b[Y][X]+1
                            now.append((Y+i,X+j))
            c=0                
            for i in b:
                d=max(i)
                c=max(d,c)
            ans=max(ans,c)     
            # print(b)
print(ans)

Submission status: Accepted

Solution code:
def clear_maze(sx, sy, maze):

    INF = float("inf")

    field_x_length = len(maze)
    field_y_length = len(maze[0])
    distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sx][sy] = 0

        while len(queue):
            x, y = queue.pop()


            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length:
                    try:
                        if maze[nx][ny] != '#' and distance[nx][ny] == INF:
                            queue.insert(0, (nx, ny))
                            distance[nx][ny] = distance[x][y] + 1
                    except Exception as e:
                        print(nx, ny)
                        print(maze)
                        print(maze[nx][ny])
                        print(distance)
                        exit()
        res = 0
        for x in range(field_x_length):
            for y in range(field_y_length):
                if distance[x][y] < float("inf"):
                    res = max(res, distance[x][y])
        return res

    return bfs()


H, W = map(int, input().split())
maze = []
for w in range(H):
    maze.append([x for x in input()])
ans = 0
for h in range(H):
    for w in range(W):
        if maze[h][w] == ".":
            sx, sy = h, w
            ans = max(clear_maze(sx,sy, maze),ans)
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def solve(maze, st_tuple):
    st_row, st_col = st_tuple
    W, H = len(maze[0]), len(maze)
    visited = [[0 for _ in range(W)] for __ in range(H)]
    steps = [[0 for _ in range(W)] for __ in range(H)]
    q = deque()
    q.append((st_row, st_col, 0))
    visited[st_row][st_col] = 1
    steps[st_row][st_col] = 0
    while q:
        cur_row, cur_col, count = q.popleft()
        for dr, dc in zip(DR, DC):
            next_row = cur_row + dr
            next_col = cur_col + dc
            if 0 <= next_row < H and 0 <= next_col < W:
                pass
            else:
                continue
            if maze[next_row][next_col] == '#':
                continue
            if visited[next_row][next_col]:
                continue
            q.append((next_row, next_col, count + 1))
            visited[next_row][next_col] = 1
            steps[next_row][next_col] = count + 1
    max_count = 0
    for r in range(H):
        for c in range(W):
            max_count = max(max_count, steps[r][c])
    return max_count

def main():
    H, W = LI()
    maze = []
    for _ in range(H):
        maze.append(S())
    num = 0
    axes = [(s_r, s_c) for s_r in range(H) for s_c in range(W)]
    for st_row, st_col in axes:
        if maze[st_row][st_col] == '#':
            continue
        a = solve(maze, (st_row, st_col))
        num = max(num, a)
    print(num)
main()

Submission status: Accepted

Solution code:
from collections import deque
ddx = [0, 0, -1, 1]
ddy = [-1, 1, 0, 0]

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

res = 0
inf = 9999999
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        dist = [[inf]*w for _ in range(h)]
        dist[i][j] = 0
        que = deque([[i, j]])
        while len(que):
            y, x = que.popleft()
            for dx, dy in zip(ddx, ddy):
                if x+dx < 0 or x+dx >= w or y+dy < 0 or y+dy >= h or s[y+dy][x+dx] == '#' or dist[y+dy][x+dx] < inf:
                    continue
                que.append([y+dy, x+dx])
                dist[y+dy][x+dx] = dist[y][x] + 1
        ma = 0
        for k in range(h):
            for l in range(w):
                if dist[k][l] < inf:
                    ma = max(ma, dist[k][l])
        res = max(ma, res)
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import copy

def display(masu):
    for m in masu:
        string = ''
        for mm in m:
            string += mm
        print(string)

[H, W] = [int(i) for i in input().split()]

S = []
for h in range(H):
    s = input()
    S.append(list(s))

# スタート地点になり得る地点
start_position = []
for i in range(len(S)):
    for j in range(len(S[i])):
        if S[i][j] == '.':
            start_position.append((i, j))

max_distance = 0
for (i, j) in start_position:
    masu = copy.deepcopy(S)
    #print('{}, {}'.format(i, j))
    masu[i][j] = '*'
    now_position = [(i, j)]
    distance = -1
    while len(now_position) > 0:
        distance += 1
        new_position = []
        for (i, j) in now_position:
            # 上
            if i > 0:
                if masu[i-1][j] == '.':
                    new_position.append((i-1, j))
                    masu[i-1][j] = '*'
            # 下
            if i < H-1:
                if masu[i+1][j] == '.':
                    new_position.append((i+1, j))
                    masu[i+1][j] = '*'
            # 左
            if j > 0:
                if masu[i][j-1] == '.':
                    new_position.append((i, j-1))
                    masu[i][j-1] = '*'
            # 右
            if j < W-1:
                if masu[i][j+1] == '.':
                    new_position.append((i, j+1))
                    masu[i][j+1] = '*'
        now_position = new_position

    #print(distance)
    if distance > max_distance:
        max_distance = distance

print(max_distance)

Submission status: Accepted

Solution code:
from scipy.sparse.csgraph import shortest_path
import numpy as np

H, W = map(int, input().split(" "))

M = np.zeros((H * W, H * W))

maiz = []

for _ in range(H):
    maiz.append(input())

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

def is_valid_move(r, c, dr, dc):
    nr = r + dr
    if not (nr >= 0 and nr < H):
        return False
    
    nc = c + dc

    if not (nc >= 0 and nc < W):
        return False

    if maiz[nr][nc] == '.':
        return True

    return False

for row, row_elem in enumerate(maiz):
    for col, col_elem in enumerate(row_elem):
        if col_elem == "#":
            continue
        for drow, dcol in move:
            if not (is_valid_move(row, col, drow, dcol)):
                continue

            M[row * W + col][(drow + row) * W + col + dcol] = 1
            M[(drow + row) * W + col + dcol][row * W + col] = 1


res = shortest_path(M)
res[res > 10000000000000000000000000] = 0

print(int(np.max(res)))