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
# sys.setrecursionlimit(10 ** 9)

# H, W = map(int, input().split())
# L = []
# for _ in range(H):
#     s = input()
#     a = []
#     for i in range(len(s)):
#         a.append(s[i])
#     L.append(a)

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


# def dfs(h, w, dp, ans, count):
#     if L[h][w] == '#':
#         return ans
#     elif (L[h][w] == '.' and dp[h][w] == -1):
#         dp[h][w] = 0

#     for i in range(4):
#         if w + dx[i] >= 0 and w + dx[i] < W and h + \
#                 dy[i] >= 0 and h + dy[i] < H:
#             if L[h + dy[i]][w + dx[i]] == '.' and dp[h + dy[i]][w + dx[i]] == -1:
#                 count += 1
#                 ans[h + dy[i]][w + dx[i]
#                                ] = min(ans[h + dy[i]][w + dx[i]], count)
#                 return dfs(h + dy[i], w + dx[i], dp, ans, count)
#             elif L[h + dy[i]][w + dx[i]] == '#':
#                 continue

#     return ans


# max_count = 0
# ans = [[100000000] * W for _ in range(H)]
# for i in range(H):
#     for j in range(W):
#         dp = [[-1] * W for _ in range(H)]
#         count = dfs(i, j, dp, ans, 0)
#         print(count)
#         # max_count = max(max_count, count)

# print(max_count)

# 幅優先探索
from collections import deque
H, W = map(int, input().split())
L = []
for _ in range(H):
    s = input()
    a = []
    for i in range(len(s)):
        a.append(s[i])
    L.append(a)

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


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

        return dp


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

Submission status: Accepted

Solution code:
from collections import deque
import itertools

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


# x,yはスタートの座標
def bfs(x, y):
    # 最初は全て未訪問なので-1で初期化
    d = [[-1] * w for _ in range(h)]
    # スタート地点への距離は0
    d[x][y] = 0
    q = deque([(x, y)])
    while q:
        tx, ty = q.popleft()
        # 右、上、左、下
        for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            nx, ny = tx + dx, ty + dy
            # グリッドの範囲(縦方向, 横方向)内、通路(壁ではない)、未訪問(== -1)の場合
            if 0 <= nx < h and 0 <= ny < w and g[nx][ny] == '.' and d[nx][ny] < 0:
                d[nx][ny] = d[tx][ty] + 1
                q.append((nx, ny))
    # 最終的なdを平坦化して最大値を返す
    return max(list(itertools.chain.from_iterable(d)))


# 全てのマスについて
max_count = 0
for x in range(h):
    for y in range(w):
        # スタートが通路であるかチェックする必要がある
        if g[x][y] == ".":
            max_count = max(max_count, bfs(x, y))

print(max_count)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10000)
H, W = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(l, d, cnt):
  tmp = []
  for n in l:
    i, j = n[0], n[1]
    if (0<i) and (S[i-1][j] == '.'):
      if d[i-1][j] > d[i][j]+1:
        d[i-1][j] = d[i][j]+1
        tmp.append([i-1, j])
    if (i<H-1) and (S[i+1][j] == '.'):
      if d[i+1][j] > d[i][j]+1:
        d[i+1][j] = d[i][j]+1
        tmp.append([i+1, j])
    if (0<j) and (S[i][j-1] == '.'):
      if d[i][j-1] > d[i][j]+1:
        d[i][j-1] = d[i][j]+1
        tmp.append([i, j-1])
    if (j<W-1) and (S[i][j+1] == '.'):
      if d[i][j+1] > d[i][j]+1:
        d[i][j+1] = d[i][j]+1
        tmp.append([i, j+1])
  if tmp == []:
    return cnt
  else:
    cnt += 1
    return main(tmp, d, cnt)
  
ans = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == '.':
      d = [[float('inf') for i in range(W)] for j in range(H)]
      d[i][j] = 0
      cnt = main([[i, j]], d, 0)
      ans = max(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
#幅優先探索
import copy
H,W=map(int,input().split())
MAZE=[0]*H
for i in range(H):
  MAZE[i]=list(str(input()))

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

def solve_maze(sy,sx):
  #多次元配列はdeepcopyを使わないといけない
  MAZE1=copy.deepcopy(MAZE)
  MAZE1[sy][sx]='#'
  queue=[]
  queue.append([sy,sx])
  d=[[100000000]*W for i in range(H)]
  d[sy][sx]=0
  while len(queue)>0:
    #Qを取り出す
    Q=queue.pop(0)
    move=d[Q[0]][Q[1]]

    #4方向をループする
    for j in range(4):
      y=Q[0]+dy[j]
      x=Q[1]+dx[j]
      if 0<=y<=(H-1) and 0<=x<=(W-1) and MAZE1[y][x] == '.':
        queue.append([y,x])
        MAZE1[y][x] = '#'
        d[y][x] = move+1
  return move

d_max=0
for i in range(H):
  for j in range(W):
    if MAZE[i][j]=='.':
      d=solve_maze(i,j)
      if d>d_max:
        d_max=d
print(d_max)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys
import copy


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


class Maze:
    def __init__(self, base_map, H, W):
        self.H = H
        self.W = W
        self.maze = base_map

        reachable = []
        for i in range(self.H):
            for j in range(self.W):
                reachable.append([i, j])

        self.reachable = reachable

    def solve(self):
        ans = 0
        for start in self.reachable:
            max_cost = self.calc_cost(start)
            ans = max(ans, max_cost)

        print(ans)

    def isNotReachable(self, i, j):
        return i < 0 or i >= self.H or j < 0 or j >= self.W or self.maze[i][j] == -1

    def calc_cost(self, start):
        costs = copy.deepcopy(self.maze)
        deque = cl.deque([])
        deque.append(start)
        ways = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        visited = [[False for j in range(self.W)] for i in range(self.H)]
        visited[start[0]][start[1]] = True

        while len(deque) > 0:
            cur_point = deque.popleft()
            i, j = cur_point[0], cur_point[1]
            for way in ways:
                next_i = i + way[0]
                next_j = j + way[1]
                if self.isNotReachable(next_i, next_j) or visited[next_i][next_j]:
                    continue
                visited[next_i][next_j] = True
                costs[next_i][next_j] = costs[i][j] + 1
                deque.append([next_i, next_j])
        max_cost = 0
        for row in costs:
            max_cost = max(max_cost, *row)
        return max_cost


def main():
    H, W = MI()
    base_map = []
    for _ in range(H):
        row = input()
        row_in_num = []
        for j in range(len(row)):
            if row[j] == ".":
                row_in_num.append(0)
            else:
                row_in_num.append(-1)

        base_map.append(row_in_num)

    maze = Maze(base_map, H, W)
    maze.solve()


main()

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
ma = [["#" for _ in range(w+2)] for _ in range(h+2)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "#":
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i, j])
            while q:
                y, x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1, x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1, x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y, x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y, x-1])
            for l in range(h+2):
                ans = max(ans, max(p[l]))
            # ans = max(ans, max(max(p)))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
ma = [["#" for _ in range(w+2)] for _ in range(h+2)]
for i in range(h):
    tmp = list(input())
    for j in range(w):
        ma[i+1][j+1] = tmp[j]
ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if ma[i][j] == "#":
            continue
        elif ma[i][j] == ".":
            p = [[-1 for _ in range(w+2)] for _ in range(h+2)]
            p[i][j] = 0
            q = deque()
            q.append([i, j])
            while q:
                y, x = q.popleft()
                if ma[y+1][x] == "." and p[y+1][x] == -1:
                    p[y+1][x] = p[y][x] + 1
                    q.append([y+1, x])
                if ma[y-1][x] == "." and p[y-1][x] == -1:
                    p[y-1][x] = p[y][x] + 1
                    q.append([y-1, x])
                if ma[y][x+1] == "." and p[y][x+1] == -1:
                    p[y][x+1] = p[y][x] + 1
                    q.append([y, x+1])
                if ma[y][x-1] == "." and p[y][x-1] == -1:
                    p[y][x-1] = p[y][x] + 1
                    q.append([y, x-1])
            for l in range(1, h+1):
                ans = max(ans, max(p[l]))
            # ans = max(ans, max(max(p)))
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))


v=[[1,0],[-1,0],[0,1],[0,-1]]
h,w=mp()
grid=["#"*(w+2)]
ans=[]
for i in range(h):
    grid.append("#"+input()+"#")
grid.append("#"*(w+2))
for i in range(h*w):
    ch=[[0]*(w+2) for i in range(h+2)]
    if grid[i//w+1][i%w+1]==".":
        sx,sy=i//w+1,i%w+1
        que=deque([[sx,sy,0]])
        while len(que):
            q=que.popleft()
            ch[q[0]][q[1]]=1
            ans.append(q[2])
            for x,y in v:
                if grid[q[0]+x][q[1]+y]=="." and ch[q[0]+x][q[1]+y]==0:
                    ch[q[0]+x][q[1]+y]=1
                    que.append([q[0]+x,q[1]+y,q[2]+1])
            
print(max(ans))

Submission status: Accepted

Solution code:
import queue
def main():
    h, w = map(int, input().split())
    st = [[1]*(w+2) for _ in range(h+2)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                st[i+1][j+1] = 0
    ans = 0
    for i in range(1, h+2):
        for j in range(1, w+2):
            if st[i][j] == 0:
                fs = [[float("inf")]*(w+2) for _ in range(h+2)]
                q = queue.Queue()
                fs[i][j] = 0
                q.put([i, j])
                while not q.empty():
                    y, x = q.get()
                    if st[y-1][x] == 0 and fs[y-1][x] > fs[y][x] + 1:
                        fs[y-1][x] = fs[y][x] + 1
                        q.put([y-1, x])
                    if st[y+1][x] == 0 and fs[y+1][x] > fs[y][x] + 1:
                        fs[y+1][x] = fs[y][x] + 1
                        q.put([y+1, x])
                    if st[y][x-1] == 0 and fs[y][x-1] > fs[y][x] + 1:
                        fs[y][x-1] = fs[y][x] + 1
                        q.put([y, x-1])
                    if st[y][x+1] == 0 and fs[y][x+1] > fs[y][x] + 1:
                        fs[y][x+1] = fs[y][x] + 1
                        q.put([y, x+1])
                    if ans < fs[y][x]:
                        ans = fs[y][x]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def connect( v ):
    con_v = []
    if v[ 0 ] > 0:
        if s[ v[ 0 ] - 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] - 1, v[ 1 ] ) )
    if v[ 1 ] > 0:
        if s[ v[ 0 ] ][ v[ 1 ] - 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] - 1 ) )
    if v[ 0 ] < h - 1:
        if s[ v[ 0 ] + 1 ][ v[ 1 ] ] == ".":
            con_v.append( ( v[ 0 ] + 1, v[ 1 ] ) )
    if v[ 1 ] < w - 1:
        if s[ v[ 0 ] ][ v[ 1 ] + 1 ] == ".":
            con_v.append( ( v[ 0 ], v[ 1 ] + 1 ) )
    return con_v

from heapq import heappush, heappop
INF = 10 ** 10
VISITED = 1
NOT_VISITED = 0
def longest_bfs( i, j ):
    cost = [ INF for _ in range( h * w ) ]
    cost[ i * w + j ] = 0
    visit = [ NOT_VISITED for _ in range( h * w ) ]
    queue = [ ( 0, ( i, j ) ) ]
    while len( queue ) > 0:
        c, v = heappop( queue )
        visit[ v[ 0 ] * w + v[ 1 ] ] = VISITED
        for u in connect( v ):
            if visit[ u[ 0 ] * w + u[ 1 ] ] == VISITED:
                continue
            if cost[ u[ 0 ] * w + u[ 1 ] ] > cost[ v[ 0 ] * w + v[ 1 ] ] + 1:
                cost[ u[ 0 ] * w + u[ 1 ] ] = cost[ v[ 0 ] * w + v[ 1 ] ] + 1
                heappush( queue, ( cost[ u[ 0 ] * w + u[ 1 ] ], u ) )
    return cost

longest_path = 0
for i in range( h ):
    for j in range( w ):
        if s[ i ][ j ] == "#":
            continue
        path_length = longest_bfs( i, j )
        for p in path_length:
            if p < INF and p > longest_path:
                longest_path = p
print( longest_path )

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [input() for _ in range(h)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
def bfs(i, j):
    cost = [[-1 for _ in range(w)] for _ in range(h)]
    que = deque()
    cost[i][j] = 0
    que.append((i, j))
    if s[i][j] == '#':
        return 0
    while que:
        ni, nj = que.popleft()
        for k in range(4):
            if 0 <= ni+dy[k] < h and 0 <= nj+dx[k] < w:
                if cost[ni+dy[k]][nj+dx[k]] != -1:
                    continue
                if s[ni+dy[k]][nj+dx[k]] == '.':
                    cost[ni+dy[k]][nj+dx[k]] = cost[ni][nj]+1
                    que.append((ni+dy[k], nj+dx[k]))

    cc = 0
    for i in range(h):
        for j in range(w):
            if cost[i][j] > cc:
                cc = cost[i][j]
    return cc

ans = 0
for i in range(h):
    for j in range(w):
        cost = bfs(i, j)
        ans = max(ans, cost)

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
field = [list(input()) for _ in range(H)]
dist = [[-1]*W for _ in range(H)]
dx = [1,0,-1,0]
dy = [0,1,0,-1]
mx = 0
for h in range(H):
    for w in range(W):
        if field[h][w] == "#":
            continue
        dist = [[-1]*W for _ in range(H)]
        dist[h][w] = 0
        que = deque([])
        que.append([h,w])
        while que != deque([]):
            u,v = que.popleft()
            for dir in range(4):
                nu = u + dx[dir]
                nv = v + dy[dir]

                if (nu < 0) or (nu >= H) or (nv < 0) or (nv >= W):
                    continue
                if field[nu][nv] == "#":
                    continue
                if dist[nu][nv] != -1:
                    continue
            
                que.append([nu,nv])
                dist[nu][nv] = dist[u][v] + 1
            
            
        for i in range(H):
            for j in range(W):
                if mx < dist[i][j]:
                    mx = dist[i][j]
    
print(mx)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# input = sys.stdin.readline
# sys.setrecursionlimit(10**8)
# mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

h,w = inpm()
maze = inplL(h)

ans = 0
for sh in range(h):
    for sw in range(w):
        if maze[sh][sw] == '#':
            continue

        q = queue.Queue()
        q.put((sh,sw,0))

        field = [[-1]*w for i in range(h)]
        tmp = 0
        while not q.empty():
            yy,xx,kk = q.get()
            if field[yy][xx] >= 0: continue

            field[yy][xx] = kk
            if tmp < kk:
                gh,gw = (yy,xx)
                tmp = kk
            if yy != h-1 and maze[yy+1][xx] == '.':
                q.put((yy+1,xx,kk+1))
            if xx != w-1 and  maze[yy][xx+1] == '.':
                q.put((yy,xx+1,kk+1))
            if yy != 0 and  maze[yy-1][xx] == '.':
                q.put((yy-1,xx,kk+1))
            if xx != 0 and  maze[yy][xx-1] == '.':
                q.put((yy,xx-1,kk+1))
        ans = max(ans,field[gh][gw])

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
import sys
INFTY=sys.maxsize

def readinput():
    h,w=map(int,input().split())
    sMat=[]
    for _ in range(h):
        sMat.append(list(input()))
    nList=[]
    for _ in range(h*w):
        nList.append(set())
    for i in range(h):
        for j in range(w):
            if sMat[i][j]=='#':
                continue
            ij=i+j*h
            if i-1>=0 and sMat[i-1][j]=='.':
                nList[ij].add(ij-1)
            if i+1<h and sMat[i+1][j]=='.':
                nList[ij].add(ij+1)
            if j-1>=0 and sMat[i][j-1]=='.':
                nList[ij].add(ij-h)
            if j+1<w and sMat[i][j+1]=='.':
                nList[ij].add(ij+h)
    for i in range(h*w):
        nList[i]=list(nList[i])
    return h,w,nList

def dijkstra(s,n,nList):
    '''優先度付きキューを使用したダイクストラ法

    パラメーター
    s: 始点
    n: 頂点の数
    nList: [ 
        [vertex1, cost1], [vertex2, cost2], ...
        [vertex1, cost1], [vertex2, cost2], ...
        ...
    ]

    返り値
    d: 始点sから各頂点vまでの最短経路上の辺の重みの総和d[v]のリスト
    '''

    WHITE=0
    GRAY=1
    BLACK=2
    color=[WHITE]*n
    d=[INFTY]*n
    for i in range(h*w):
        if len(nList[i])==0:
            d[i]=0

    HQ=[]

    d[s]=0
    heappush(HQ,(d[s],s))

    while(len(HQ)>0):
        du,u=heappop(HQ)
        color[u]=BLACK

        if d[u]<du:
            continue

        for v in nList[u]:
            vw=1
            if color[v]!=BLACK:
                if d[u] + vw < d[v]:
                    d[v] = d[u] + vw
                    color[v]=GRAY
                    heappush(HQ, (d[v], v))
    return d

def main(h,w,nList):
    #print(nList)
    ans=0
    for i in range(h*w):
        if len(nList[i])>0:
            d=dijkstra(i,h*w,nList)
            #print(d)
            dmax=max(d)
            ans=max(ans,dmax)
    return ans

if __name__=='__main__':
    h,w,nList=readinput()
    ans=main(h,w,nList)
    print(ans)

Submission status: Accepted

Solution code:
from copy import deepcopy
from collections import Counter, defaultdict, deque
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]
def maze_solve(S_1,S_2,maze_list):
    d = deque()
    dist[S_1][S_2] = 0
    d.append([S_1,S_2])
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    while d:
        v = d.popleft()
        x = v[0]
        y = v[1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
    return max(list(map(lambda x: max(x), dist)))
h,w = MI()
ans = 0
maze = [list(input()) for _ in range(h)]
dist = [[-1]*w for _ in range(h)]
start_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == "#":
          dist[i][j] = 0
        else:
          start_list.append([i,j])
dist_copy = deepcopy(dist)
for k in start_list:
  dist = deepcopy(dist_copy)
  ans = max(ans,maze_solve(k[0],k[1],maze))
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    #N = int(input())
    H,W = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    S = tuple(input() for i in range(H)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    
    n=H*W
    inf=10000000

    def warshall_floyd():#n^3, 処理が軽いので多少ギリギリでも通る
        #d[i][j]: iからjへの最短距離
        #初期化
        d = [[inf]*n for i in range(n)] 
        for i in range(H):
            for j in range(W):
                if S[i][j]!=".":
                    continue
                for ni,nj in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
                    if 0<=ni<H and 0<=nj<W and S[ni][nj]==".":
                        d[i*W+j][ni*W+nj]=1
                        
        for i in range(n):
            d[i][i] = 0 #自身のところに行くコストは０
        for k in range(n):
            for i in range(n):
                for j in range(i+1,n):#無向グラフ,有向グラフの場合はrange(0,n)
                    x = min(d[i][j],d[i][k] + d[k][j])
                    d[i][j]=x
                    d[j][i]=x#無向グラフの場合
                # if i==j and d[i][i]<0: #負閉路がある場合
                #     return -1
        return d

    d=warshall_floyd()
    ans=0
    for i in range(H):
        for j in range(W):
            if S[i][j]!=".":
                continue
            for ni in range(H):
                for nj in range(W):
                    if d[i*W+j][ni*W+nj]<inf:
                        ans=max(ans,d[i*W+j][ni*W+nj])
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import sys
import copy

N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7


### BFS ###

nextH = [0, 1, 0, -1]
nextW = [1, 0, -1, 0]


def bfs(u, S):

    S[u[0]][u[1]] = 0  # state を変更

    q = deque()
    q.append(u)
    m = 0
    while q:
        u = q.popleft()
        for h, w in zip(nextH, nextW):
            h += u[0]
            w += u[1]
            if not (0 <= h < len(S) and 0 <= w < len(S[0])):
                continue

            if S[h][w] == '.':  # state を確認
                S[h][w] = S[u[0]][u[1]] + 1  # state を変更
                m = max(m, S[h][w])
                q.append((h, w))
    
    return m


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    S = []
    for _ in range(H):
        S.append([x for x in sys.stdin.readline().rstrip()])

    # print(S)

    m = 0
    for h in range(H):
        for w in range(W):
            D = copy.deepcopy(S)
            if S[h][w] == '.':
                m = max(m, bfs((h, w), D))

    print(m)


main()

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [0]*(H+2)
S[0] = ''.join(['#']*(W+2))
S[-1] = ''.join(['#']*(W+2))
for i in range(1,H+1):
  S[i] = '#'+input()+'#'

maxd = 0
import queue
dy = [1,0,-1,0]
dx = [0,1,0,-1]
for h in range(1,H+1):
  for w in range(1,W+1):
    if S[h][w]=='.':
      visited = [[False]*(W+2) for _ in range(H+2)]
      q = queue.Queue()
      visited[h][w] = True
      q.put([h,w,0])
      while not q.empty():
        a,b,c = q.get()
        #print(a,b,c)
        for i in range(4):
          y,x = a+dy[i], b+dx[i]
          if S[y][x]=='.' and visited[y][x]==False:
            q.put([y,x,c+1])
            visited[y][x]=True
      maxd = max(maxd,c)
print(maxd)

Submission status: Accepted

Solution code:
inf=float("inf")  


h,w=map(int,input().split())
s=[["#"]*(w+2) for i in range(h+2)]
for i in range(h):
    s[i+1]=["#"]+list(input())+["#"]

#h,w=3,5
#s=[['#', '#', '#', '#', '#', '#', '#'], ['#', '.', '.', '.', '#', '.', '#'], ['#', '.', '#', '.', '#', '.', '#'], ['#', '.', '#', '.', '.', '.', '#'], ['#', '#', '#', '#', '#', '#', '#']]    

nv=h*w
dp=[[inf]*nv for i in range(nv)] 

def nhw(hi,wi):
    return (hi-1)*w+wi-1

for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":
            continue
        vij=nhw(i,j)
        if s[i-1][j]==".":
            vij2=nhw(i-1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i+1][j]==".":
            vij2=nhw(i+1,j)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j-1]==".":
            vij2=nhw(i,j-1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
        if s[i][j+1]==".":
            vij2=nhw(i,j+1)
            dp[vij][vij2]=1
            dp[vij2][vij]=1
for i in range(nv):
    dp[i][i]=0
           
#print(dp)
for k in range(nv):
    for i in range(nv):
        for j in range(nv):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
#    print(dp)
#print(dp)
dpmax=0
for i in range(nv):
    for j in range(nv):
        if dp[i][j]!=inf:
            if dpmax<dp[i][j]:
                dpmax=dp[i][j]
print(dpmax)

Submission status: Accepted

Solution code:
"""
解法１：
startとgoalの組み合わせの全探索で調べる。
マス目の数は最大で400なので、組み合わせの数は最大で約160000.
各組み合わせごとにBFSで最短経路を調べるので、400回ループが必要。
なので計算時間としてはO(H^3W^3)

解法２：
ワーシャルフロイドで各ノードから各ノードへの最短経路を求める。
計算量としては、O(H^3W^3となる)。

解法１だとなんかTLEするので、解法２で行く。
"""

H,W = map(int,input().split())
MAP = [list(input()) for _ in range(H)]
dp = [[float("INF")]*(H*W) for _ in range(H*W)]
adjecents = [(1,0),(-1,0),(0,1),(0,-1)]

for i in range(H):
    for j in range(W):
        if MAP[i][j] == ".":
            pointer = i*W + j
            dp[pointer][pointer] = 0
            for a,b in adjecents:
                x = i + a
                y = j + b
                if 0<=x<H and 0<=y<W and MAP[x][y] == ".":
                    pointer2 = x*W + y
                    dp[pointer][pointer2] = 1

for i in range(H*W):
    for j in range(H*W):
        for k in range(H*W):
            dp[j][k] = min(dp[j][k],dp[j][i]+dp[i][k])

ans = 0
for i in range(H*W):
    for j in range(H*W):
        if dp[i][j] != float("INF"):
            ans = max(ans,dp[i][j])
print(ans)