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: Runtime Error

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


from collections import deque
def bfs(maze, dist, sy, sx):
    d = deque()
    d.append([sy, sx])
    while d:
        y, x = d.popleft()
        for dy, dx in [1, 0], [-1, 0], [0, 1], [0, -1]:
            ny = y + dy
            nx = x + dx
            if ny < 0 or ny >= H or nx < 0 or nx >= W:
                continue
            if maze[ny][nx] == '#':
                continue
            if dist[ny][nx] == -1:
                dist[ny][nx] = dist[y][x] + 1
                d.append([ny, nx])

ans = -1
for sy in range(H):
    for sx in range(W):
        dist = [[-1] * W for _ in range(W)]
        for gy in range(H):
            for gx in range(W):
                dist[sy][sx] = 0
                bfs(maze, dist, sy, sx)
                ans = max(ans, dist[gy][gx])
print(ans)

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
p=list(map(int,input().split()))
q=[(1+pp)/2 for pp in p]
ans=0
c=[0]
for qq in q:
      c.append(c[-1]+qq)
ans=0

for qq in range(k,1+n):
  ans=max(ans,c[qq]-c[qq-k])

print(ans)

Submission status: Runtime Error

Solution code:
#n = int(input())
#l = list(map(int, input().split()))

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''
import queue
import numpy as np

def sol(h,w,s,start):
    dx = [1, 0, -1, 0]
    dy=[0,1,0,-1]
    inf = -1000000000
    d=np.array([[inf for i in range(w)] for i in range(h)])
    q=queue.Queue()
    q.put(start)
    d[start[1]][start[0]]=0
    while not q.empty():
        p = q.get()
        for i in range(4):
            nx=p[0]+dx[i]
            ny=p[1]+dy[i]
            if 0<=nx<w and 0<=ny<h:
                S = s[ny][0]
                if d[nx][ny]==inf:
                    
                    if S[nx]=='.':
                        q.put([nx,ny])
                        d[nx][ny]=d[p[0]][p[1]]+1
    return np.max(d)


def main():
    import sys
    input = sys.stdin.readline
    h,w = map(int, input().split())
    s = []
    for i in range(h):
        SS = list(map(str, input().split()))
        s.append(SS)
    ans=[]
    for i in range(w):
        for j in range(h):
            start = [i,j]
            ans.append(sol(h,w,s,start))
    print(max(ans))
        


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
G=[["#"]*(w+2) for i in range(h+2)]
for i in range(1,h+1):
  G[i]=["#"]+list(input())+["#"]
ans=0
for sx in range(1,h+1):
  for sy in range(1,w+1):
    B=[[0]*(w+2) for i in range(h+2)]
    for i in range(h+2):
      for j in range(w+2):
        if G[i][j]=="#":
          B[i][j]=1
    INF=10**4
    A=[[INF]*(w+2) for i in range(h+2)]
    C=[-1,1,0,0]
    D=[0,0,-1,1]
    A[sx][sy]=0
    E=deque([sx,sy])
    while len(E)>0:
      x=E[0]
      E.popleft()
      y=E[0]
      E.popleft()
      for i in range(4):
        if B[x+C[i]][y+D[i]]==0:
          A[x+C[i]][y+D[i]]=A[x][y]+1
          a=A[x+C[i]][y+D[i]]
          B[x+C[i]][y+D[i]]=1
          E.append(x+C[i])
          E.append(y+D[i])
    if ans<a:
      ans=a
print(ans)

Submission status: Runtime Error

Solution code:
#python3
INF = int(1e9)
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

def main():
    h, w = map(int, input().split())
    maze = []
    ans = 0
    for _ in range(h):
        data = input()
        maze.append(data)    
    
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                continue
            start = (i, j)
            from collections import deque         
            g = [[INF for _ in range(w)] for _ in range(h)] 
            q = deque()
            q.append(start)
            g[i][j] = 0
            while len(q) > 0:
                x, y = q.popleft()
                for d in dd:
                    di = x + d[0]
                    dj = y + d[1]
                    if (di < 0) | (dj < 0) | (di >= h) | (dj >= w): 
                        continue
                    if maze[di][dj] == "#":
                        continue
                    if g[di][dj] != INF:
                        continue
                    q.append((di, dj))
                    g[di][dj] = g[x][y]+1 
            

        for i in range(h):
            for j in range(w):
                if g[i][j] == INF:
                    continue
                ans = max(ans, g[i][j])
    print(ans)
main()

Submission status: Runtime Error

Solution code:
import sys
import math
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)

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

queue=deque([])
def bfs(x,y):
    for i,j in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:
        if i<0 or h<=i or j<0 or w<=j :continue
        if dist[i][j] != -1:continue
        if miti[i][j]=="#":continue
        dist[i][j]=dist[x][y]+1
        queue.append([i,j])
    while queue:
        t,r=queue.popleft()
        bfs(t,r)

for i in range(h):
  for j in range(w):
    if miti[i][j]==".":
      s=i;t=j
      break
  break
dist=[[-1 for i in range(w)] for j in range(h)]
dist[s][t]=0
bfs(s,t)


dis0=0
ty=[0,0]
for i in range(h):
    for j in range(w):
        if dis0<dist[i][j]:
            dis0=dist[i][j]
            ty=[i,j]
q,e=ty
dist=[[-1 for i in range(w)] for j in range(h)]
dist[q][e]=0
queue=deque([])
bfs(q,e)

ans=0

for i in range(h):
    for j in range(w):
        if ans<dist[i][j]:
            ans=dist[i][j]

print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
from math import sqrt
from collections import deque
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)

h,w=map(int,input().split())
miti=[]
for i in range(h):
    miti.append(input())
    
dist=[[-1 for i in range(w)] for j in range(h)]
dist[0][0]=0
queue=deque([])
def bfs(x,y):
    for i,j in [[x+1,y],[x,y+1],[x-1,y],[x,y-1]]:
        if i<0 or h<=i or j<0 or w<=j :continue
        if dist[i][j] != -1:continue
        if miti[i][j]=="#":continue
        dist[i][j]=dist[x][y]+1
        queue.append([i,j])
    while queue:
        t,r=queue.popleft()
        bfs(t,r)

for i in range(h):
  for j in range(w):
    if miti[i][j]==".":
      s=i;t=j
      break
  break
bfs(s,t)
dis0=0
ty=[0,0]
for i in range(h):
    for j in range(w):
        if dis0<dist[i][j]:
            dis0=dist[i][j]
            ty=[i,j]
i,j=ty
dist=[[-1 for i in range(w)] for j in range(h)]
dist[i][j]=0
queue=deque([])
bfs(i,j)

ans=0


for i in range(h):
    for j in range(w):
        if ans<dist[i][j]:
            ans=dist[i][j]

print(ans)

Submission status: Runtime Error

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


def bfs(maze, sx, sy, gy, gx):
    d = [[float("inf")] * w for i in range(h)]

    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()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gy][gx]


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

print(ans)

Submission status: Runtime Error

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

for i in range(H):
    t = list(input())
    A.append(t)

print(A)

move = [[-1,0],[1,0],[0,-1],[0,1]]
for i in range(H):
    for j in range(W):
        dp = [[float('inf') for i in range(W)] for j in range(H)]
        if A[i][j] == '.':
            for p,q in zip(move):
                if

Submission status: Runtime Error

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

#print(*a, sep = "\n")

l = h*w
INF = 10**5

dp = [[INF]*(l) for i in range(l)]

for i in range(l):
    if a[i] == "#":
        for j in range(l):
            dp[i][j] = "#"
            dp[j][i] = "#"
            continue

    for j in range(l):
        if i == j:
            dp[i][j] = 0

    #左右上下を1にする
    #右
    if i%w+1 < w:
        dp[i][i+1] = 1
        dp[i+1][i] = 1
    #左
    if i%w-1 > 0:
        dp[i][i-1] = 1
        dp[i-1][i] = 1
    #上
    if i//h-1 > 0:
        dp[i][i-w] = 1
        dp[i-w][i] = 1
    #下
    if i//h+1 < h:
        dp[i][i+w] = 1
        dp[i+w][i] = 1

max = 0
for k in range(l):
    for i in range(l):
        for j in range(l):
            if dp[i][j] == -1:
                continue
            try:
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            except:
                dp[i][j] = dp[i][j]
max = 0
for i in dp:
    for j in i:
        try:
            if max < j:
                max = j
        except:
            pass

#print(*dp, sep="\n")
print(max)

Submission status: Runtime Error

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

# sの位置をあらかじめ調べておく
for n1,c_w in enumerate(C):
    for n2,c in enumerate(c_w):
        if c == "s":
            s_h = n1
            s_w = n2
stack=[]
stack.append([[s_h, s_w]])  # スタートの位置だけ入ったスタックを作成

visited_list = [[0]*W for _ in range(H)]
visited_list[s_h][s_w] = 1

def dfs(town, visited_list, stack):
    while len(stack) > 0:
        h, w = stack.pop()
        if town[h][w] == "g":
            return "Yes"
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h, new_w = h+j, w+k
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if town[new_h][new_w] != "#" and visited_list[new_h][new_w] == 0:
                visited_list[new_h][new_w] = 1
                stack.append([new_h, new_w])

    return "No"

print(dfs(C, visited_list, stack))

Submission status: Runtime Error

Solution code:
n,k=map(int, input().split())
an=[int(i) for i in input().split()]
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p
p = 10 ** 9 + 7
N = 10 ** 5
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

an=sorted(an)
r_an=list(reversed(an))

max1=0
min1=0
for i in range(1,n-k+2):
    c=cmb(n-i,k-1,mod)
    max1=max1 + an[-i]*c%p
    min1=min1 + r_an[-i]*c%p
print((max1-min1)%p)

Submission status: Runtime Error

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

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

    d, i, j = -1, -1, -1
    while q:
        d, (i, j) = q.popleft()
        if dist[i][j] != -1:
            continue
        dist[i][j] = d
        for di, dj in MOVE:
            ni, nj = i + di, j + dj
            if not 0 <= ni < h or not 0 <= nj < w:
                continue
            if field[ni][nj] == '#':
                continue
            if dist[ni][nj] != -1:
                continue
            q.append((d + 1, (ni, nj)))
    return d, i, j

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

print(ans)

Submission status: Runtime Error

Solution code:
import sys

def flagInit():
    global NODES
    for i in c:
        tmp=[]
        for j in i:
            if(j=='#'):
              tmp.append(-1)
            else:
              NODES+=1
              tmp.append(0)
        bf_flag.append(tmp)

def bf_search(sx,sy,gx,gy):
    queue=[[]]*NODES
    bf_flag[sx][sy] = 1
    head=0
    tail=0
    tmp=1
    queue[head]=[sx,sy]
    head+=1
    

    while (head > tail):
        u=queue[tail]
        tail+=1
        tmp=1
        x=u[0]
        y=u[1]
        if(x==gx and y==gy):
            return (bf_flag[gx][gy]-1)
        
        if(c[x+1][y] == '.' and bf_flag[x+1][y]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x+1,y]
                head+=1
                bf_flag[x+1][y]=bf_flag[x][y]+1
                tmp+=1
        if(c[x-1][y] == '.' and bf_flag[x-1][y]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x-1,y]
                head+=1
                bf_flag[x-1][y]=bf_flag[x][y]+1 
                tmp+=1
        if(c[x][y+1] == '.' and bf_flag[x][y+1]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x,y+1]
                head+=1
                tmp+=1
                bf_flag[x][y+1]=bf_flag[x][y]+1
        if(c[x][y-1] == '.' and bf_flag[x][y-1]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x,y-1]
                head+=1
                tmp+=1
                bf_flag[x][y-1]=bf_flag[x][y]+1



NODES = 0  # ノードの数
START = 0  # 探索開始ノード
bf_flag=[]
maxValue=0
c=[]

H,W=map(int,input().split())
c.append(['#' for _ in range(W+2)])
for _ in range(H):
    li = list(input())
    li.append('#')
    li.insert(0,'#')
    c.append(li)
c.append(['#' for _ in range(W+2)])
nod=[[1,1,H,W],[H,1,1,W]]
for _ in range(2):
    bf_flag=[]
    NODES=0
    flagInit()
    n=nod.pop()
    sx,sy,gx,gy=n[0],n[1],n[2],n[3]
    tmp=bf_search(sx,sy,gx,gy)
    if(maxValue<tmp):
        maxValue=tmp
print(maxValue)

Submission status: Runtime Error

Solution code:
import sys

def flagInit():
    global NODES
    for i in c:
        tmp=[]
        for j in i:
            if(j=='#'):
              tmp.append(-1)
            else:
              NODES+=1
              tmp.append(0)
        bf_flag.append(tmp)

def bf_search(sx,sy,gx,gy):
    queue=[[]]*NODES
    bf_flag[sx][sy] = 1
    head=0
    tail=0
    tmp=1
    queue[head]=[sx,sy]
    head+=1
    

    while (head > tail):
        u=queue[tail]
        tail+=1
        tmp=1
        x=u[0]
        y=u[1]
        if(x==gx and y==gy):
            return (bf_flag[gx][gy]-1)
        
        if(c[x+1][y] == '.' and bf_flag[x+1][y]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x+1,y]
                head+=1
                bf_flag[x+1][y]=bf_flag[x][y]+1
                tmp+=1
        if(c[x-1][y] == '.' and bf_flag[x-1][y]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x-1,y]
                head+=1
                bf_flag[x-1][y]=bf_flag[x][y]+1 
                tmp+=1
        if(c[x][y+1] == '.' and bf_flag[x][y+1]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x,y+1]
                head+=1
                tmp+=1
                bf_flag[x][y+1]=bf_flag[x][y]+1
        if(c[x][y-1] == '.' and bf_flag[x][y-1]==0):  # 隣接しているノードでまだ探索していない場合
                queue[head]=[x,y-1]
                head+=1
                tmp+=1
                bf_flag[x][y-1]=bf_flag[x][y]+1



NODES = 0  # ノードの数
START = 0  # 探索開始ノード
bf_flag=[]
maxValue=0
c=[]

H,W=map(int,input().split())
c.append(['#' for _ in range(W+2)])
for _ in range(H):
    li = list(input())
    li.append('#')
    li.insert(0,'#')
    c.append(li)
c.append(['#' for _ in range(W+2)])

nod=[[1,1,H,W],[H,1,1,W]]
for _ in range(2):
    bf_flag=[]
    NODES=0
    flagInit()
    n=nod.pop()
    sx,sy,gx,gy=n[0],n[1],n[2],n[3]
    tmp=bf_search(sx,sy,gx,gy)
    if(maxValue<tmp):
        maxValue=tmp
print(maxValue)

Submission status: Runtime Error

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: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ 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: Runtime Error

Solution code:
from collections import deque
h,w=map(int,input().split())
S=[input() for _ 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)]
         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: Runtime Error

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]]
            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])
                    map[y + 1][x] = "a"
                if maps[y][x + 1] == ".":
                    pos.append([y, x + 1, depth + 1])
                    map[y][x + 1] = "a"
                if maps[y - 1][x] == ".":
                    pos.append([y - 1, x, depth + 1])
                    map[y - 1][x] = "a"
                if maps[y][x - 1] == ".":
                    pos.append([y, x - 1, depth + 1])
                    map[y][x - 1] = "a"
print(MAX)

Submission status: Runtime Error

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().split()
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: Runtime Error

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):
        """
        下記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(max(tmp))

Submission status: Runtime Error

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][j] == '#':
            continue
        if ans > mat[i][j]:
            tmp.append(mat[i][j])
            
print(max(tmp))

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

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=[list(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,0))
      visited=copy.deepcopy(_visited)
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

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

# main()
print(main())

Submission status: Runtime Error

Solution code:
import math,itertools,fractions,heapq,bisect,sys,copy,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,0))
      for _i in range(h):
        for _j in range(w):
          visited[_i][_j]=-1
      while len(q)>0:
        y,x,c=q.popleft()
        visited[y][x]=c

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

# main()
print(main())

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

S = []
for e in sys.stdin:
    S.append(e.rstrip())

H, M = map(int, S[0].split())

meiro = []
for i in range(H):
    meiro.append([])
    for k in S[i + 1]:
        if k == '.':
            meiro[i].append(1)
        else:
            meiro[i].append(0)
meiro_array = np.array(meiro)
susumikata = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def BFS(y, x):
    global max_distance
    if meiro_array[x, y] == 1:
        max_distance = 0
        reached = {(x, y): 0}
        for i in range(H * M):
            zahyous = [k for k, v in reached.items() if v == i]
            for zahyou in zahyous:
                for susumi in susumikata:
                    new_zahyou = tuple([zahyou[0] + susumi[0], zahyou[1] + susumi[1]])
                    if not(0 <= new_zahyou[0] < H and 0 <= new_zahyou[1] < M):
                        a = 0
                    elif new_zahyou not in reached.keys() and meiro_array[new_zahyou] == 1:
                        reached[new_zahyou] = i + 1
                        max_distance = i + 1

    return max_distance


keiro_max = []
for x in range(H):
    for y in range(M):
        keiro_max.append(BFS(x, y))

print(max(keiro_max))