Problem p02579 (python)

Fixed submission:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

# ワープを最低で何回使うか
# 上下左右2つ向こうまでの範囲内でワープできる
# 隣接する'.'が領域

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 歩いて移動
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            # 0-1 bfs
            # 先頭に置く
            pos.appendleft([ny, nx])
            dp[ny][nx] = dp[y][x]
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            # 歩いて移動不可能でないと使わない
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and dp[wy][wx] == -1:
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])

Buggy submission (verdict: Runtime Error):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# 各頂点を変換
def alter(y, x):
    return H * y + x

pos = []

# エッジ生成
for y in range(H):
    for x in range(W):
        if maze[y][x] == '#':
            continue
        # walkingエッジ
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '.':
                pos.append([alter(y, x), alter(ny, nx), 0])
        # warpエッジ
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                if w_y == 0 and w_x == 0:
                    continue
                wy = y + w_y
                wx = x + w_x
                if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == '.':
                    pos.append([alter(y, x), alter(wy, wx), 1])

# 木の生成
def build_tree_dis(N, edge_list):

    G = [[] for i in range(N)]

    for i in range(len(edge_list)):
        a, b, c = edge_list[i]
        G[a].append([b, c])
        # G[b].append([a, c])
        # G[a - 1].append([b - 1, c])
        # G[b - 1].append([a - 1, c])

    """
    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            #leaves.append(i)
    """

    return G

edges = build_tree_dis(H * W, pos)

# ダイクストラ
def dij(start, goal, size):
    dist = [float('inf') for i in range(size)]
    dist[start] = 0
    pq = [(0, start)]

    # pqの先頭がgoal行きのものなら最短距離を返す
    while len(pq) > 0:
        d, now = heappop(pq)
        if (d > dist[now]):
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heappush(pq, (dist[i[0]], i[0]))
    return dist[goal]

ans = dij(alter(Ch, Cw), alter(Dh, Dw), H * W)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

# 各頂点を変換
def alter(y, x):
    return H * y + x

pos = []

# エッジ生成
for y in range(H):
    for x in range(W):
        if maze[y][x] == '#':
            continue
        # walkingエッジ
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == '.':
                pos.append([alter(y, x), alter(ny, nx), 0])
        # warpエッジ
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                if w_y == 0 and w_x == 0:
                    continue
                wy = y + w_y
                wx = x + w_x
                if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == '.':
                    pos.append([alter(y, x), alter(wy, wx), 1])

# 木の生成
def build_tree_dis(N, edge_list):

    G = [[] for i in range(N)]

    for i in range(len(edge_list)):
        a, b, c = edge_list[i]
        G[a].append([b, c])
        # G[b].append([a, c])
        # G[a - 1].append([b - 1, c])
        # G[b - 1].append([a - 1, c])

    """
    # 葉（末端の数）
    leaves = []
    for i in range(N):
        if len(G[i]) == 1:
            #leaves.append(i)
    """

    return G

edges = build_tree_dis(H * W, pos)

# ダイクストラ
def dij(start, goal, size):
    dist = [float('inf') for i in range(size)]
    dist[start] = 0
    pq = [(0, start)]

    # pqの先頭がgoal行きのものなら最短距離を返す
    while len(pq) > 0 and (pq[0][1] != goal):
        d, now = heappop(pq)
        if (d > dist[now]):
            continue
        for i in edges[now]:
            if dist[i[0]] > dist[now] + i[1]:
                dist[i[0]] = dist[now] + i[1]
                heappush(pq, (dist[i[0]], i[0]))
    if len(pq) == 0:
        return -1
    else:
        return pq[0][0]

print(dij(alter(Ch, Cw), alter(Dh, Dw), H * W))