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:
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop
 
# sys.setrecursionlimit(5000)
 
n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]
 
def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)
 
H, W = nn()
Ch, Cw = nn()
Dh, Dw = nn()
S = sm(H)
 
T = [u"#"*(W+4)] * 2
for s in S:
    T.append("##" + s[0] + "##")
T += [u"#"*(W+4)] * 2
 
H += 4
W += 4
Ch += 2 - 1
Cw += 2 - 1
Dh += 2 - 1
Dw += 2 - 1
 
deq1 = deque()
deq1.append((Ch, Cw))
deq2 = deque()
 
cnt = 0
 
memo = array2(H, W, 10**6)
memo[Ch][Cw] = 0
 
memo2 = deque()
memo2.append((Ch, Cw))

for i in range(10**6):
    #pprint(T)
    #pprint(memo)
    #print("-"*30 + "\n")
 
    if len(deq1) == 0:
        print(-1)
        exit(0)
 
    while len(deq1) > 0:
        h, w = deq1.pop()
 
        if h == Dh and w == Dw:
            print(i)
            exit(0)
 
        def sch(x, y, i):
            #print(x, y, T[x][y])
            if T[x][y] == "." and i < memo[x][y]:
                memo[x][y] = i
                deq1.append((x, y))
                memo2.append((x, y))
 
        sch(h+1, w, i)
        sch(h-1, w, i)
        sch(h, w+1, i)
        sch(h, w-1, i)
 
    #for j in range(H):
    #    for k in range(W):
    while len(memo2) > 0:
        j, k = memo2.pop()
        if memo[j][k] == i:
            for l in range(-2, 3):
                for m in range(-2, 3):
                    if T[j+l][k+m] == "." and i + 1 < memo[j+l][k+m]:
                        memo[j+l][k+m] = i + 1
                        deq2.append((j+l, k+m))
 
    deq1 = deq2
    deq2 = deque()
    memo2 = deque()

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = set()
        for s in S[max(0, i-2):i+2]:
            g |= set(s[max(0, j-2):j+2])
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True
can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()
reached = set([s])
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    ans += 1
    new_reached = []
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[p]:
                new_reached.append(p)
    reached = list(set(new_reached))
print(-1)

Submission status: Wrong Answer

Solution code:
H,W = map(int, input().strip().split())
Ch, Cw = map(int, input().strip().split())
Dh, Dw = map(int, input().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

moves=[]
for i in range(H):
    moves.append([1000000]*W)

for i in range(H):
    s = input().strip()
    for j in range(W):
        if s[j] == '#':
            moves[i][j] = -1

moves[Ch][Cw]=0
sources_0 = [[-1,0],[1,0],[0,-1],[0,1]]
sources_1 = [[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2]]
sources_1 += [[-2,-1],[-1,-1],[0,-1],[1,-1],[2,-1]]
sources_1 += [[-2,0],[-1,0],[1,0],[2,0]]
sources_1 += [[-2,1],[-1,1],[0,1],[1,1],[2,1]]
sources_1 += [[-2,2],[-1,2],[0,2],[1,2],[2,2]]

def not_concluded():
    for i in range(H):
        for j in range(W):
            if moves[i][j] == 1000000:
                return True
    return False

n = 0
while (not_concluded() and n <= H*W):
    n += 1
    for i in range(H):
        for j in range(W):
            if moves[i][j] <= 0:
                continue
            for src in sources_0:
                if i+src[0] >= 0 and i+src[0] < H and j+src[1] >= 0 and j+src[1] < W:
                    src_move = moves[i+src[0]][j+src[1]]
                    if src_move >= 0 and src_move < moves[i][j]:
                        moves[i][j] = src_move
            for src in sources_1:
                if i+src[0] >= 0 and i+src[0] < H and j+src[1] >= 0 and j+src[1] < W:
                    src_move = moves[i+src[0]][j+src[1]]
                    if src_move >= 0 and src_move + 1 < moves[i][j]:
                        moves[i][j] = src_move + 1

if moves[Dh][Dw] == 1000000:
    print(-1)
else:
    print(moves[Dh][Dw])

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '#':
            S[i][j] = WALL
        else:
            S[i][j] = INI

S[Ch][Cw] = 0
d = deque()
d.append((Ch, Cw))

direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]

is_goal = False
while len(d):
    y, x = d.popleft()
    warp = False
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            d.append((next_y, next_x))
            S[next_y][next_x] = S[y][x]
        if S[next_y][next_x] == WALL:
            warp = True
        if next_y == Dh and next_x == Dw:
            is_goal = True

    if warp:
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                next_y = y + dy
                next_x = x + dx
                if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                    continue
                if S[next_y][next_x] == INI:
                    d.append((next_y, next_x))
                    S[next_y][next_x] = S[y][x] + 1
                if next_y == Dh and next_x == Dw:                    
                    is_goal = True
    if is_goal:
        break

if is_goal:
    print(S[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    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

    maze = list()
    arrived = [[0 for i in range(W)] for j in range(H)]
    arrived[Ch][Cw] = 1

    for i in range(H):
        maze.append(list(input()))

    ans = 0
    while (Ch != Dh) and (Cw != Dw):

        update_flag = 0
        if Cw + 1 < W and maze[Ch][Cw + 1] == "." and arrived[Ch][Cw + 1] == 0:
            Cw += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch + 1 < H and maze[Ch + 1][Cw] == "." and arrived[Ch + 1][Cw] == 0:
            Ch += 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Cw - 1 > 0 and maze[Ch][Cw - 1] == "." and arrived[Ch][Cw - 1] == 0:
            Cw -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1
        elif Ch - 1 > 0 and maze[Ch - 1][Cw] == "." and arrived[Ch - 1][Cw] == 0:
            Ch -= 1
            arrived[Ch][Cw] = 1
            update_flag = 1

        if update_flag == 0:
            find = 0
            for i in range(2, -3, -1):
                for j in range(2, -3, -1):
                    x = Cw + j
                    y = Ch + i

                    if 0 <= y < H and 0 <= x < W:
                        if y == Dh and x == Dw:
                            Ch = Dh
                            Cw = Dw
                            find = 1
                            ans += 1
                            update_flag = 1
                            break

                if find == 1:
                    break

            if update_flag == 0:
                find = 0
                for i in range(2, -3, -1):
                    for j in range(2, -3, -1):
                        x = Cw + j
                        y = Ch + i

                        if 0 <= y < H and 0 <= x < W:
                            if maze[y][x] == "." and arrived[y][x] == 0:
                                Ch = y
                                Cw = x
                                find = 1
                                ans += 1
                                break

                    if find == 1:
                        break

                if find == 0:
                    print(-1)
                    exit()
                    
    print(ans)

if __name__ == "__main__":
    main()

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):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp2=[[0]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue = deque([[ch-1, cw-1]])
while queue:  
  x,y=queue.popleft()
  for i,j in [[1,0],[-1,0],[0,1],[0,-1],[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=temp[x][y]:
      continue
    if (i==1 and j==0) or (i==-1 and j==0) or (i==0 and j==1) or (i==0 and j==-1):
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y])
    else:
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y]+1)
    if temp2[xtemp][ytemp]==0:
      temp2[xtemp][ytemp]=1
      queue.append([xtemp,ytemp])

if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			if getMaze(x - 1, y) == ".":
				graph[y][x].append((x - 1, y, 0))
			if getMaze(x + 1, y) == ".":
				graph[y][x].append((x + 1, y, 0))
			if getMaze(x, y - 1) == ".":
				graph[y][x].append((x, y - 1, 0))
			if getMaze(x, y + 1) == ".":
				graph[y][x].append((x, y + 1, 0))
			for i in range(-2, 2+1):
				if i in (1, -1):
					continue
				for j in range(-2, 2+1):
					if j in (1, -1):
						continue
					if getMaze(x + i, y + j) == ".":
						graph[y][x].append((x + i, y + j, 1))


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[-1]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		if dist[y][x] == -1:
			dist[y][x] = 0
		d = dist[y][x]
		nexts = graph[y][x]
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] != -1:
				dist[ny][nx] = min(dist[ny][nx], d + cost)
				continue
			dist[ny][nx] = d + cost
			stack.append((nx, ny))
	log.print(dist)
	print(dist[dh-1][dw-1])
	
	


main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)

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

maze = [list(input()) for i in range(h)]

maze_deque = deque([[ch, cw]])
warp_deque = deque([[ch, cw]])

warp = 0

while True:
    while maze_deque:
        x, y = maze_deque.pop()
        for i, j in ([1, 0], [0, 1], [-1, 0], [0, -1]):
            tx, ty = x + i, y + j
            # 到達
            if tx == dh and ty == dw:
                print(warp)
                sys.exit()
            # 探索
            elif (0 <= tx < h) and (0 <= ty < w) and maze[tx][ty] == ".":
                maze[tx][ty] = "!"
                warp_deque.append([tx, ty])
                maze_deque.append([tx, ty])

    warp += 1

    while warp_deque:
        x, y = warp_deque.pop()
        for ta in range(5):
            for tb in range(5):
                tx, ty = x - 2 + ta, y - 2 + tb
                # ワープした先で到達
                if tx == dh and ty == dw:
                    print(warp)
                    sys.exit()
                # ワープ先が未到達なら
                elif (0 <= tx < h) and (0 <= ty < w) and maze[tx][ty] == ".":
                    maze[tx][ty] = "!"
                    maze_deque.append([tx, ty])

    if len(maze_deque) == 0:
        print(-1)
        sys.exit()

Submission status: Wrong Answer

Solution code:
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
cy -= 1
cx -= 1
dy -= 1
dx -= 1

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

worps = [[float('inf')]*W for _ in range(H)]
used = [[False]*W for _ in range(H)]
q = deque([[cy, cx]])

worp = 0
while q:
    v = {}
    while q:
        y, x = q.popleft()
        used[y][x] = True
        worps[y][x] = min(worps[y][x], worp)

        for h in range(-2+y, 3+y):
            for w in range(-2+x, 3+x):
                if 0 <= h and h < H and 0 <= w and w < W and S[h][w] == "." and not used[h][w]:
                    v[(h, w)] = True

        for h, w in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            ny, nx = y+h, x+w
            if 0 <= ny and ny < H and 0 <= nx and nx < W:
                if not used[ny][nx] and S[ny][nx] == ".":
                    q.append([ny, nx])

    worp += 1
    for h, w in v.keys():
        if not used[h][w]:
            q.append([h, w])
            used[h][w] = True
            break

ans = worps[dy][dx]
if ans != float('inf'):
    print(ans)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
#abc176-d
import sys,math,collections,itertools
input = sys.stdin.readline

H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]

#DPで遷移が2種類　初期値をinf として、現在値より小さければ遷移可能とする
dp = [ [float('inf') ]*W  for _ in range(H)]

q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    nh,nw = q.popleft()
    case = []
    #徒歩での遷移
    if nh>0 and s[nh-1][nw] =='.' and dp[nh-1][nw]>dp[nh][nw]:
        q.append((nh-1,nw))
        dp[nh-1][nw] = dp[nh][nw]
    elif nh>0 and s[nh-1][nw] =='#': #上が壁だったら　上辺壁抜けワープ遷移
        for ih in range(-2,-1,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
                       
    
    if nh<H-1 and s[nh+1][nw] =='.' and dp[nh+1][nw]>dp[nh][nw]:
        q.append((nh+1,nw))
        dp[nh+1][nw] = dp[nh][nw]
    elif nh<H-1 and s[nh+1][nw] =='#':#下が壁だったら　下辺壁抜けワープ遷移
        for ih in range(2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1

        
    if nw>0 and s[nh][nw-1] =='.' and dp[nh][nw-1]>dp[nh][nw]:
        q.append((nh,nw-1))
        dp[nh][nw-1] = dp[nh][nw]
    elif nw>0 and s[nh][nw-1] =='#': #左が壁     
        for ih in range(-2,3,1):
            for iw in range(-2,-1,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1   
        
    if nw<W-1 and s[nh][nw+1] =='.' and dp[nh][nw+1]>dp[nh][nw]:
        q.append((nh,nw+1))
        dp[nh][nw+1] = dp[nh][nw]
    elif nw<W-1 and s[nh][nw+1] =='#': #右が壁     
        for ih in range(-2,3,1):
            for iw in range(2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1   

ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement, groupby
from math import sqrt, ceil, floor, factorial, gcd
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
import sys  # def input(): return sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**6)

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))
count = 0
while True:
    flag = False
    if not que:
        for y in range(h):
            for x in range(w):
                if grid[y][x] == count:
                    que.append((y, x))
                    flag = True
    else:
        flag = True
    if not flag:
        break
    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.append((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
    count += 1
    if grid[dh][dw] != -1:
        break

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())
maze = [[9]*(w+2)]
for i in range(h):
  s = input()
  tmp = [9]
  for i in s:
    if i == "#":
      tmp.append(9)
    else:
      tmp.append(0)
  tmp.append(9)
  maze.append(tmp)
maze.append([9]*(w+2))
#print(maze)

pos = [[ch,cw,0,0]]
while len(pos)>0:
  x, y, depth, hop = pos.pop(0)
  #print(x,y,hop)
  if (x,y) == (dh,dw):
    print(hop)
    break
  
  if maze[x][y] == 2:
    pass
  else:
    maze[x][y] = 2
  
    flag = 0
    if maze[x-1][y] <2:
      pos.append([x-1,y,depth+1,hop])
      flag = 1
    if maze[x+1][y] <2:
      pos.append([x+1,y,depth+1,hop])
      flag = 1
    if maze[x][y-1] <2:
      pos.append([x,y-1,depth+1,hop])
      flag = 1
    if maze[x][y+1] <2:
      pos.append([x,y+1,depth+1,hop])
      flag = 1

    if flag == 0:
      try:
        if maze[x-2][y] <2:
          flag =1
          pos.append([x-2,y,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x-2][y+1] <2:
          flag =1
          pos.append([x-2,y+1,depth+1,hop+1])
      except:
        pass

      try: 
        if maze[x-2][y+2] <2:
          flag =1
          pos.append([x-2,y+2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x-2][y-1] <2:
          flag =1
          pos.append([x-2,y-1,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x-2][y-2] <2:
          flag =1
          pos.append([x-2,y-2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x+2][y] <2:
          flag =1
          pos.append([x+2,y,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x+2][y-1] <2:
          flag=1
          pos.append([x+2,y-1,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x+2][y-2] <2:
          flag=1
          pos.append([x+2,y-2,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x+2][y+1] <2:
          flag=1
          pos.append([x+2,y+1,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x+2][y+2] <2:
          flag=1
          pos.append([x+2,y+2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x][y-2] <2:
          flag=1
          pos.append([x,y-2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x+1][y-2] <2:
          flag=1
          pos.append([x+1,y-2,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x-1][y-2] <2:
          flag=1
          pos.append([x-1,y-2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x][y+2] <2:
          flag=1
          pos.append([x,y+2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x+1][y+2] <2:
          flag=1
          pos.append([x+1,y+2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x-1][y+2] <2:
          flag=1
          pos.append([x-1,y+2,depth+1,hop+1])
      except:
        pass

      try:
        if maze[x-1][y-1] <2:
          flag=1
          pos.append([x-1,y-1,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x-1][y+1] <2:
          flag=1
          pos.append([x-1,y+1,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x+1][y-1] <2:
          flag=1
          pos.append([x+1,y-1,depth+1,hop+1])
      except:
        pass
      try:
        if maze[x+1][y+1] <2:
          flag=1
          pos.append([x+1,y+1,depth+1,hop+1])
      except:
        pass
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if q == goal:
                        return t
                    parent[q[0]][q[1]] = p
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline

road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Submission status: Wrong Answer

Solution code:
from heapq import heappop,heappush
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)]

t = [[[[] for k in range(2)] for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if s[i][j] == '.':
            for x,y in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                if 0<=x < H and 0 <= y < W and s[x][y] == '.':
                    t[i][j][0].append([x,y])
            for x in range(i-2,i+3):
                for y in range(i-2,i+3):
                    if [x,y] in ((i,j),(i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                        pass 
                    else:
                        if 0<=x < H and 0 <= y < W and s[x][y] == '.':
                            t[i][j][1].append([x,y])
                
def dijkstra(x,y):
    node_x = x 
    node_y = y
    weight = {(node_x,node_y):0}
    checklist = []
    heappush(checklist,[0,node_x,node_y])
    while(checklist):
        weight_node,node_x,node_y = heappop(checklist)
        if node_x == dh-1 and node_y == dw-1:
            return weight_node
        for i in range(len(t[node_x][node_y][0])):
            next_x,next_y = t[node_x][node_y][0][i]
            weight_next_node = weight_node
            if (next_x,next_y) not in weight or weight_next_node < weight[(next_x,next_y)]:
                weight[(next_x,next_y)] = weight_next_node
                heappush(checklist,[weight_next_node,next_x,next_y])
        for i in range(len(t[node_x][node_y][1])):
            next_x,next_y = t[node_x][node_y][1][i]
            weight_next_node = weight_node + 1
            if (next_x,next_y) not in weight or weight_next_node < weight[(next_x,next_y)]:
                weight[(next_x,next_y)] = weight_next_node
                heappush(checklist,[weight_next_node,next_x,next_y])
    return -1

print(dijkstra(ch-1,cw-1))