Problem p02579 (python)

Fixed submission:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy

sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]



def main(H, W, c_h, c_w, d_h, d_w):

    que = deque([(c_h, c_w)])
    INF = 1e9
    dist = [[INF]*W for _ in range(H)]
    dist[c_h][c_w] = 0
    while que:
        # print(que)
        tmp = que.popleft()
        h, w = tmp
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d:
                continue
            dist[new_h][new_w] = d
            que.appendleft((new_h, new_w))
        # 魔法
        for m_dy in range(-2, 3):
            for m_dx in range(-2, 3):
                new_h = h + m_dy
                new_w = w + m_dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if board[new_h][new_w] == '#':
                    continue
                if dist[new_h][new_w] <= d + 1:
                    continue
                dist[new_h][new_w] = d + 1
                que.append((new_h, new_w))

    ans = dist[d_h][d_w]
    if ans == INF:
        print(-1)
    else:
        print(ans)


H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
for i in range(H):
    tmp = S()
    board.append(tmp)
main(H, W, c_h, c_w, d_h, d_w)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
import numba
from numba import njit, b1, i4, i8, f8
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(H, W, c_h, c_w, d_h, d_w):

    que = deque([(c_h, c_w)])
    INF = 1e9
    dist = [[INF]*W for _ in range(H)]
    dist[c_h][c_w] = 0
    while que:
        # print(que)
        tmp = que.popleft()
        h, w = tmp
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d:
                continue
            dist[new_h][new_w] = d
            que.appendleft((new_h, new_w))
        # 魔法
        for m_dy in range(-2, 3):
            for m_dx in range(-2, 3):
                new_h = h + m_dy
                new_w = w + m_dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if board[new_h][new_w] == '#':
                    continue
                if dist[new_h][new_w] <= d + 1:
                    continue
                dist[new_h][new_w] = d + 1
                que.append((new_h, new_w))

    ans = dist[d_h][d_w]
    if ans == INF:
        print(-1)
    else:
        print(ans)


H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
for i in range(H):
    tmp = S()
    board.append(tmp)
main(H, W, c_h, c_w, d_h, d_w)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
import numba
from numba import njit, b1, i4, i8, f8
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main():
    H, W = zz()

    c_h, c_w = zz()
    d_h, d_w = zz()
    board = []
    c_h -= 1
    c_w -= 1
    d_h -= 1
    d_w -= 1
    for i in range(H):
        tmp = S()
        board.append(tmp)

    que = deque([(c_h, c_w)])
    INF = 1e9
    dist = [[INF]*W for _ in range(H)]
    dist[c_h][c_w] = 0
    while que:
        # print(que)
        tmp = que.popleft()
        h, w = tmp
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d:
                continue
            dist[new_h][new_w] = d
            que.appendleft((new_h, new_w))
        # 魔法
        for m_dy in range(-2, 3):
            for m_dx in range(-2, 3):
                new_h = h + m_dy
                new_w = w + m_dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if board[new_h][new_w] == '#':
                    continue
                if dist[new_h][new_w] <= d + 1:
                    continue
                dist[new_h][new_w] = d + 1
                que.append((new_h, new_w))

    ans = dist[d_h][d_w]
    if ans == INF:
        print(-1)
    else:
        print(ans)


main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main():
    H, W = zz()

    c_h, c_w = zz()
    d_h, d_w = zz()
    board = []
    c_h -= 1
    c_w -= 1
    d_h -= 1
    d_w -= 1
    for i in range(H):
        tmp = S()
        board.append(tmp)

    que = deque([(c_h, c_w)])
    INF = 1e9
    dist = [[INF]*W for _ in range(H)]
    dist[c_h][c_w] = 0
    while que:
        # print(que)
        tmp = que.popleft()
        h, w = tmp
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d:
                continue
            dist[new_h][new_w] = d
            que.appendleft((new_h, new_w))
        # 魔法
        for m_dy in range(-2, 3):
            for m_dx in range(-2, 3):
                new_h = h + m_dy
                new_w = w + m_dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if board[new_h][new_w] == '#':
                    continue
                if dist[new_h][new_w] <= d + 1:
                    continue
                dist[new_h][new_w] = d + 1
                que.append((new_h, new_w))

    ans = dist[d_h][d_w]
    if ans == INF:
        print(-1)
    else:
        print(ans)


main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


@njit
def main():
    H, W = zz()

    c_h, c_w = zz()
    d_h, d_w = zz()
    board = []
    c_h -= 1
    c_w -= 1
    d_h -= 1
    d_w -= 1
    for i in range(H):
        tmp = S()
        board.append(tmp)

    que = deque([(c_h, c_w)])
    INF = 1e9
    dist = [[INF]*W for _ in range(H)]
    dist[c_h][c_w] = 0
    while que:
        # print(que)
        tmp = que.popleft()
        h, w = tmp
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d:
                continue
            dist[new_h][new_w] = d
            que.appendleft((new_h, new_w))
        # 魔法
        for m_dy in range(-2, 3):
            for m_dx in range(-2, 3):
                new_h = h + m_dy
                new_w = w + m_dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if board[new_h][new_w] == '#':
                    continue
                if dist[new_h][new_w] <= d + 1:
                    continue
                dist[new_h][new_w] = d + 1
                que.append((new_h, new_w))

    ans = dist[d_h][d_w]
    if ans == INF:
        print(-1)
    else:
        print(ans)


main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


H, W = zz()

c_h, c_w = zz()
d_h, d_w = zz()
board = []
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
for i in range(H):
    tmp = S()
    board.append(tmp)

que = deque([(c_h, c_w)])
INF = 1e9
dist = [[INF]*W for _ in range(H)]
dist[c_h][c_w] = 0
while que:
    # print(que)
    tmp = que.popleft()
    h, w = tmp
    d = dist[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '#':
            continue
        if dist[new_h][new_w] <= d:
            continue
        dist[new_h][new_w] = d
        que.appendleft((new_h, new_w))
    # 魔法
    for m_dy in range(-2, 3):
        for m_dx in range(-2, 3):
            new_h = h + m_dy
            new_w = w + m_dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d + 1:
                continue
            dist[new_h][new_w] = d + 1
            que.append((new_h, new_w))

ans = dist[d_h][d_w]
if ans == INF:
    print(-1)
else:
    print(ans)

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
from scipy.special import comb
import copy
import networkx as nx
sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


def dijkstra(path, N, start):
    visited = [False] * N
    que = [(0, start)]
    heapify(que)  # 始点aから各頂点への(距離, 頂点ID)
    dist = [-1] * N  # 始点aから各頂点への距離
    dist[start] = 0  # 始点aからaへの距離は0
    while que:
        d, v = heappop(que)  # 始点から最短距離の頂点を(確定ノード)を取り出す
        visited[v] = True  # 確定フラグを立てる
        # 接続先ノードの情報を更新する
        for d, to in path[v]:
            cost = dist[v] + d
            if dist[to] < 0 or cost < dist[to]:
                dist[to] = cost
                if not visited[to]:
                    heappush(que, (cost, to))
    return dist


# MAGIC = ((-2, -2), (-1, -2), (0, -2), (1, -2), (2, -2),
#          (-2, -1), (-1, -1), (0, -1), (1, -1), (2, -1),
#          (-2, 0), (-1, 0), (0, 0), (1, 0), (2, 0),
#          (-2, 1), (-1, 1), (0, 1), (1, 1), (2, 1),
#          (-2, -2), (-1, 2), (0, 2), (1, 2), (2, 2))

MAGIC = ((-2, -2), (-1, -2), (1, -2), (2, -2),
         (-2, -1), (-1, -1),  (1, -1), (2, -1),
         (-2, 1), (-1, 1), (1, 1), (2, 1),
         (-2, -2), (-1, 2), (1, 2), (2, 2))
H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
N = H*W
for i in range(H):
    tmp = S()
    # N += tmp.count('.')
    board.append(tmp)
G = nx.Graph()
path = [[] for _ in range(N)]
for h in range(H):
    for w in range(W):
        if board[h][w] == '.':
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if(board[new_h][new_w] == '.'):
                    # path[h*W + w].append((0, new_h*W + new_w))
                    # path[new_h*W + new_w].append((0, h*W + w))
                    G.add_edge(h*W + w, new_h*W + new_w, weight=0)
                else:
                    #  隣は壁
                    new_h = h + dy*2
                    new_w = w + dx*2
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):  # 2個先は存在
                        # path[h*W + w].append((1, new_h*W + new_w))
                        # path[new_h*W + new_w].append((1, h*W + w))
                        G.add_edge(h*W + w, new_h*W + new_w, weight=1)
                for dy, dx in MAGIC:
                    new_h = h + dy
                    new_w = w + dx
                    if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                        continue
                    if(board[new_h][new_w] == '.'):
                        # path[h*W + w].append((1, new_h*W + new_w))
                        # path[new_h*W + new_w].append((1, h*W + w))
                        G.add_edge(h*W + w, new_h*W + new_w, weight=1)

c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
# dist = dijkstra(path, N, c_h * W + c_w)
length = nx.dijkstra_path_length(G, c_h * W + c_w, d_h*W+d_w)
print(length)

"""

print(board)
que = deque([[c_h, c_w]])
visited = []
# bfs()
while que:
    h, w = que.popleft()
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        new_h = h + dy
        new_w = w + dx
        if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
            continue
        if board[new_h][new_w] == '.':  # セルが白('.')であるのと同義
            que.append((new_h, new_w))

    print(h, w)
"""