Problem p02579 (python)

Fixed submission:
from collections import deque


H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[10**9+7] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        h, w = queue.popleft()
        d = dist[h][w]
        flag = 0
        for vh,vw in walk:
            nh = h + vh
            nw = w + vw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        queue.append([nh,nw])
                else:
                        flag += 1
        if flag:
            queue2.append([h,w])
            
    while len(queue2) > 0:
        h, w = queue2.popleft()
        for vh in range(-2,3):
            for vw in range(-2,3):
                nh = h + vh
                nw = w + vw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == '.' and dist[nh][nw] == 10**9+7:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append([nh,nw])
                
if dist[Dh][Dw] != 10**9+7:
    print(dist[Dh][Dw])
else:
    print(-1)

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


H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]
INF = float('inf')

dist = [[INF] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        x, y = queue.popleft()
        d = dist[y][x]
        flag = 0
        for vx,vy in walk:
            nx = x + vx
            ny = y + vy
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                if S[ny][nx] == '.':
                    if dist[ny][nx] > d:
                        dist[ny][nx] = d
                        queue.append([nx,ny])
                else:
                        flag += 1
        if flag:
            queue2.append([x,y])
            
    while len(queue2) > 0:
        x, y = queue2.popleft()
        for vx in range(-2,3):
            for vy in range(-2,3):
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny< W:
                    if S[ny][nx] == '.' and dist[ny][nx] == 10**9+7:
                        dist[ny][nx] = dist[y][x] + 1
                        queue.append([nx,ny])
                
if dist[Dh][Dw] != INF:
    print(dist[Dh][Dw])
else:
    print(-1)

Buggy submission (verdict: Runtime Error):
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[10**9+7 for _ in range(W)] for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = []
queue.append([Ch,Cw])
queue2 = []
dist[Ch2][Cw2] = 0
    
while len(queue) > 0:
    while len(queue) > 0:
        x, y = queue.pop(0)
        d = dist[x][y]
        flag = 0
        for vx in range(-1,2):
            for vy in range(-1,2):
                if [vx,vy] in [[1,1],[1,-1],[-1,-1],[-1,1]]:
                    continue
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny < W:
                    if S[nx][ny] == '.':
                        if dist[nx][ny] > d:
                            dist[nx][ny] = d
                            queue.append([nx,ny])
                    else:
                        flag += 1
        if flag:
            queue2.append([x,y])
            
    while len(queue2) > 0:
        x, y = queue2.pop(0)
        for vx in range(-2,3):
            for vy in range(-2,3):
                nx = x + vx
                ny = y + vy
                if 0 <= nx and nx < H and 0 <= ny and ny< W:
                    if S[nx][ny] == '.' and dist[nx][ny] == 10**9+7:
                        dist[nx][ny] = dist[x][y] + 1
                        queue.append([nx,ny])
                
print(dist[Dh][Dw])

Buggy submission (verdict: Runtime Error):
def solve():
    h, w = map(int,input().split())
    ch, cw = map(int,input().split())
    dh, dw = map(int,input().split())
    
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    
    
    s = ["#"*(w+4)]
    s.append("#"*(w+4))
    for i in range(h):
        s.append("##" + input()[:-1] + "##")
    s.append("#"*(w+4))
    s.append("#"*(w+4))
    
    
    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
             (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), \
             (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), \
             (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), \
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
        
    not_yet = [(ch, cw)]
    one_time = []
    
    while len(not_yet) > 0:
        x, y = not_yet.pop()
        one_time.append((x, y))
        for (p, q) in move:
            v1, v2 = x+p, y+q
            if ans[v1][v2] == -1:
                not_yet.append((v1, v2))
                ans[v1][v2] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.pop()
                for (v1, v2) in move2:
                    i, j = x2+v1, y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        not_yet.append((i, j))
    print(ans[dh][dw])
      
solve()

Buggy submission (verdict: Runtime Error):
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[-1 for _ in range(W)] for _ in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            dist[h][w] = -2
Ch2 = Ch-1
Cw2 = Cw-1
Dh2 = Dh-1
Dw2 = Dw-1

queue = []
queue.append([Ch2,Cw2])
queue2 = []
dist[Ch2][Cw2] = 0
    
while len(queue) > 0:
    x, y = queue.pop(0)
    if x == Dw and y == Dh:
        break
    queue2.append([x,y])
    for vx in range(-1,2):
        for vy in range(-1,2):
            nx = x + vx
            ny = y + vy
            if abs(vx) == abs(vy):
                continue
            if 0 <= nx and nx < W and 0 <= ny and ny < H:
                if dist[nx][ny] != '#' and dist[nx][ny] == -1:
                    queue.append([nx,ny])
                    dist[nx][ny] = dist[x][y]
                    
    if len(queue) == 0:
        while len(queue2) > 0:
            x, y = queue2.pop(0)
            if x == Dw and y == Dh:
                break
            for vx in range(-2,3):
                for vy in range(-2,3):
                    nx = x + vx
                    ny = y + vy
                    if 0 <= nx and nx < W and 0 <= ny and ny < H:
                        if dist[nx][ny] != '#' and dist[nx][ny] == -1:
                            queue.append([nx,ny])
                            dist[nx][ny] = dist[x][y] + 1
                
print(dist[Dh2][Dw2])

Buggy submission (verdict: Runtime Error):
def C_BFS2(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs2(maze, row, column, sy, sx, gy, gx):
        tmp = [[2,2],[2,1],[2,0],[2,-1],[2,-2],\
       [1,2],[1,-2],[0,2],[0,-2],\
       [-1,2],[-1,-2],\
       [-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                 # ゴール座標と一致するなら
                break
            for i in range(16):
                nx = x + tmp[i][0]
                ny = y + tmp[i][1]
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    if dist[ny][nx] > dist[y][x]:
                        dist[ny][nx] = dist[y][x]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs2(maze, R, C, sy, sx, gy, gx)
    return ans
  
  def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
            if x == gx and y == gy:
                break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x]
                    # （追記）距離の最大値を更新する
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]
import sys
# スタート地点は全て試す
dist_ans = 0
dist_tmp = C_BFS(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
INF = float('inf')
if dist_tmp == 0:
    print(0)
    sys.exit()
else:
    dist_ans = 0
    dist_tmp = C_BFS2(H, W, Ch, Cw, Dh, Dw, S) # 今回、 gy, gx は不要
    INF = float('inf')
    if dist_tmp == INF:
        print(-1)
    else:
        print(dist_tmp)