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:
import copy
H,W=map(int,input().split())

def BFS(h,w,maze):


maze=[]
maze.append("#"*W)
for h in range(H):
    maze_e=input()
    line=[]

    maze.append("#"+line+"#")

maze.append("#"*W)


maze_ori=copy.deepcopy(maze)

maxd=0

for h in range(1,H+1):
    for w in range(1,W+1):
        maze=copy.deepcopy(maze_ori)
        if maze[h][w]="#":
            continue
        else:
            next_flag=True


        direction=[[-1,0],[0][-1],[1,0],[0][1]])
        distance=0
        maze[h][w]=distance

        next_list=[h,w]
        while next_flag is True:
            p_list=next_list[]
            next_list=[]
            distance+=1
            next_flag=False
            for p in p_list:
                for d in direction:
                    i=p[0]+d[0]
                    j=p[1]+d[1]

                    if maze[i,j]==".":
                        maze[i,j]=distance
                        next_list.append([i,j])
                        next_flag=True
            
        maxd=max(maxd,distance-1)

print(maxd)

Submission status: Runtime Error

Solution code:
from collections import deque

x4 = [ 1,0,-1,0 ]
y4 = [ 0,1,0,-1 ] 
max_int = 2**63-1


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

ans = 0

for i in range(h):
    for j in range(w):
        if S[i][j] == '#':
            continue

        visited = [[False for o in range(w)] for l in range(h)]
        q = deque()
        d = [[max_int for o in range(w)] for l in range(h)]

        visited[i][j] = True
        q.append((i,j))
        d[i][j] = 0

        while(q.empty() == False):
            cy, cx = q.popleft()
            visited[cy][cx] = True
            for k in range(4):
                ny = cy + y4[k]
                nx = cx + x4[k]
                if 0 <= nx < w and 0 <= ny < h and S[ny][nx] == '.' and visited[ny][nx] == False:
                    q.append((ny, nx))
                    d[ny][nx] = min(d[ny][nx], d[cy][cx] + 1)
                    ans = max(d[ny][nx], ans)

print(ans)

Submission status: Runtime Error

Solution code:
""""
3 5
...#.
.#.#.
.#...
"""
from collections import deque
#import numpy as np

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


def make_wall(W, Map):
    for map_row in Map:
        map_row.append("#")
        map_row.insert(0, "#")

    wall = ["#"]*(W+2)
    Map.append(wall)
    Map.insert(0, wall)
    return Map


start_list = deque()
search_list = deque()
Map = make_wall(W, Map)
H += 2
W += 2

start_h = 0
for h in range(H):
    start_w = 0
    for w in range(W):
        if Map[h][w] == ".":
            start_list.append([start_h, start_w])
        start_w += 1
    start_h += 1



max_cost = 0
while start_list != deque():
    search_list.append(start_list.popleft())
    cost_map = np.array([[0] * W for i in range(H)])
    search_map = np.array([[0] * W for i in range(H)])
    while search_list != deque():
        tmp = search_list.popleft()
        x = tmp[0]
        y = tmp[1]
        search_map[x][y] = 1
        if Map[x][y+1] == "." and search_map[x][y+1] == 0:
            search_list.append([x, y+1])
            cost_map[x][y+1] = cost_map[x][y]+1
        if Map[x][y-1] == "." and search_map[x][y-1] == 0:
            search_list.append([x, y-1])
            cost_map[x][y-1] = cost_map[x][y]+1
        if Map[x+1][y] == "." and search_map[x+1][y] == 0:
            search_list.append([x+1, y])
            cost_map[x+1][y] = cost_map[x][y]+1
        if Map[x-1][y] == "." and search_map[x-1][y] == 0:
            search_list.append([x-1, y])
            cost_map[x-1][y] = cost_map[x][y]+1
    """"
    cost_map = np.array(cost_map)
    if max_cost < np.amax(cost_map):
        max_cost = np.amax(cost_map)
    """
    max_tmp = [0]*H
    for i in range(H):
        max_tmp[i] = max(cost_map[i])
    if max_cost < max(max_tmp):
        max_cost = max(max_tmp)

print(max_cost)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import itertools
H,W= [int(x) for x in input().split()]
meiro=[list(input())for _ in range(H)]
#print(meiro)
ans=0
dx = [1,0,-1,0]
dy=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    result=[[0]*W for _ in range(H)]
    cnt=0
    #print(i,j)
    if meiro[i][j]=="#":
      continue
    elif meiro[i][j]==".":
      stk =[[i,j]]
      result[i][j]=1
      while stk:
        x,y = stk.pop(0)
        
        for r in range(4):
          xx,yy=x+dx[r],y+dy[r]
          if yy<0 or xx<0 or W<=yy or H<=xx or meiro[xx][yy]=="#" or result[xx][yy]!=0:
            continue
          result[xx][yy]=result[x][y]+1
          stk.append([xx,yy])
      for l in range(H):
        for t in range(W):
          ans = max(ans,result[l][t])
print(ans-1)import itertools
H,W= [int(x) for x in input().split()]
meiro=[list(input())for _ in range(H)]
#print(meiro)
ans=0
dx = [1,0,-1,0]
dy=[0,1,0,-1]
for i in range(H):
  for j in range(W):
    result=[[0]*W for _ in range(H)]
    cnt=0
    #print(i,j)
    if meiro[i][j]=="#":
      continue
    elif meiro[i][j]==".":
      stk =[[i,j]]
      result[i][j]=1
      while stk:
        x,y = stk.pop(0)
        
        for r in range(4):
          xx,yy=x+dx[r],y+dy[r]
          if yy<0 or xx<0 or W<=yy or H<=xx or meiro[xx][yy]=="#" or result[xx][yy]!=0:
            continue
          result[xx][yy]=result[x][y]+1
          stk.append([xx,yy])
      for l in range(H):
        for t in range(W):
          ans = max(ans,result[l][t])
print(ans-1)

Submission status: Runtime Error

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    c = [input() for j in range(H)]
    st = [(h, w) for h in range(H) for w in range(W)]

    def bfs(sy, sx, gy, gx):
        que = deque()
        dist = [[-1]*W for h in range(H)]
        dist[sy][sx] = 0
        que.append((sy, sx))
        d = ((1, 0), (0, 1), (-1, 0), (0, -1))
        while que:
            uy, ux = que.popleft()
            for dy, dx in d:
                next_y = uy + dy
                next_x = ux + dx
                if not(0 <= next_y < H and 0 <= next_x < W):
                    continue
                if dist[next_y][next_x] != -1:
                    continue
                if c[next_y][next_x] == '#':
                    continue
                dist[next_y][next_x] = dist[uy][ux] + 1
                que.append((next_y, next_x))
        return dist[gy][gx]
    ans = 0
    for s in st:
        for t in st:
            if s == t or c[s[0]][s[1]] == "#" or c[t[0]][t[1]] == "#":
                continue
            ans = max(ans, bfs(*s, *t))
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
buffer = ""

def set_buffer(text):
    global buffer
    import io
    buffer = io.StringIO(text)
    
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])
def solve(maze, start_r, start_c):
    
    distances = {}
    offsets = [(-1,0),(1,0),(0,-1),(0,1)]
    
    distances[start_r, start_c] = 0
    candidates = [(start_r, start_c)]
    
    while candidates:
        r, c= candidates.pop(0)
        
        for offset_r, offset_c in offsets:
            move_r, move_c = r + offset_r, c + offset_c
            if not (move_r, move_c) in distances and maze[move_r, move_c] == ".":
                distances[move_r, move_c] = distances[r, c] + 1
                candidates.append((move_r, move_c))
    
    return max(distances.values())
    

def main(input_text=""):
    if input_text:
        set_buffer(input_text)
    h, w = get_next_ints()
    from collections import defaultdict
    maze = defaultdict(str)
    for r in range(h):
        line = get_next_str()
        for c in range(w):
            maze[r,c] = line[c]
    
    results = []
    for r in range(h):
        for c in range(w):
            result = solve(maze, r, c)
            results.append(result)
    
    print(max(results))
    
if __name__ == '__main__':
    main()
if __name__ == '__jupyter__':
    import doctest
    print(doctest.testmod())

Submission status: Runtime Error

Solution code:
import numpy as np

def chk_route(c,s,T):
    global H,W,R
    mx = H*W
    #print(c)
    #print(T)
    flg = 0
    T[c[0]][c[1]]=s
    if R[c[0]][c[1]] > s:
        R[c[0]][c[1]] = s

    if c[0] != H-1:
        #if T[c[0]+1][c[1]]!=1 and T[c[0]+1][c[1]]!=s-1 and T[c[0]+1][c[1]]!=2:
        if T[c[0]+1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]+1,c[1]],s+1,B)
    if c[0] != 0:
        #if T[c[0]-1][c[1]]!=1 and T[c[0]-1][c[1]]!=s-1 and T[c[0]-1][c[1]]!=2:
        if T[c[0]-1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]-1,c[1]],s+1,B)
    if c[1] != W-1:
        #if T[c[0]][c[1]+1]!=1 and T[c[0]][c[1]+1]!=s-1 and T[c[0]][c[1]+1]!=2:
        if T[c[0]][c[1]+1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]+1],s+1,B)
    if c[1] != 0:
        #if T[c[0]][c[1]-1]!=1 and T[c[0]][c[1]-1]!=s-1 and T[c[0]][c[1]-1]!=2:
        if T[c[0]][c[1]-1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]-1],s+1,B)

    if flg == 0:
        #print(T)
        #r=np.count_nonzero(T==2)
        if R[c[0]][c[1]] > s:
            R[c[0]][c[1]] = s
        #return s
    if s==2: pass #return mx
        #T=np.copy(B)
H,W= [int(x) for x in input().split()]
n=[]
#T = [[0] * W for i in range(H)]
T=np.zeros((H,W),dtype=int)
MX = H*W
R=np.full((H,W),MX,dtype = int)
#R = [[15] * W for i in range(H)]
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#print(T)
d=0
for i in range(H):
    for j in range(W):

        if T[i][j] ==1:continue

        c=[i,j]
        B=T.copy()
        R=np.full((H,W),MX,dtype = int)
        chk_route(c,int(2),B)

        d = max(d,np.max(R[np.where(R<MX)]))

        #b= b[np.where(b[:,22].astype(float) > 0)]
print(d-2)
#print(mx)

Submission status: Runtime Error

Solution code:
import numpy as np

def chk_route(c,s,T):
    global H,W,R
    mx = H*W
    #print(c)
    #print(T)
    flg = 0
    T[c[0]][c[1]]=s
    if R[c[0]][c[1]] > s:
        R[c[0]][c[1]] = s

    if c[0] != H-1:
        #if T[c[0]+1][c[1]]!=1 and T[c[0]+1][c[1]]!=s-1 and T[c[0]+1][c[1]]!=2:
        if T[c[0]+1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]+1,c[1]],s+1,B)
    if c[0] != 0:
        #if T[c[0]-1][c[1]]!=1 and T[c[0]-1][c[1]]!=s-1 and T[c[0]-1][c[1]]!=2:
        if T[c[0]-1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]-1,c[1]],s+1,B)
    if c[1] != W-1:
        #if T[c[0]][c[1]+1]!=1 and T[c[0]][c[1]+1]!=s-1 and T[c[0]][c[1]+1]!=2:
        if T[c[0]][c[1]+1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]+1],s+1,B)
    if c[1] != 0:
        #if T[c[0]][c[1]-1]!=1 and T[c[0]][c[1]-1]!=s-1 and T[c[0]][c[1]-1]!=2:
        if T[c[0]][c[1]-1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]-1],s+1,B)

    if flg == 0:
        #print(T)
        #r=np.count_nonzero(T==2)
        if R[c[0]][c[1]] > s:
            R[c[0]][c[1]] = s
        #return s
    if s==2: pass #return mx
        #T=np.copy(B)
H,W= [int(x) for x in input().split()]
n=[]
#T = [[0] * W for i in range(H)]
T=np.zeros((H,W),dtype=int)
MX = H*W
R=np.full((H,W),MX,dtype = int)
#R = [[15] * W for i in range(H)]
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#print(T)
d=0
for i in range(H):
    for j in range(W):

        if T[i][j] =='1':continue

        c=[i,j]
        B=T.copy()
        R=np.full((H,W),MX,dtype = int)
        chk_route(c,int(2),B)

        d = max(d,np.max(R[np.where(R<MX)]))

        #b= b[np.where(b[:,22].astype(float) > 0)]
print(d-2)
#print(mx)

Submission status: Runtime Error

Solution code:
import numpy as np

def chk_route(c,s,T):
    global H,W,R
    mx = H*W
    #print(c)
    #print(T)
    flg = 0
    T[c[0]][c[1]]=s
    if R[c[0]][c[1]] > s:
        R[c[0]][c[1]] = s

    if c[0] != H-1:
        #if T[c[0]+1][c[1]]!=1 and T[c[0]+1][c[1]]!=s-1 and T[c[0]+1][c[1]]!=2:
        if T[c[0]+1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]+1,c[1]],s+1,B)
    if c[0] != 0:
        #if T[c[0]-1][c[1]]!=1 and T[c[0]-1][c[1]]!=s-1 and T[c[0]-1][c[1]]!=2:
        if T[c[0]-1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]-1,c[1]],s+1,B)
    if c[1] != W-1:
        #if T[c[0]][c[1]+1]!=1 and T[c[0]][c[1]+1]!=s-1 and T[c[0]][c[1]+1]!=2:
        if T[c[0]][c[1]+1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]+1],s+1,B)
    if c[1] != 0:
        #if T[c[0]][c[1]-1]!=1 and T[c[0]][c[1]-1]!=s-1 and T[c[0]][c[1]-1]!=2:
        if T[c[0]][c[1]-1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]-1],s+1,B)

    if flg == 0:
        #print(T)
        #r=np.count_nonzero(T==2)
        if R[c[0]][c[1]] > s:
            R[c[0]][c[1]] = s
        #return s
    if s==2: pass #return mx
        #T=np.copy(B)
H,W= [int(x) for x in input().split()]
n=[]
#T = [[0] * W for i in range(H)]
T=np.zeros((H,W),dtype=int)
MX = H*W
R=np.full((H,W),MX,dtype = int)
#R = [[15] * W for i in range(H)]
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#print(T)
d=0
for i in range(H):
    for j in range(W):

        if T[i][j] =='#':continue
        
        c=[i,j]
        B=T.copy()
        R=np.full((H,W),MX,dtype = int)
        chk_route(c,int(2),B)

        d = max(d,np.max(R[np.where(R<MX)]))

        #b= b[np.where(b[:,22].astype(float) > 0)]
print(d-2)
#print(mx)

Submission status: Runtime Error

Solution code:

def mk_idx(y,x):
    return y*22+x

H,W=map(int, input().split())
DINF = 100000
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0
G = [ [] for _ in range( mk_idx(22,22) ) ]
for y in range(1,H+1):
    for x in range(1,W+1):
        if (S[y][x] == '.'):
            idx = mk_idx(y,x)
            if (S[y-1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y-1,x) )
            if (S[y][x-1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x-1) )
            if (S[y+1][x] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y+1,x) )
            if (S[y][x+1] == '.'):  G[ mk_idx(y,x) ].append( mk_idx(y,x+1) )

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            d = [ DINF for _ in range( mk_idx(22,22) ) ]
            d[ mk_idx(y,x) ] = 0
            q = deque( [mk_idx(y,x)] )
            while len(q) != 0:
                v = q.popleft()
                n = d[v];
                dmax = max(dmax, n)
                for nv in G[v]:
                    if d[ nv ] <= n+1 :
                        continue
                    d[ nv ] = n+1
                    q.append(nv)
print(dmax)

Submission status: Runtime Error

Solution code:
import numpy as np

def chk_route(c,s,T):
    global H,W,R
    mx = H*W
    #print(c)
    #print(T)
    flg = 0
    T[c[0]][c[1]]=s
    if R[c[0]][c[1]] > s:
        R[c[0]][c[1]] = s
    #if s==2: B=T.copy()
    if c[0] != H-1:
        #if T[c[0]+1][c[1]]!=1 and T[c[0]+1][c[1]]!=s-1 and T[c[0]+1][c[1]]!=2:
        if T[c[0]+1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]+1,c[1]],s+1,B)
    if c[0] != 0:
        #if T[c[0]-1][c[1]]!=1 and T[c[0]-1][c[1]]!=s-1 and T[c[0]-1][c[1]]!=2:
        if T[c[0]-1][c[1]]==0:
            flg=1
            B=T.copy()
            chk_route([c[0]-1,c[1]],s+1,B)
    if c[1] != W-1:
        #if T[c[0]][c[1]+1]!=1 and T[c[0]][c[1]+1]!=s-1 and T[c[0]][c[1]+1]!=2:
        if T[c[0]][c[1]+1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]+1],s+1,B)
    if c[1] != 0:
        #if T[c[0]][c[1]-1]!=1 and T[c[0]][c[1]-1]!=s-1 and T[c[0]][c[1]-1]!=2:
        if T[c[0]][c[1]-1]==0:
            flg=1
            B=T.copy()
            chk_route([c[0],c[1]-1],s+1,B)

    if flg == 0:
        #print(T)
        #r=np.count_nonzero(T==2)
        if R[c[0]][c[1]] > s:
            R[c[0]][c[1]] = s
        #return s
    if s==2: pass #return mx
        #T=np.copy(B)
H,W= [int(x) for x in input().split()]
n=[]
#T = [[0] * W for i in range(H)]
T=np.zeros((H,W),dtype=int)
MX = H*W
R=np.full((H,W),MX,dtype = int)
#R = [[15] * W for i in range(H)]
for i in range(H):
  n=input()
  for j in range(W):
    if n[j]=="#": T[i][j]=1
#print(T)
d=0
for i in range(H):
    for j in range(W):
        c=[i,j]
        B=T.copy()
        R=np.full((H,W),MX,dtype = int)
        chk_route(c,int(2),B)

        d = max(d,np.max(R[np.where(R<MX)]))

        #b= b[np.where(b[:,22].astype(float) > 0)]
print(d-2)
#print(mx)

Submission status: Runtime Error

Solution code:
import copy
H = 0
W = 0


def search_route(maps, x_start, y_start, x_end, y_end):
    # print('starting search shortest path:')
    # print('start:', x_start, y_start, 'end:', x_end, y_end)
    maps[y_start][x_start]['distance'] = 0
    maps[y_start][x_start]['from_p'] = 'start'
    maps[y_end][x_end]['distance'] = 0
    maps[y_end][x_end]['from_p'] = 'end'

    # スタートとゴールから一歩ずつ移動する
    latest_searched_from_start =[{'x': x_start, 'y': y_start}]
    latest_searched_from_end = [{'x': x_end, 'y': y_end}]
    for i in range(1, H*W):
        new_latest_searched_from_start = []
        for road in latest_searched_from_start:
            for direction in [{'x': 1, 'y': 0}, {'x': -1, 'y': 0}, {'x': 0, 'y': 1}, {'x': 0, 'y': -1}]:
                x = road['x'] + direction['x']
                y = road['y'] + direction['y']
                if x < 0 or x >= W or y < 0 or y >= H:
                    continue
                object_r = maps[y][x]
                if 'from_p' in object_r.keys() and object_r['from_p'] == 'end':  # 探索済みだったら終了
                    return (i - 1) * 2 + 1
                if not object_r['isWall'] and 'from_p' not in object_r.keys():
                    object_r['distance'] = i
                    object_r['from_p'] = 'start'
                    new_latest_searched_from_start.append({'x': x, 'y': y})
        latest_searched_from_start = new_latest_searched_from_start
        # print(latest_searched_from_start)

        new_latest_searched_from_end = []
        for road in latest_searched_from_end:
            for direction in [{'x': 1, 'y': 0}, {'x': -1, 'y': 0}, {'x': 0, 'y': 1}, {'x': 0, 'y': -1}]:
                x = road['x'] + direction['x']
                y = road['y'] + direction['y']
                if x < 0 or x >= W or y < 0 or y >= H:
                    continue
                object_r = maps[y][x]
                if 'from_p' in object_r.keys() and object_r['from_p'] == 'start':  # 探索済みだったら終了
                    return i * 2
                if not object_r['isWall'] and 'from_p' not in object_r.keys():
                    object_r['distance'] = i
                    object_r['from_p'] = 'end'
                    new_latest_searched_from_end.append({'x': x, 'y': y})
        latest_searched_from_end = new_latest_searched_from_end
        # print(latest_searched_from_end)

    return None


def main():
    global H, W
    H, W = map(int, input().split())
    maps = []
    for i in range(H):
        row = []
        for load in list(input()):
            if load == '#':
                row.append({'isWall': True})
            else:
                row.append({'isWall': False})
        maps.append(row)

    max_times = 0  # 移動回数の最大値
    for i_start in range(H*W):  # 縦：５　横：３のマップで i = 10のとき
        x_start = i_start % W  # x_start = 1
        y_start = i_start // W  # y_start = 3
        if maps[y_start][x_start]['isWall']:
            continue
        for i_end in range(i_start+1, H*W):
            x_end = i_end % W
            y_end = i_end // W
            times = search_route(copy.deepcopy(maps), x_start, y_start, x_end, y_end)
            # print('shortest path takes', times, 'times')
            # print('')
            if times > max_times:
                max_times = times

    # x_start = 0  # x_start = 1
    # y_start = 0  # y_start = 3
    # x_end = 2
    # y_end = 2
    # times = search_route(copy.deepcopy(maps), x_start, y_start, x_end, y_end)
    # print('shortest path takes', times, 'times')
    # print('')
    # if times > max_times:
    #     max_times = times

    print(max_times)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:

H,W=map(int, input().split())
d = [ [ 100000 for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))
dmax = 0

def SUB(x,y,n):
    d[y][x] = n
    dmax = max(n,dmax)
    if (S[y-1][x] == '.') and (d[y-1][x] > n+1): SUB(x,y-1,n+1)
    if (S[y][x-1] == '.') and (d[y][x-1] > n+1): SUB(x-1,y,n+1)
    if (S[y+1][x] == '.') and (d[y+1][x] > n+1): SUB(x,y+1,n+1)
    if (S[y][x+1] == '.') and (d[y][x+1] > n+1): SUB(x+1,y,n+1)

for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    d[iy][ix] = 100000
print(dmax)

Submission status: Runtime Error

Solution code:

H,W=map(int, input().split())
d = [ [ 100000 for _ in range(W+2)] for _ in range(H+2)]
S = []
S.append('#' * (W+2))
for i in range(H):
    S.append('#'+ input() + '#')
S.append('#' * (W+2))

def SUB(x,y,n):
    d[y][x] = n
    dmax = max(n,dmax)
    if (S[y-1][x] == '.') and (d[y-1][x] > n+1): SUB(x,y-1,n+1)
    if (S[y][x-1] == '.') and (d[y][x-1] > n+1): SUB(x-1,y,n+1)
    if (S[y+1][x] == '.') and (d[y+1][x] > n+1): SUB(x,y+1,n+1)
    if (S[y][x+1] == '.') and (d[y][x+1] > n+1): SUB(x+1,y,n+1)

dmax = 0
for y in range(1,H+1):
    for x in range(1,W+1):
        if S[y][x] == '.':
            SUB(x,y,0)
            for iy in range(1,H+1):
                for ix in range(1,W+1):
                    d[iy][ix] = 100000
print(dmax)

Submission status: Runtime Error

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

def bfs(sw,sh):
    res = 0
    dw = [-1,1,0,0]
    dh = [0,0,1,-1]
    dist = [[-1 for _ in range(w)] for _ in range(h)]
    dist[sw][sh] = 0
    queue = deque()
    queue.append((sw,sh))
    while len(queue) != 0:
        cw,ch = queue.popleft()
        for i in range(4):
            nw,nh = cw + dw[i], ch + dh[i]
            if not (0<= nw < w and 0 <= nh < h): continue
            if path[nw][nh] == "#": continue
            if dist[nw][nh] != -1: continue
            dist[nw][nh] = dist[cw][ch] + 1
            queue.append((nw,nh))
            res = max(res, dist[nw][nh])
    return res

ans = 0
for i in range(w):
    for j in range(h):
        if path[i][j] == "#":
            continue
        ans = max(ans, bfs(i,j))
print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)] # 始点からの距離
      dist[i][j] = 0 # 始点を定義
      stack = deque([(i, j)]) # 始点を"先入れ先出し"の配列に入れる
      
      while stack:
      # BFS
      # * 計算量 O(4HW:辺の数)
      si, sj = stack.popleft() 
        # "先入れ先出し"
        # * ⇔後入れ後出し。DFS
        #   si, sj = stack.pop()
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        # 経路に重みがない場合、BFSでは先に入れた方がそのマスに対する最短経路になる...☆
        # * DFSを使用すると更新の必要があり、
        #    計算量が(4HW*HW:辺の数×グリッドの数)->TLE
        # ** 木だと経路は1つしかないため、BFSもDFSも計算量は同じ
        #     グラフでは基本的にBFS推奨[要出典]
        # * 経路に重みがある場合も更新の必要があり、計算量はO(4HW*HW)
        # ** Dijkstra法を使えば、計算量はO(4HW+HWlogHW)
        #     O(E + VlogV): E -> Edge, V -> Vertex
          if 0 <= ni <= H - 1 and 0 <= nj <= W - 1 and S[ni][nj] != "#":
            if dist[ni][nj] > dist[si][sj] + 1:
              dist[ni][nj] = dist[si][sj] + 1
              stack.append((ni, nj))
          # ☆より、最短経路をとるマスからの隣接が次の最短経路の候補となる
          # すでに最短経路を取っているものは排除
              
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      # * 添え字被りに注意
      
print(answer)

Submission status: Runtime Error

Solution code:
from collections import deque
 
H, W = map(int, input().split())
S = [input() for _ in range(H)]
INF = 10**15

answer = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      continue
    else:
      dist = [[INF for _ in range(W)] for _ in range(H)] # 始点からの距離
      dist[i][j] = 0 # 始点を定義
      stack = deque([(i, j)]) # 始点を"先入れ先出し"の配列に入れる
      
      while stack:
      # BFS
      # * 計算量 O(4HW:辺の数)
      si, sj = stack.popleft() 
        # "先入れ先出し"
        # * ⇔後入れ後出し。DFS
        #   si, sj = stack.pop()
        
        for ni, nj in [(si + 1, sj), (si - 1, sj), (si, sj + 1), (si, sj - 1)]:
        # 経路に重みがない場合、BFSでは先に入れた方がそのマスに対する最短経路になる...☆
        # * DFSを使用すると更新の必要があり、
        #    計算量が(4HW*HW:辺の数×グリッドの数)->TLE
        # ** 木だと経路は1つしかないため、BFSもDFSも計算量は同じ
        #     グラフでは基本的にBFS推奨[要出典]
        # * 経路に重みがある場合も更新の必要があり、計算量はO(4HW*HW)
        # ** Dijkstra法を使えば、計算量はO(4HW+HWlogHW)
        #     O(E + VlogV): E -> Edge, V -> Vertex
          if 0 <= ni <= H - 1 and 0 <= nj <= W - 1 and S[ni][nj] != "#":
            if dist[ni][nj] > dist[si][sj] + 1:
              dist[ni][nj] = dist[si][sj] + 1
              stack.append((ni, nj))
          # ☆より、最短経路をとるマスからの隣接が次の最短経路の候補となる
          # すでに最短経路を取っているものは排除
              
              
      max_dist = 0
      for ii in range(H):
        for jj in range(W):
          if dist[ii][jj] != INF:
            max_dist = max(max_dist, dist[ii][jj])
      answer = max(max_dist, answer)
      # * 添え字被りに注意
      
print(answer)

Submission status: Runtime Error

Solution code:
import queue
dx=[1,0,-1,0]
dy=[0,1,0,-1]
H,W=map(int,input().split())
S=[]
for h in range(H):
  S.append(input())

def bfs(s):
  dist = [[-1]*H for _ in range(W)]
  
  h,w = s
  dist[h][w]=0
  que = queue.Queue()
  que.put(s)
  
  while not(que.empty()):
    h,w = que.get()
    for d in range(4):
      nh = h + dx[d]
      nw = w + dy[d]
      if nh<0 or H<=nh or nw<0 or W<=nw:
        continue
      if S[nh][nw]=="#":
        continue
      if dist[nh][nw]==-1:
        dist[nh][nw]=dist[h][w]+1
        que.put([nh,nw])
  return dist[h][w]

ans = 0
for h in range(H):
  for w in range(W):
    if S[h][w]==".":
      ans = max(ans,bfs([h,w]))
print(ans)

Submission status: Runtime Error

Solution code:
import Queue
dx=[1,0,-1,0]
dy=[0,1,0,-1]
H,W=input().split()
S=[]
for h in range(H):
  S.append(input())

def bfs(s):
  dist = [[-1]*H for _ in range(W)]
  
  h,w = s
  dist[h][w]=0
  que = queue.Queue()
  que.put(s)
  
  while not(que.empty):
    h,w = que.get()
    for d in range(4):
      nh = h + dx[d]
      nw = w + dy[d]
      if nh<0 or H<=nh or nw<0 or W<=nw:
        continue
      if S[nh][nw]=="#":
        continue
      if dist[nh][nw]==-1:
        dist[nh][nw]=dist[h][w]+1
        que.put([nh,nw])
  return dist(h,w)

ans = 0
for h in range(H):
  for w in range(W):
    if S[h][w]==".":
      ans = max(ans,bfs([h,w]))
print(ans)

Submission status: Runtime Error

Solution code:
H,W = map(int,input().split())
L = []
for i in range(H):
    L.append(input())
import collections
q = collections.deque()
li = ((1,0),(0,1),(-1,0),(0,-1))
LL=[]

for i in range(H):
    for j in range(W):
        visited = [[-1]*W for i in range(H)]
        if L[i][j] ==".":
            visited[i][j] = 0
            q.append((i,j))
            cnt = 0
        
        while q:
            x,y = q.popleft()
            for dx,dy in li:
                nx,ny = x+dx,y+dy
                #print(nx,ny)
                if nx<0 or nx>=H or ny<0 or ny>=W or visited[nx][ny] >0:
                    continue
                if visited[nx][ny] ==-1 and  L[nx][ny] == ".": 
                    visited[nx][ny] = visited[x][y] +1
                    cnt = max(cnt,visited[nx][ny])
                    q.append((nx,ny))
                    print(q,cnt)
        LL.append(cnt)
print(max(LL))

Submission status: Runtime Error

Solution code:
import collections
q = collections.deque()
li = ((1,0),(0,1),(-1,0),(0,-1))
LL=[]

for i in range(H):
    for j in range(W):
        visited = [[-1]*W for i in range(H)]
        if L[i][j] ==".":
            visited[i][j] = 0
            q.append((i,j))
            cnt = 0
        
        while q:
            x,y = q.popleft()
            for dx,dy in li:
                nx,ny = x+dx,y+dy
                #print(nx,ny)
                if nx<0 or nx>=H or ny<0 or ny>=W or visited[nx][ny] >0:
                    continue
                if visited[nx][ny] ==-1 and  L[nx][ny] == ".": 
                    visited[nx][ny] = visited[x][y] +1
                    cnt = max(cnt,visited[nx][ny])
                    q.append((nx,ny))
        LL.append(cnt)
print(max(LL))