Problem:


Score : 400 points

Problem Statement

A maze is composed of a grid of H \times W squares - H vertical, W horizontal.

The square at the i-th row from the top and the j-th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is ..

There is a magician in (C_h,C_w). He can do the following two kinds of moves:

Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.

Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.

In either case, he cannot go out of the maze.

At least how many times does he need to use the magic to reach (D_h, D_w)?

Constraints

1 \leq H,W \leq 10^3

1 \leq C_h,D_h \leq H

1 \leq C_w,D_w \leq W

S_{ij} is # or ..

S_{C_h C_w} and S_{D_h D_w} are ..

(C_h,C_w) \neq (D_h,D_w)

Input

Input is given from Standard Input in the following format:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

Output

Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w), print -1 instead.

Sample Input 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

Sample Output 1

1

For example, by walking to (2,2) and then using the magic to travel to (4,4), just one use of magic is enough.

Note that he cannot walk diagonally.

Sample Input 2

4 4
1 4
4 1
.##.
####
####
.##.

Sample Output 2

-1

He cannot move from there.

Sample Input 3

4 4
2 2
3 3
....
....
....
....

Sample Output 3

0

No use of magic is needed.

Sample Input 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

Sample Output 4

2



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Runtime Error

Solution code:
import heapq
import sys

def in_grid(temp, h, w, s):
	if 0 <= temp[0] and temp[0] < w and 0 <= temp[1] and temp[1] < h:
		return s[temp[0]][temp[1]] == "."
	return False

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 = [list(input()) for i in range(h)]

drc = [[1,0], [-1,0], [0,1], [0,-1]]
openl = [[0, ch, cw]]
closel = []

while True:
	if not openl:
		break
	
	now = heapq.heappop(openl)
	if now[1] == dh and now[2] == dw:
		print(now[0])
		sys.exit()

	heapq.heappush(closel, [now[1], now[2]])
	for i in drc:
		temp = [now[1] + i[0], now[2] + i[1]]
		if in_grid(temp, h, w, s) and not temp in closel:
			heapq.heappush(openl, [now[0], temp[0], temp[1]])
	
	for i in range(2, 6):
		for k in range(2, 6):
			temp = [now[1] + i, now[2] + k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] - i, now[2] + k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] + i, now[2] - k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
			temp = [now[1] - i, now[2] - k]
			if in_grid(temp, h, w, s) and not temp in closel:
				heapq.heappush(openl, [now[0] + 1, temp[0], temp[1]])
				
print(-1)

Submission status: Runtime Error

Solution code:
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
# 同一の集合の判定
def same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False
# 集合の併合
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x

# 集合の数
def uCnt(x):
    return -par[find(x)]

N, M = map(int, input().split())
par = [-1 for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    unite(a - 1, b - 1)

ans = min(par)
print(-ans)

Submission status: Runtime Error

Solution code:
    from collections import deque
    INF = float("inf")
     
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch, cw = ch-1, cw-1
    dh, dw = dh-1, dw-1
    S = [input() for _ in range(h)]
     
    dist = [[INF] * w for _ in range(h)]
    dist[ch][cw] = 0
    q = deque([(cw, ch)])
     
    while q:
        x, y = q.popleft()
        for _x in range(-2, 3):
            for _y in range(-2, 3):
                if _x == _y == 0:
                    continue
                next_x, next_y = x + _x, y + _y
                if not 0 <= next_x < w:
                    continue
                if not 0 <= next_y < h:
                    continue
                if S[next_y][next_x] == "#":
                    continue
                if abs(_x) + abs(_y) <= 1:
                    if dist[next_y][next_x] <= dist[y][x]:
                        continue
                    q.appendleft((next_x, next_y))
                    dist[next_y][next_x] = dist[y][x]
                else:
                    if dist[next_y][next_x] <= dist[y][x] + 1:
                        continue
                    q.append((next_x, next_y))
                    dist[next_y][next_x] = dist[y][x] + 1
     
    if dist[dh][dw] != INF:
        print(dist[dh][dw])
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
from collections import deque
infty = 10 ** 12

def BFS(dist):
    start = (C_H-1)*H + C_W-1
    queue = deque()
    queue.append((start, 0))
    searched = [False for k in range(len(dist))] #少なくとも1回探索されたか否か
    determined = [False for k in range(len(dist))] #最短距離が決まったか否か
    L = 1
    searched[start] = True
    while queue:
        add_v = 0
        while L > 0:
            v = queue.popleft()
            if not determined[v[0]]:
                determined[v[0]] = True
                dist[v[0]] = v[1]
            L -= 1
            row = v[0]//H
            col = v[0]%H
            for k in range(5):
                for l in range(5):
                    if S_extended[row + k][col + l] == "." and not searched[(row+k-2)*H + col+l-2]:
                        searched[(row + k - 2)*H + col + l - 2] = True
                        add_v += 1
                        if (k, l) == (2, 2):
                            continue
                        elif (k, l) in [(1, 2), (2, 1), (2, 3), (3, 2)]:
                            queue.appendleft(((row + k - 2)*H + col + l - 2, v[1]))
                        else:
                            queue.append(((row + k - 2)*H + col + l - 2, v[1]+1))
        L = add_v

H, W = map(int, input().split())
C_H, C_W = map(int, input().split())
D_H, D_W = map(int, input().split())

graph = [[] for i in range(H * W)]
S = []
for i in range(H):
    S.append(input())

s = ""
for j in range (W+4):
    s += "#"
S_extended = [s, s]
for i in range(H):
    S_extended.append("##" + S[i] + "##")
S_extended.append(s)
S_extended.append(s)

dist = [infty for i in range(H*W)]
BFS(dist)
if dist[(D_H - 1) * H + D_W-1] == infty:
    print("-1")
else:
    print(dist[(D_H - 1) * H + D_W-1])

Submission status: Runtime Error

Solution code:
from collections import deque
infty = 10 ** 12

def BFS(dist):
    start = (C_H-1)*H + C_W-1
    queue = deque()
    queue.append((start, 0))
    searched = [False for k in range(len(dist))] #少なくとも1回探索されたか否か
    determined = [False for k in range(len(dist))] #最短距離が決まったか否か
    L = 1
    searched[start] = True
    while queue:
        add_v = 0
        while L > 0:
            v = queue.popleft()
            if not determined[v[0]]:
                determined[v[0]] = True
                dist[v[0]] = v[1]
            L -= 1
            row = v[0]//H
            col = v[0]%H
            for k in range(5):
                for l in range(5):
                    if S_extended[row + k][col + l] == "." and not determined[(row+k-2)*H + col+l-2]:
                        searched[(row + k - 2)*H + col + l - 2] = True
                        add_v += 1
                        if (k, l) == (2, 2):
                            continue
                        elif (k, l) in [(1, 2), (2, 1), (2, 3), (3, 2)]:
                            queue.appendleft(((row + k - 2)*H + col + l - 2, v[1]))
                        else:
                            queue.append(((row + k - 2)*H + col + l - 2, v[1]+1))
        L = add_v

H, W = map(int, input().split())
C_H, C_W = map(int, input().split())
D_H, D_W = map(int, input().split())

graph = [[] for i in range(H * W)]
S = []
for i in range(H):
    S.append(input())

s = ""
for j in range (W+4):
    s += "#"
S_extended = [s, s]
for i in range(H):
    S_extended.append("##" + S[i] + "##")
S_extended.append(s)
S_extended.append(s)

dist = [infty for i in range(H*W)]
BFS(dist)
if dist[(D_H - 1) * H + D_W-1] == infty:
    print("-1")
else:
    print(dist[(D_H - 1) * H + D_W-1])

Submission status: Runtime Error

Solution code:
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'
    cell_list = list()

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W, cell_list)
    print(answer)


def resolve(q, S, D, H, W, cell_list):
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W, cell_list)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    cell_list = list()
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = Queue()
    q.put((0, Ch - 1, Cw - 1))
    S[Ch - 1][Cw - 1] = '1'

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(S)
    print(answer)


def resolve(q, S, D, H, W):
    cell_list = list()
    while not q.empty():
        worp_count, x, y = q.get()
        S[x][y] = '2'
        cell_list.append((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q.put((worp_count, i, j))
                S[i][j] = '1'

    if not cell_list:
        return -1

    for x, y in cell_list:
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q.put((worp_count + 1, x + i, y + j))
                S[x + i][y + j] = '1'

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
infty = 10 ** 12

def BFS(graph, dist):
    start = (C_H-1)*H + C_W-1
    queue = deque()
    queue.append((start, 0))
    searched = [False for k in range(len(dist))] #少なくとも1回探索されたか否か
    determined = [False for k in range(len(dist))] #最短距離が決まったか否か
    L = 1
    searched[start] = True
    while queue:
        add_v = 0
        while L > 0:
            v = queue.popleft()
            if not determined[v[0]]:
                determined[v[0]] = True
                dist[v[0]] = v[1]
            L -= 1
            for j in graph[v[0]]:
                if not determined[j]:
                    queue.appendleft((j, v[1]))
                    searched[j] = True
                    add_v += 1
            row = v[0]//H
            col = v[0]%H
            for k in range(5):
                for l in range(5):
                    if S_extended[row + k][col + l] == "." and not determined[(row+k-2)*H + col+l-2]:
                        searched[(row+k-2)*H + col+l-2] = True
                        queue.append(((row + k - 2)*H + col + l - 2, v[1]+1))
                        add_v += 1
        L = add_v

H, W = map(int, input().split())
C_H, C_W = map(int, input().split())
D_H, D_W = map(int, input().split())

graph = [[] for i in range(H * W)]
S = []
for i in range(H):
    S.append(input())

s = ""
for j in range (W+4):
    s += "#"
S_extended = [s, s]
for i in range(H):
    S_extended.append("##" + S[i] + "##")
S_extended.append(s)
S_extended.append(s)

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if i != 0 and S[i - 1][j] == ".":
                graph[i * H + j].append((i-1)*H + j)
            if j != 0 and S[i][j-1] == ".":
                graph[i * H + j].append(i*H + j-1)
            if i != H-1 and S[i+1][j] == ".":
                graph[i*H+j].append((i+1)*H + j)
            if j != W-1 and S[i][j+1] == ".":
                graph[i*H+j].append(i*H + j+1)


dist = [infty for i in range(H*W)]
BFS(graph, dist)
if dist[(D_H - 1) * H + D_W-1] == infty:
    print("-1")
else:
    print(dist[(D_H - 1) * H + D_W-1])

Submission status: Runtime Error

Solution code:
# 正解ではない

from queue import Queue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q1 = Queue()
    q2 = Queue()
    q1.put((0, Ch - 1, Cw - 1))

    answer = resolve(q1, q2, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q1, q2, S, D, H, W):
    while not q1.empty():
        worp_count, x, y = q1.get()
        if S[x][y] == '/':
            continue
        S[x][y] = '/'
        q2.put((x, y))

        if (x, y) == D:
            return worp_count

        for i, j in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
            if 0 <= i < H and 0 <= j < W and S[i][j] == '.':
                q1.put((worp_count, i, j))

    if q2.empty():
        return -1

    while not q2.empty():
        x, y = q2.get()
        for i, j in [(a, b) for a in range(-2, 3) for b in range(-2, 3)]:
            if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                q1.put((worp_count + 1, x + i, y + j))

    return resolve(q1, q2, S, D, H, W)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
# 正解ではない

from queue import PriorityQueue


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [list(input()) for i in range(H)]
    q = PriorityQueue()
    q.put((0, (Ch - 1, Cw - 1)))

    answer = resolve(q, S, (Dh - 1, Dw - 1), H, W)
    print(answer)


def resolve(q, S, D, H, W):
    is_empty = True
    location_list = set()
    while not q.empty():
        worp_count, (x, y) = q.get()
        S[x][y] = '/'
        is_empty = False

        if (x, y) == D:
            return worp_count

        location_list.add((x, y))
        if 0 <= x - 1 < H and S[x - 1][y] == '.':
            q.put((worp_count, (x - 1, y)))
        elif 0 <= x + 1 < H and S[x + 1][y] == '.':
            q.put((worp_count, (x + 1, y)))
        elif 0 <= y - 1 < W and S[x][y - 1] == '.':
            q.put((worp_count, (x, y - 1)))
        elif 0 <= y + 1 < W and S[x][y + 1] == '.':
            q.put((worp_count, (x, y + 1)))

    if is_empty:
        return -1

    for i in range(-2, 3):
        for j in range(-2, 3):
            for x, y in location_list:
                if 0 <= x + i < H and 0 <= y + j < W and S[x + i][y + j] == '.':
                    q.put((worp_count + 1, (x + i, y + j)))

    return resolve(q, S, D, H, W)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = ""
for h in range(H):
    S += input()
    
G = [{} for i in range(H*W)]
INF = 10**18
@jit
for h in range(H):
    for w in range(W):
        now = h * W + w
        if now != "#":
            # left
            t = now - 1
            if  h * W <= t:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # right
            t = now + 1
            if  h * W <= t < (h+1) * W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # up
            t = now - W
            if 0 <= t < H*W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # down
            t = now + W
            if 0 <= t < H*W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
        
            # Warp
            for hh in range(-2, 3):
                t = (h+hh)*W + w
                #print(now)
                for i in range(-2, 3):
                    t_ = t + i
                    G[now][t_] = 1

Submission status: Runtime Error

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = ""
for h in range(H):
    S += input()
    
G = [{} for i in range(H*W)]
INF = 10**18
for h in range(H):
    for w in range(W):
        now = h * W + w
        if now != "#":
            # left
            t = now - 1
            if  h * W <= t:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # right
            t = now + 1
            if  h * W <= t < (h+1) * W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # up
            t = now - W
            if 0 <= t < H*W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # down
            t = now + W
            if 0 <= t < H*W:
                if S[t] == "#":
                    G[now][t] = INF
                else:
                    G[now][t] = 0
            # Warp
            for hh in range(-2, 3):
                t = (h+hh)*W + w
                #print(now)
                for i in range(-2, 3):
                	G[now][t_] = 1

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
#wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]


for j in ww:
    for i in hh[0:-1]:
        if s[i+1][j]==".": g[i][j].append((i+1,j))        
        if s[i][j]==".": g[i+1][j].append((i,j))        
for i in hh:
    for j in ww[0:-1]:
        if s[i][j+1]==".": g[i][j].append((i,j+1))        
        if s[i][j]==".": g[i][j+1].append((i,j))        print(-2)

#for i in hh:
#    for j in ww:
#        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
for i in hh:
    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#for i in hh:
#    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if wpg2[i][j]>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:
import sys
from collections import deque

def input(): return sys.stdin.readline().strip()

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
#wpg2=[[0]*w for i in range(h)]
wpg2=[[[] for i in range(w)] for i in range(h)]
wpg=[]

for i in hh:
    for j in ww:
        g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")]
#        wpg2[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")]
#for i in hh:
#    for j in ww:
        if i+1<h and s[i+1][j]=="#": wpg2[i][j]=1
        elif 0<=i-1 and s[i-1][j]=="#": wpg2[i][j]=1
        elif j+1<w and s[i][j+1]=="#": wpg2[i][j]=1
        elif 0<=j-1 and s[i][j-1]=="#": wpg2[i][j]=1
                
#        if (i+1<h and s[i+1][j]=="#") or \
#           (0<=i-1 and s[i-1][j]=="#") or \
#           (j+1<w and s[i][j+1]=="#") or \
#           (0<=j-1 and s[i][j-1]=="#"): 
#            wpg2[i][j]=1


#g=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] for j in ww ] for i in hh]


#wpg2=[[[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]=="#")] for j in ww ] for i in hh]


for i in hh:
    for j in ww:
        if len(wpg2[i][j])>=1:
            wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:
#        print("q1:",q)
        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Submission status: Runtime Error

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
from collections import deque
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

INF=10**9
H,W=nm()
sx,sy=nm()
gx,gy=nm()
mass=[[0 for i in range(H)] for j in range(W)]
edge1=[[[] for i in range(H)] for j in range(W)]
edge2=[[[] for i in range(H)] for j in range(W)]

def bfs(start,edge1,edge2):
    d=[[INF for i in range(1000)] for j in range(1000)]
    d[start[0]][start[1]]=0
    q=deque([start])
    while (q):
        e=q.popleft()
        for i,j in edge1[e[0]][e[1]]:
            if(d[e[0]][e[1]]<d[i][j]):
                d[i][j]=d[e[0]][e[1]]
                q.appendleft((i,j))   
        for i,j in edge2[e[0]][e[1]]:
            if(d[e[0]][e[1]]+1<d[i][j]):
                d[i][j]=d[e[0]][e[1]]+1
                q.append((i,j))   
    return d

for i in range(H):
    t=list(ns())
    for j in range(W):
        if(t[j]=='.'):
            mass[i][j]=1

for i in range(H):
    for j in range(W):
        for k in range(-2,3):
            for l in range(-2,3):
                if((k==0 and l==0) or i+k<0 or j+l<0 or H<(i+k) or W<(j+l)):
                    continue
                else:
                    if(mass[i+k][j+l]==1):
                        if(abs(k)^2+abs(l)^2==1):
                            edge1[i][j].append((i+k,j+l))
                        else:
                            edge2[i][j].append((i+k,j+l))


start=[sx-1,sy-1]
d=bfs(start,edge1,edge2)
if(d[gx-1][gy-1]==INF):
    print(-1)
    sys.exit(0)
print(d[gx-1][gy-1])