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: Wrong Answer

Solution code:
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 = [list(input()) for _ in range(H)]
used = [[-float("inf")] * (W) for _ in range(H)]


x = []
for i in range(5):
    for j in range(5):
        if i == 3 and j == 3:
            continue
        x.append((i-2, j-2))
x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
x = x - y

from collections import deque
q = deque()
q.append((ch, cw, 0))
while q:
    h, w, c = q.popleft()
    for hh, ww in y:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == ".":
            if used[h+hh][w+ww] < 0 or used[h+hh][w+ww] > c:
                used[h+hh][w+ww] = c
                q.append((h+hh, w+ww, c))
    for hh, ww in x:
        if h+hh >= 0 and h+hh < H and w+ww >= 0 and w+ww < W and S[h+hh][w+ww] == "." and used[h+hh][w+ww] < 0:
            if used[h+hh][w+ww] < 0 or used[h+hh][w+ww] > c+1: 
                used[h+hh][w+ww] = c + 1
                q.append((h+hh, w+ww, c+1))
if used[dh][dw] < 0:
    print(-1)
else:
    print(used[dh][dw])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]

INF = h + w + 1
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = []
dxy2 += [(i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy2 += [(i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy2 += [(-1, -1), (-1, +1), (+1, -1), (+1, +1)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)
# print(*cost, sep='\n')

Submission status: Wrong Answer

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

from heapq import heappush, heappop

def resolve():
    H, W = iim()
    Ch, Cw = iim()
    Dh, Dw = iim()
    W1 = W+4; H1 = H+4

    ok = "."
    X = "XX"
    XX = X * W1

    S = XX + "".join(X + input() + X for i in range(H)) + XX

    pos1 = W1 * (Ch+1) + (Cw+1)
    pos2 = W1 * (Dh+1) + (Dw+1)

    inf = H1*W1+1
    dp = [inf] * (H1*W1)
    step = [1+W1, W1-1,-1-W1, 1-W1]

    dq = []
    heappush(dq, (0, pos1))
    vis = set()

    while dq:
        n, p0 = heappop(dq)

        if p0 in vis:
            continue
        if p0 == pos2:
            print(n)
            return
        vis.add(p0)
        dp[p0] = min(dp[p0], n)

        x1 = 0
        for i, j, x in ((1, W1, 9), (-1, W1, 6), (W1, 1, 3), (-W1, 1, 12)):
            p1 = p0 + i

            if S[p1] == ok:
                heappush(dq, (n, p1))
                continue
            elif S[p1] == X:
                continue

            x1 |= x
            n1 = n + 1
            for k in (i-j, i, i+j):
                p2 = p1 + k
                if S[p2] == ok:
                    heappush(dq, (n1, p1))
                    continue

        if not x:
            continue

        for i in range(4):
            if 1<<i & x1 == 0:
                continue

            p1 = p0
            j = step[i]
            for i in range(2):
                p1 += j
                if S[p1] == ok:
                    heappush(dq, (n1, p1))
                elif S[p1] == X:
                    break
    print(-1)

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]

INF = h + w + 1
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = []
dxy2 += [(i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy2 += [(i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy2 += [(-1, -1), (-1, +1), (+1, -1), (+1, +1)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] < c:
        continue

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)
print(*cost, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
visited = [[False] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, 0, 0, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2]
que = deque()
que.append((ch, cw))
while que:
    y, x = que.popleft()
    if visited[y][x]:
        continue
    visited[y][x] = True
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] == grid[y][x] + 1:
                grid[ny][nx] = grid[y][x]
                que.appendleft((ny, nx))
    for i in range(16):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#" and grid[py][px] == -1:
            grid[py][px] = grid[y][x] + 1
            que.append((py, px))

print(grid[dh][dw])

Submission status: Wrong Answer

Solution code:
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)]

res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
count = 0

que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0

while (que or que_warp):
    while (que):
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)

    count += 1

    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)

print (res_S[Dh-1][Dw-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI_()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch, cw))
    c[(ch, cw)] = 0
    nq = deque()
    nq.append((ch, cw))
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[(nh, nw)]
            for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                    c[(mh, mw)] = now
                    q.appendleft((mh, mw))
                    nq.append((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[(nh, nw)]
            for i in range(-2, 3):
                i += nh
                if 0 <= i < h:
                    si = s[i]
                    for j in range(-2, 3):
                        j += nw
                        if 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                            c[(i, j)] = now + 1
                            q.append((i, j))
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    h, w = LI()
    ch, cw = LI()
    dh, dw = LI_()
    # from time import time
    # st = time()
    s = SR(h)
    q = deque()
    c = defaultdict(lambda :inf)
    q.append((ch, cw))
    c[(ch, cw)] = 0
    nq = deque()
    nq.append((ch, cw))
    while 1:
        while q:
            nh, nw = q.popleft()
            now = c[(nh, nw)]
            for mh, mw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
                mh += nh
                mw += nw
                if 0 <= mh < h and 0 <= mw < w and c[(mh, mw)] > now and s[mh][mw] == ".":
                    c[(mh, mw)] = now
                    q.appendleft((mh, mw))
                    nq.append((mh, mw))
        while nq:
            nh, nw = nq.popleft()
            now = c[(nh, nw)]
            for i in range(-2, 3):
                i += nh
                if 0 <= i < h:
                    si = s[i]
                    for j in range(-2, 3):
                        j += nw
                        if 0 <= j < w and c[(i, j)] > now + 1 and si[j] == ".":
                            c[(i, j)] = now + 1
                            q.append((i, j))
        if len(q) == 0:
            break
    print(-1 if c[(dh, dw)] == inf else c[(dh, dw)])
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [0]*h
for i in range(h):
	s[i] =  input()
	s[i] = list(s[i])
 
def clear_maze(sx, sy, gx, gy, maze):
 
	INF = 100000000
 
	field_x_length = len(maze)
	field_y_length = len(maze[0])
	distance = [[INF for i in range(field_y_length)] for j in range(field_x_length)]
#	distance = [[INF]*field_y_length]*field_x_length
 
	def bfs():
		count = 0
		queue = []
 
		queue.insert(0, (sx, sy))
 
		distance[sx][sy] = 0
 
		while len(queue):
			x, y = queue.pop()
 
			if x == gx and y == gy:
				break
 
			for i in range(0, 24):
				if i <= 3:
					nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
				if i >= 4:
					nx, ny = x + [-1, 1, 1, -1, -2, -1, 0, 1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2][i-4], y + [1, 1, -1, -1, 2, 2, 2, 2, 2, 1, 0, -1, -2, -2, -2, -2, -2, -1, 0, 1][i-4]
				if (i <= 3 and 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
					count += 1
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y]
				if (i >= 4 and count ==0 and 0 <= nx and nx < field_x_length and 0 <= ny and ny < field_y_length and maze[nx][ny] != '#' and distance[nx][ny] == INF):
					queue.insert(0, (nx, ny))
					distance[nx][ny] = distance[x][y] + 1
			count = 0
		return distance[gx][gy]
	return bfs()
if clear_maze(ch-1, cw-1, dh-1, dw-1, s) == 100000000:
	print(-1)
else:
	print(clear_maze(ch-1, cw-1, dh-1, dw-1, s))

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

h, w = map(int, input().split())
ch, cw = map(lambda x: int(x) - 1, input().split())
dh, dw = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]

INF = h + w + 1
cost = [[INF] * w for _ in range(h)]
dx = [+1, 0, -1, 0]
dy = [0, +1, 0, -1]
dxy2 = []
dxy2 += [(i, j) for i in [-2, 2] for j in range(-2, 3)]
dxy2 += [(i, j) for j in [-2, 2] for i in range(-1, 2)]
dxy2 += [(-1, -1), (-1, +1), (+1, -1), (+1, +1)]
q = [(0, ch, cw)]
cost[ch][cw] = 0
while q:
    c, x, y = heappop(q)
    if cost[x][y] <= c:
        continue

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c:
            continue
        cost[nx][ny] = c
        heappush(q, (c, nx, ny))

    for dx_, dy_ in dxy2:
        nx = x + dx_
        ny = y + dy_
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if s[nx][ny] == '#':
            continue
        if cost[nx][ny] <= c + 1:
            continue
        cost[nx][ny] = c + 1
        heappush(q, (c + 1, nx, ny))

ans = -1 if cost[dh][dw] == INF else cost[dh][dw]
print(ans)
# print(*cost, sep='\n')

Submission status: Wrong Answer

Solution code:
import queue
import heapq

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

def bfs(ch,cw):
    q = []
    S[ch][cw] = 0
    cd = 0
    heapq.heappush(q,(cd,[ch,cw]))
    while q:
        cd,p = heapq.heappop(q)
        if p[0]==dh and p[1]==dw:
            break
            
        for i in range(4):
            next_p = [p[0]+dx[i],p[1]+dy[i]]
            if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                continue
            if S[next_p[0]][next_p[1]] > cd:
                S[next_p[0]][next_p[1]] = cd
                heapq.heappush(q,(cd,next_p))
                
                
        for i in range(-2,3):
            for j in range(-2,3):
                if (i == 0 and j == 0) or (i==-1 and j==0)or(i==1 and j==0)or(i==0 and j==-1)or (i==0 and j==1):
                    continue
                next_p = [p[0]+i,p[1]+j]
                if next_p[0]<0 or next_p[1]<0 or next_p[0]>=h or next_p[1]>=w:
                    continue
                if S[next_p[0]][next_p[1]] > cd+1:
                    S[next_p[0]][next_p[1]] = cd+1
                    heapq.heappush(q,(cd,next_p))
                    
            
    return 
        
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 = [list(input()) for _ in range(h)]

for i in range(h):
    for j in range(w):
        if S[i][j] == '.':
            S[i][j] = float('inf')
        else:
            S[i][j] = -1


bfs(ch,cw)
if S[dh][dw] != float('inf'):
    print(S[dh][dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		#print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				for t in [-2,-1,0,1,2]:
					if xx==0:
						if S[x+t][y+2*yy]==".":
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
						elif S[x+t][y+2*yy]=="#":
							pass
						elif S[x+t][y+2*yy]>d+1:
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
						elif S[x+2*xx][y+t]=="#":
							pass
						elif S[x+2*xx][y+t]>d+1:
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]<d:
				S[x][y]=S[x+xx][y+yy]
				heapq.heappush(Q,[S[x+xx][y+yy],x,y])


	#print(S[2:-2])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x)-1 for x in input().split())
dh, dw = (int(x)-1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, 0, 0, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2]
que = deque()
que.append((ch, cw))
while que:
    y, x = que.popleft()
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] == grid[y][x] + 1:
                grid[ny][nx] = grid[y][x]
                que.appendleft((ny, nx))
    for i in range(16):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#" and grid[py][px] == -1:
            grid[py][px] = grid[y][x] + 1
            que.append((py, px))

print(grid[dh][dw])

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

import heapq

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["#"]*(w+4)]
	S.append(["#"]*(w+4))
	for _ in range(h):
		S.append(["#"]*2+list(RD())+["#"]*2)
	S.append(["#"]*(w+4))
	S.append(["#"]*(w+4))

	#print(S)

	Q=[[0,ch,cw]]
	heapq.heapify(Q)
	S[ch][cw]=0

	#print(Q)

	while Q:
		print(Q)
		d,x,y=heapq.heappop(Q)

		if S[x][y]<d:
			continue

		for xx,yy in [[0,1],[0,-1],[1,0],[-1,0]]:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="#":
				for t in [-2,-1,0,1,2]:
					if xx==0:
						if S[x+t][y+2*yy]==".":
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
						elif S[x+t][y+2*yy]=="#":
							pass
						elif S[x+t][y+2*yy]>d+1:
							S[x+t][y+2*yy]=d+1
							heapq.heappush(Q,[d+1,x+t,y+2*yy])
					else:
						if S[x+2*xx][y+t]==".":
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
						elif S[x+2*xx][y+t]=="#":
							pass
						elif S[x+2*xx][y+t]>d+1:
							S[x+2*xx][y+t]=d+1
							heapq.heappush(Q,[d+1,x+2*xx,y+t])
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				heapq.heappush(Q,[d,x+xx,y+yy])
			elif S[x+xx][y+yy]<d:
				S[x][y]=S[x+xx][y+yy]
				heapq.heappush(Q,[S[x+xx][y+yy],x,y])


	print(S[2:-2])

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque

h,w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())

G = []
for i in range(h):
    G.append(list(input()))

queue = deque([(ch-1, cw-1)])
S = [[float("inf")]*w for _ in range(h)]
S[ch-1][cw-1] = 0

while queue:
    y, x = queue.popleft()
    for i in range(-1, 2):
        for j in range(-1, 2):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x]
                        queue.appendleft((y+j, x+i))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if i != 0 and j != 0:
                if 0 <= x+i < w and 0 <= y+j < h:
                    if S[y+j][x+i] > S[y][x] and G[y+j][x+i] == ".":
                        S[y+j][x+i] = S[y][x] + 1
                        queue.append((y+j, x+i))


if S[dh-1][dw-1] == float("inf"):
    print(-1)
else:
    print(S[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
from collections import deque

def resolve():
    H,W = map(int, input().split())

    # [0] = h, [1] = w
    C_h, C_w = map(int, input().split())
    C = (C_h-1, C_w-1)
    D_h, D_w = map(int, input().split())
    D = (D_h-1, D_w-1)

    S = []
    for _ in range(H):
        S.append(list(input()))

    # next[i] = (point, d)
    # d = distance from C
    next = deque([(C, 0)])
    visited = set()
    ans = -1

    while next:
        A, d = next.popleft()
        if A in visited:
            continue
        curr = deque([A])

        while curr:
            B = curr.popleft()
            if B in visited:
                continue
            visited.add(B)
            if B == D:
                if ans == -1:
                    ans = d
                else:
                    ans = min(ans, d)

            h,w = B

            # top
            if h-1 >= 0:
                top = (h-1, w)
                if S[h-1][w] == ".":
                    if top not in visited:
                        curr.append(top)
                else:
                    if h-2 >= 0:
                        next_h = h-2
                        if S[next_h][w] == ".":
                            point = (next_h, w)
                            if point not in visited:
                                next.append((point, d+1))
                        if w-1 >= 0 and S[next_h][w-1] == ".":
                            point = (next_h, w-1)
                            if point not in visited:
                                next.append((point, d+1))
                        if w-2 >= 0 and S[next_h][w-2] == ".":
                            point = (next_h, w-2)
                            if point not in visited:
                                next.append((point, d+1))
                        if w+1 < W and S[next_h][w+1] == ".":
                            point = (next_h, w+1)
                            if point not in visited:
                                next.append((point, d+1))
                        if w+2 < W and S[next_h][w+2] == ".":
                            point = (next_h, w+2)
                            if point not in visited:
                                next.append((point, d+1))

            # left
            if w-1 >= 0:
                left = (h, w-1)
                if S[h][w-1] == ".":
                    if left not in visited:
                        curr.append(left)
                else:
                    if w-2 >= 0:
                        if S[h][w-2] == ".":
                            point = (h, w-2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h-1 >= 0 and S[h-1][w-2] == ".":
                            point = (h-1, w-2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h-2 >= 0 and S[h-2][w-2] == ".":
                            point = (h-2, w-2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h+1 < H and S[h+1][w-2] == ".":
                            point = (h+1, w-2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h+2 < H and S[h+2][w-2] == ".":
                            point = (h+2, w-2)
                            if point not in visited:
                                next.append((point, d+1))

            # right
            if w+1 < W:
                right = (h, w+1)
                if S[h][w+1] == ".":
                    if right not in visited:
                        curr.append(right)
                else:
                    if w+2 < W:
                        if S[h][w+2] == ".":
                            point = (h, w+2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h-1 >= 0 and S[h-1][w+2] == ".":
                            point = (h-1, w+2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h-2 >= 0 and S[h-2][w+2] == ".":
                            point = (h-2, w+2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h+1 < H and S[h+1][w+2] == ".":
                            point = (h+1, w+2)
                            if point not in visited:
                                next.append((point, d+1))
                        if h+2 < H and S[h+2][w+2] == ".":
                            point = (h+2, w+2)
                            if point not in visited:
                                next.append((point, d+1))


            # bottom
            if h+1 < H:
                bottom = (h+1, w)
                if S[h+1][w] == ".":
                    if bottom not in visited:
                        curr.append(bottom)
                else:
                    if h+2 < H:
                        if S[h+2][w] == ".":
                            point = (h+2, w)
                            if point not in visited:
                                next.append((point, d+1))
                        if w-1 >= 0 and S[h+2][w-1] == ".":
                            point = (h+2, w-1)
                            if point not in visited:
                                next.append((point, d+1))
                        if w-2 >= 0 and S[h+2][w-2] == ".":
                            point = (h+2, w-2)
                            if point not in visited:
                                next.append((point, d+1))
                        if w+1 < W and S[h+2][w+1] == ".":
                            point = (h+2, w+1)
                            if point not in visited:
                                next.append((point, d+1))
                        if w+2 < W and S[h+2][w+2] == ".":
                            point = (h+2, w+2)
                            if point not in visited:
                                next.append((point, d+1))

    print(ans)
    
resolve()

Submission status: Wrong Answer

Solution code:
import sys, math, heapq

# input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [[1 if s=='.' else 0 for s in input()] for _ in range(H)]
costs = [[math.inf]*W for _ in range(H)]
costs[Ch-1][Cw-1] = 0
hq = [(0, Ch-1, Cw-1)]
heapq.heapify(hq)

while len(hq)>0:
    c, h, w = heapq.heappop(hq)
    for i, j in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
        if i < 0 or j < 0 or i>=H or j>=W:
            continue
        if i == Dh - 1 and j == Dw - 1:
            print(c)
            sys.exit()
        if S[i][j] and costs[i][j] > c:
            costs[i][j] = c
            heapq.heappush(hq, (c, i, j))
    for dw in [-2, -1, 0, 1, 2]:
        for dh in [-2, -1, 0, 1, 2]:
            if w+dw < 0 or h+dh < 0 or w+dw>=W or h+dh>=H:
                continue
            if w+dw == Dw-1 and h+dh==Dh-1:
                print(c+1)
                sys.exit()
            if S[h+dh][w+dw] and costs[h+dh][w+dw] > c+1:
                costs[h+dh][w+dw] = c+1
                heapq.heappush(hq, (c+1, h+dh, w+dw))

print(-1)