Problem p02803 (python)

Fixed submission:
from collections import deque

h,w = map(int,input().split())
maze = []

for _ in range(h):
    maze.append(list(input()))

def bfs(initial):
    distance = [[-1] * w for _ in range(h)]
    frontier = deque()
    frontier.append(initial)
    distance[initial[0]][initial[1]] = 0
    while len(frontier):
        current_node = frontier.popleft()
        x,y = current_node
        for i,j in ((1,0),(-1,0),(0,1),(0,-1)):
            new_x, new_y = x+i, y+j
            if 0<=new_x<h and 0<=new_y<w:
                if maze[new_x][new_y] == '.' and distance[new_x][new_y]==-1:
                    distance[new_x][new_y] = distance[x][y] + 1
                    frontier.append((new_x, new_y))
    return distance[x][y]

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

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

def cand_pos(i,j):
    neighbor = []
    if i==0:
        neighbor.append(maze[i+1][j])
    elif i==h-1:
        neighbor.append(maze[i-1][j])
    else:
        neighbor.append(maze[i+1][j])
        neighbor.append(maze[i-1][j])
    
    if j==0:
        neighbor.append(maze[i][j+1])
    elif j==w-1:
        neighbor.append(maze[i][j-1])
    else:
        neighbor.append(maze[i][j+1])
        neighbor.append(maze[i][j-1])
    
    if maze[i][j]!='#' and neighbor.count('.')==1:
        return True
    else:
        return False


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

pos_dic = {}
for i in range(h):
    for j in range(w):
        if cand_pos(i,j):
            pos_dic[i] = j
        else:
            continue

ans = 1000000

if len(pos_dic) == 0:
    ans = h+w-2
elif len(pos_dic) == 1:
    stx,sty = 0,0
    for k,v in pos_dic.items():
        glx, gly = k,v
    ans = bfs(stx, sty, glx, gly)
else:
    for k,v in pos_dic.items():
        stx, sty = k,v
        for kk, vv in pos_dic.items():
            glx, gly = kk, vv
            if stx != glx and sty != gly:
                tmp = bfs(stx, sty, glx, gly)
                ans = min(ans, tmp)
print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

def cand_pos(i,j):
    neighbor = []
    if i==0:
        neighbor.append(maze[i+1][j])
    elif i==h-1:
        neighbor.append(maze[i-1][j])
    else:
        neighbor.append(maze[i+1][j])
        neighbor.append(maze[i-1][j])
    
    if j==0:
        neighbor.append(maze[i][j+1])
    elif j==w-1:
        neighbor.append(maze[i][j-1])
    else:
        neighbor.append(maze[i][j+1])
        neighbor.append(maze[i][j-1])
    
    if maze[i][j]!='#' and neighbor.count('.')==1:
        return True
    else:
        return False


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

pos_dic = {}
for i in range(h):
    for j in range(w):
        if cand_pos(i,j):
            pos_dic[i] = j
        else:
            continue

ans = 1000000

if len(pos_dic) == 0:
    ans = h+w-2
elif len(pos_dic) == 1:
    stx,sty = 0,0
    for k,v in pos_dic.items():
        glx, gly = k,v
    ans = bfs(stx, sty, glx, gly)
else:
    for k,v in pos_dic.items():
        stx, sty = k,v
        for kk, vv in pos_dic.items():
            glx, gly = kk, vv
            tmp = bfs(stx, sty, glx, gly)
            ans = min(ans, tmp)

print(ans)

Buggy submission (verdict: Runtime Error):
from collections import deque

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

def cand_pos(i,j):
    neighbor = []
    if i==0:
        neighbor.append(maze[i+1][j])
    elif i==h-1:
        neighbor.append(maze[i-1][j])
    else:
        neighbor.append(maze[i+1][j])
        neighbor.append(maze[i-1][j])
    
    if j==0:
        neighbor.append(maze[i][j+1])
    elif j==w-1:
        neighbor.append(maze[i][j-1])
    else:
        neighbor.append(maze[i][j+1])
        neighbor.append(maze[i][j-1])
    
    if maze[i][j]!='#' and neighbor.count('.')==1:
        return True
    else:
        return False


# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs(sx,sy,gx,gy):
    # すべての点を INF で初期化
    d = [[float("inf")] * w for i in range(h)]

    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

pos_dic = {}
for i in range(h):
    for j in range(w):
        if cand_pos(i,j):
            pos_dic[i] = j
        else:
            continue

ans = 0

if len(pos_dic) == 0:
    ans = h+w-2
elif len(pos_dic) == 1:
    stx,sty = 0,0
    for k,v in pos_dic.items():
        glx, gly = k,v
    ans = bfs(stx, sty, glx, gly)
else:
    for k,v in pos_dic.items():
        stx, sty = k,v
        for kk, vv in pos_dic.items():
            glx, gly = kk, vv
            tmp = bfs(stx, sty, glx, gly)
            ans = min(ans, tmp)
print(ans)