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
import itertools

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

for i in range(H):
  w = list(input())
  labyrinth[i] = w
  for j in range(W):
    if w[j] == ".":
      points.append([j,i])

com = list(itertools.combinations(points,2))

#移動パターン
movex = [1,0,-1,0]
movey = [0,1,0,-1]

def shortest_path(sx,sy,labyrinth):
  INF = -(10 ** 6)

  x_length = W
  y_length = H
  distance = [[INF for i in range(x_length)] for j in range(y_length)]
  
  queue = deque()
  queue.append((sx,sy))
  distance[sy][sx] = 0
  
  #幅優先探索
  def bfs():
    #探索候補がある限り
    while len(queue) > 0:
      x,y = queue.popleft()

      #上下左右を探索
      for i in range(0, 4):
        nx = x + movex[i]
        ny = y + movey[i]
        #print(nx,ny)
        #探索迷路内であり
        if (0 <= nx and ny < y_length and 0 <= ny and nx < x_length):
          #通行可能かつ未到達であれば
          if (labyrinth[ny][nx] != "#"  and distance[ny][nx] == INF):
            queue.append((nx,ny))
            distance[ny][nx] = distance[y][x] + 1
    
    dismax = max(list(itertools.chain.from_iterable(distance)))

    return dismax
    
  return bfs()

path = 0

for i in range(len(points)):
  sx = points[i][0]
  sy = points[i][1]
  dist = shortest_path(sx,sy,labyrinth)
  if path < dist:
    path = dist
  
print(path)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import queue

H,W=map(int,input().split())
c=["#"*(W+2)]+["#"+input()+"#" for _ in range(H)]+["#"*(W+2)]

ans=0
e=True
for i in range(1,H+1):
    for g in range(1,W+1):
        if c[i][g]==".":
            MAX=0
            dist=[[-1]*(W+2) for _ in range(H+2)]
            que=queue.Queue()
            que.put((i,g))
            dist[i][g]=0

            while not que.empty():
                h,w=que.get()
                direction=[(0,-1),(0,1),(1,0),(-1,0)]
                for y,x in direction:
                    if c[h+y][w+x]=="." and dist[h+y][w+x]==-1:
                        que.put((h+y,w+x))
                        dist[h+y][w+x]=dist[h][w]+1
                        MAX=max(MAX,dist[h+y][w+x])
            ans=max(MAX,ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            visited = [[0 for _ in range(w)] for _ in range(h)]
            visited[i][j] = 1
            que = deque([])
            que.append((i, j, 0))
            while que:
                (x, y, cnt) = que.popleft()
                for (nx, ny) in (x+1,y), (x-1, y), (x, y+1), (x, y-1):
                    if 0<=nx<h and 0<=ny<w:
                        if s[nx][ny] == "." and visited[nx][ny] == 0:
                            que.append((nx, ny, cnt+1))
                            visited[nx][ny] = 1
            ans = max(ans, cnt)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def f(S, start):
    H = len(S)
    W = len(S[0])
    stack = [start]
    closed = set()
    r = 0
    while stack:
        next_stack = []
        for s in stack:
            if s in closed:
                continue
            closed.add(s)
            for d in (-1, 1):
                for p in ((s[0] + d, s[1]), (s[0], s[1] + d)):
                    if p in closed:
                        continue
                    if p[0] < 0 or H <= p[0] or p[1] < 0 or W <= p[1]:
                        continue
                    if S[p[0]][p[1]] == "#":
                        continue
                    next_stack.append(p)
        stack = next_stack
        r += 1
    return r - 1


def main():
    H, W = read_values()
    S = [input() for _ in range(H)]

    res = 0
    for h in range(H):
        for w in range(W):
            if S[h][w] == "#":
                continue
            res = max(res, f(S, (h, w)))
    print(res)

        
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
S = [input() for _ in range(h)]
inf = float("inf")
ans = 0

for i in range(h):
  for j in range(w):
    if S[i][j] == "#":
      continue
    D = [[inf for _ in range(w)] for _ in range(h)]
    D[i][j] = 0
    que = deque([(i, j)])
    while que:
      si, sj = que.popleft()
      for ni, nj in [(si+1, sj), (si-1, sj), (si, sj+1), (si, sj-1)]:
        if 0 <= ni < h and 0 <= nj < w and S[ni][nj] != "#":
          if D[ni][nj] > D[si][sj]+1:
            D[ni][nj] = D[si][sj]+1
            ans = max(ans, D[si][sj]+1)
            que.append((ni, nj))
            
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import copy

H, W = map(int, input().split())
maps2 = deque([deque(["#" for _ in range(W + 2)])])
MAX = 0

for _ in range(H):
    temp = deque(input())
    temp.appendleft("#")
    temp.append("#")
    maps2.append(temp)
maps2.append(deque(["#" for _ in range(W + 2)]))

for i in range(1, H + 1):
    for l in range(1, W + 1):
        if maps2[i][l] != "#":
            maps = copy.deepcopy(maps2)
            pos = [[i, l, 0]]
            maps[i][l] = "a"
            while len(pos) > 0:

                y, x, depth = pos.pop(0)
                if depth > MAX:
                    MAX = depth

                if maps[y + 1][x] == ".":
                    pos.append([y + 1, x, depth + 1])
                    maps[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    maps[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    maps[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    maps[y][x - 1] = "a"
print(MAX)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
H = H + 2
W = W + 2
grid = '#' * W
for i in range(H-2):
    grid += '#' + input() + '#'
grid += '#' * W

def bfs(start):
    INF = 10**9
    dist = [INF] * (H*W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            w = v + move
            if grid[w] == '#':
                continue
            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)

answer = max(bfs(v) for v in range(H*W) if grid[v]!='#')
print(answer)

Submission status: Accepted

Solution code:
from collections import deque

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

H += 2
W += 2

grid = "#" * W
for _ in range(H - 2):
    grid += "#" + input() + "#"
grid += "#" * W


def bfs(start):
    INF = 10 ** 9
    dist = [INF] * (H * W)
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.popleft()
        dv = dist[v]
        for move in (-1, 1, W, -W):
            # next place
            w = v + move
            # wall or not
            if grid[w] == "#":
                continue

            dw = dv + 1
            if dw >= dist[w]:
                continue
            dist[w] = dw
            q.append(w)

    return max(x for x in dist if x < INF)


answer = max(bfs(v) for v in range(H * W) if grid[v] != "#")
print(answer)

Submission status: Accepted

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

for i in range(w*h):
    mat[i][i] = 0

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '#':
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    #print(i,i,i,i,i,i,i,i,i)
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 0
tmp = []

for i in range(w*h):
    for j in range(w*h):
        """
        下記4行がないからWA生やした
        """
        if s[i//w][i%w] == '#':
            continue
        if s[j//w][j%w] == '#':
            continue
        ans = max(ans,mat[i][j])
        #if ans > mat[i][j]:
        #    tmp.append(mat[i][j])
            
print(ans)

Submission status: Accepted

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


"""
s_idx = [-1,-1]
g_idx = [-1,-1]

for i in range(h):
    for j in range(w):
        if s[i][j] == 'S':
            s_idx[0] = i
            s_idx[1] = j
        if s[i][j] == 'G':
            g_idx[0] = i
            g_idx[1] = j
"""

tate = [0,0,1,-1]
yoko = [-1,1,0,0]

mat=[[10**18 for i in range(w*h)] for j in range(w*h)]

for i in range(w*h):
    mat[i][i] = 0

for i in range(w*h):
    for j in range(4):
        next_idx = i + w*tate[j] + yoko[j]
        if next_idx < 0 or next_idx >= w*h:
            continue
        if i % w == 0:
            if j == 0:
                continue
        if i % w == w - 1:
            if j == 1:
                continue
        if s[next_idx//w][next_idx%w] == '#':
            mat[i][next_idx] = 10**18
        else:
            mat[i][next_idx] = 1

for i in range(w*h):
    #print(i,i,i,i,i,i,i,i,i)
    for x in range(w*h):
        for y in range(w*h):
            """
            if x == s_idx[0]*w+s_idx[1] and y == g_idx[0]*w+g_idx[1]:
                print(mat[x][y],mat[x][i] , mat[i][y],i)
            """
            mat[x][y] = min(mat[x][y], mat[x][i] + mat[i][y])
    
ans = 10**18
tmp = []

for i in range(w*h):
    for j in range(w*h):
        if s[i//w][i%w] == '#':
            continue
        if s[j//w][j%w] == '#':
            continue
        if ans > mat[i][j]:
            tmp.append(mat[i][j])
            
print(max(tmp))

Submission status: Accepted

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


if __name__ == '__main__':

    # make graph
    maze = []
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

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

    max_path = 0
    for i in range(H):
        for j in range(W):
            if maze[i][j] != '#':
                que = deque([[i, j]])
                dist = [[-1 for k in range(W)] for l in range(H)]
                dist[i][j] = 0
                while len(que) != 0:
                    h, w = que[0][0], que[0][1]
                    que.popleft()
                    for k in range(4):
                        if h + dy[k] < 0 or w + dx[k] < 0 or h + dy[k] >= H or w + dx[k] >= W:
                            continue
                        if maze[h + dy[k]][w + dx[k]] == '#':
                            continue
                        if dist[h + dy[k]][w + dx[k]] == -1:
                            dist[h + dy[k]][w + dx[k]] = dist[h][w] + 1
                            que.append([h + dy[k], w + dx[k]])

                max_dist = max(max(li) for li in dist)
                if max_dist > max_path:
                    max_path = max_dist

    print(max_path)

Submission status: Accepted

Solution code:
from collections import deque

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

s = ["#"*(w+2)]
for i in range(h):
    si = "#"+input()+"#"
    s.append(si)
s.append("#"*(w+2))
nb = [(-1,0),(1,0),(0,1),(0,-1)]
inf = 10000
def bfs(x_,y_):
    dist = [[inf for i in range(w+2)] for j in range(h+2)]
    Q = deque()
    dist[x_][y_] = 0
    Q.append((x_,y_))
    while Q:
        x,y = Q.popleft()
        for u,v in nb:
            if s[x+u][y+v]!="#":
                if dist[x+u][y+v]>dist[x][y]+1:
                    dist[x+u][y+v]=dist[x][y]+1
                    Q.append((x+u,y+v))
    res = -1
    for i in range(h+2):
        for j in range(w+2):
            if dist[i][j]<inf:
                res = max(res,dist[i][j])
    return res
ans = 0
for i in range(1,h+1):
    for j in range(1,w+1):
       if s[i][j]!="#":###
            ans = max(ans,bfs(i,j))
print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def bfs(maze, x, y):
    m = [1, 0, -1, 0]
    n = [0, 1, 0, -1]
    queue = deque([[x, y]])
    dist = [[-1] * (w + 2) for _ in range(h + 2)]
    dist[x][y] = 0

    while queue:
        sx, sy = queue.popleft()

        for dx, dy in zip(m, n):
            nx = sx + dx
            ny = sy + dy
            if maze[nx][ny] != '#' and dist[nx][ny] == -1:
                queue.append([nx, ny])
                dist[nx][ny] = dist[sx][sy] + 1

    return max(max(x) for x in dist)


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

maze = [['#'] * (w + 2)]
for i in range(h):
    maze.append(['#'] + list(map(str, input())) + ['#'])

maze.append(['#'] * (w + 2))

ans = 0
for sy in range(1, w + 1):
    for sx in range(1, h + 1):
        if maze[sx][sy] != '#':
            ans = max(ans, bfs(maze, sx, sy))

print(ans)

Submission status: Accepted

Solution code:
import queue


class Solution:

    def solve(self, H: int, W: int, S) -> int:

        def onEdge(pos):
            i = pos[0]
            j = pos[1]
            if 0 < i and i < H - 1 and 0 < j and j < W - 1:
                return False
            else:
                return True

        def bfs(start):
            INF = H*W+1
            dist = {}
            for i in range(H):
                for j in range(W):
                    dist[(i, j)] = INF

            max_dist = 0

            dist[start] = 0
            nexts = queue.Queue()
            nexts.put(start)

            while not nexts.empty():
                __next = nexts.get()

                # if onEdge(__next):
                max_dist = max(dist[__next], max_dist)

                for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    h = __next[0] + delta[0]
                    w = __next[1] + delta[1]

                    if h < 0 or h > H - 1 or w < 0 or w > W - 1:
                        continue

                    if S[h][w] != "#":
                        if dist[(h, w)] == INF:
                            nexts.put((h, w))
                            dist[(h, w)] = dist[__next] + 1

            return max_dist

        ans = 0
        for i in range(H):
            for j in range(W):

                # skip if (i,j) is not on the edge
                # if not onEdge((i, j)):
                #     continue

                # skip if (i,J) is a wall
                if S[i][j] == "#":
                    continue

                ans = max(bfs((i, j)), ans)

        return ans


if __name__ == '__main__':

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

    # solve
    solution = Solution()
    print(solution.solve(H, W, S))

Submission status: Accepted

Solution code:
from collections import deque
import numpy as np


def bfs(maze, sx, sy):
    H = len(maze)
    W = len(maze[0])

    dist = np.zeros((H, W), dtype=int)
    dist[:, :] = -1

    q = deque([(sx, sy)])
    dist[sx, sy] = 0

    while q:
        x, y = q.popleft()
        d = dist[x, y]
        for dx, dy in [[1,0],[0,1],[-1,0],[0,-1]]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny]=="." and dist[nx, ny] == -1:
                q.append((nx, ny))
                dist[nx, ny] = d+1
    return dist.max()


def main():
    H, W = [int(x) for x in input().split()]

    maze = [input() for _ in range(H)]

    ans = 0
    for sx, sy in [(x, y) for x in range(H) for y in range(W) if maze[x][y] == "."]:
        ans = max(ans, bfs(maze, sx, sy))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
h,w=map(int,input().split())
h += 2
w += 2
s="#"*w
for _ in range(h-2):
    s += "#" + input() + "#"
s += "#"*w
def bfs(start):
    que=deque([start])
    INF=10**9
    dis=[INF]*(w*h)
    dis[start]=0
    move=(1,-1,w,-w)
    while que:
        v=que.popleft()
        for i in move:
            n=v+i
            if s[n]=="#":
                continue
            dv=dis[v]
            dn=dv+1
            if dis[n] <= dv+1:
                continue
            dis[n]=dn
            que.append(n)
    return max(i for i in dis if i<INF)
ans=max(bfs(v) for v in range(h*w) if s[v] != "#")
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import copy


def bfs(start, s):
    h = len(s)
    w = len(s[0])
    distance = 0
    maze = [[-1] * w for _ in range(h)]
    maze[start[0]][start[1]] = 0
    s[start[0]][start[1]] = "#"
    drcs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    q = deque()
    q.append(start)
    while(q):
        cr, cc = q.popleft()
        for dr, dc in drcs:
            nr, nc = cr + dr, cc + dc
            if nr < 0 or nc < 0 or nr >= h or nc >= w:
                continue
            if s[nr][nc] == ".":
                q.append([nr, nc])
                s[nr][nc] = "#"
                maze[nr][nc] = maze[cr][cc] + 1
                if maze[nr][nc] > distance:
                    distance = maze[nr][nc]
                    goal = [nr, nc]
    return goal, distance
    


def main():
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    for r in range(h):
        if "." in s[r]:
            start = [r, s[r].index(".")]
    goal, distance = bfs(start, copy.deepcopy(s))
    _, res = bfs(goal, s)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            d = [[-1 for i in range(w)] for j in range(h)]
            que = []
            que.append([i, j])
            d[i][j] = 0

            while len(que) != 0:
                p = que.pop(0)
                for dx, dy in zip((1, 0, -1, 0), (0, 1, 0, -1)):
                    nx = p[0] + dx
                    ny = p[1] + dy
                    if 0 <= nx < h and 0 <= ny < w and S[nx][ny] != '#' and d[nx][ny] == -1:
                        que.append([nx, ny])
                        d[nx][ny] = d[p[0]][p[1]] + 1

            for _ in d:
                ans = max(ans, max(_))

print(ans)

Submission status: Accepted

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

from collections import deque

def bfs(sx, sy):  # 引数にはスタート地点を取る
    # 移動ベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    
    # 移動距離の記録
    d = [[-1]*w for _ in range(h)]
    d[sx][sy] = 0  # スタート地点を0に設定する
    
    # キュー
    que = deque([])
    que.append([sx, sy])  # スタート地点を追加する
    
    while que:
        # FIFO
        x, y = que.popleft()
        # 移動先
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 移動先がマップ内に収まっているか、
            # 壁ではないか、
            # 移動済みではないか、を確認する
            if (0 <= nx < h) and (0 <= ny < w) and \
                (field[nx][ny] != '#') and (d[nx][ny] == -1):
                # スタート地点からの距離を記録していく
                d[nx][ny] = d[x][y] + 1
                # 移動先をキューに追加する
                que.append([nx, ny])
                
    return d
  
  
import itertools

ans = 0
for i in range(h):
    for j in range(w):
        if field[i][j] == '#':
            continue
        d = bfs(i, j)
        ans = max(ans, max(itertools.chain(*d)))
        
print(ans)

Submission status: Accepted

Solution code:
import sys,collections

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  field=[S() for _ in range(h)]

  ans=0
  visited=[[-1 for __ in range(w)] for _ in range(h)]
  q=collections.deque()
  for i in range(h):
    for j in range(w):
      if field[i][j]=='#':
        continue
      q.append((i,j))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      visited[i][j]=0
      _ans=0
      while q:
        y,x=q.popleft()

        for dy,dx in ((-1,0),(0,1),(1,0),(0,-1)):
          ny=y+dy
          nx=x+dx
          if not 0<=ny<h:
            continue
          if not 0<=nx<w:
            continue
          if field[ny][nx]=='#':
            continue
          if visited[ny][nx]!=-1:
            continue
          _ans=visited[y][x]+1
          visited[ny][nx]=_ans
          q.append((ny,nx))
      ans=max(ans,_ans)
  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
from collections import deque

def bfs():
    d = [[-1] * C for i in range(R)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0

    while que:
        p = que.popleft()

        for i in range(4):
            nx = p[1] + dx[i]
            ny = p[0] + dy[i]

            if 0<=nx<C and 0<=ny<R and maze[ny][nx] != '#' and d[ny][nx]== -1:
                que.append((ny, nx))
                d[ny][nx] = d[p[0]][p[1]] + 1
    
    Max_d = 0
    for d1 in d:
        Max_d = max(Max_d, max(d1))

    return Max_d



R, C = map(int, input().split())
maze = [list(input()) for _ in range(R)]
ans = 0

for i in range(R):
    for j in range(C):
        if maze[i][j] == ".":
            sy = i
            sx = j
            ans = max(ans, bfs())

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
inf = 401
H,W=map(int,input().split(' '))
maze=[list(input()) for i in range(H)]
ans = 0
def short_long(a,b):
    q=deque()
    q.append((a,b))
    d=[[inf for i in range(W)] for j in range(H)]
    d[a][b]=0
    tmp = 0
    while q:
        x,y=q.popleft()
        for i,j in [(1,0),(-1,0),(0,1),(0,-1)]:
            nx,ny=x+i,y+j
            if 0<=nx<H and 0<=ny<W and maze[nx][ny]!='#' and d[nx][ny] == inf:
                q.append((nx,ny))
                d[nx][ny]=d[x][y]+1
                tmp = max(d[nx][ny],tmp)
    return tmp
for i in range(H):
    for j in range(W):
        if maze[i][j] =='.':
            ans =max(ans,short_long(i,j))
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	H, W = MAP()
	maze = [list(input()) for _ in range(H)]
	dp = [[INF]*W*H for _ in range(W*H)]

	for i in range(H*W):
		for j in range(H*W):
			if maze[i//W][i%W] == "#":
				continue
			if maze[j//W][j%W] == "#":
				continue
			if i == j:
				dp[i][j] = 0
			if i + W == j:
				dp[i][j] = 1
			if i + 1 == j:
				if i%W == W - 1:
					continue
				dp[i][j] = 1
			if i - W == j:
				dp[i][j] = 1
			if i - 1 == j:
				if i%W == 0:
					continue
				dp[i][j] = 1

	for i in range(W*H):
	    for j, c2 in enumerate(row[i] for row in dp):
	           for k, (c1, c3) in enumerate(zip(dp[j], dp[i])):
	               if c1 > c2+c3:
	                   dp[j][k] = c2+c3

	ma = 0
	for i in range(len(dp)):
		for j in range(len(dp[i])):
			if dp[i][j] == INF:
				continue
			ma = ma if ma > dp[i][j] else dp[i][j]

	print(int(ma))

if __name__ == "__main__":
	main()

Submission status: Accepted

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