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())
dh, dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
inf = float('inf')
graph = []
for _ in range(H):
    g = input()
    graph.append(g)
    
def get_near(vh, vw):
    next_list = []
    for h, w in [[vh, vw + 1], [vh, vw - 1], [vh - 1, vw], [vh + 1, vw]]:
        if (0 <= h < H) & (0 <= w < W):
                    next_list.append([h, w])
    return next_list

def get_far(vh, vw):
    next_list = []
    for h in range(vh - 2, vh + 3):
        for w in range(vw - 2, vw + 3):
            if 0 <= h < H:
                if 0 <= w < W:
                    next_list.append([h, w])
    return next_list


from collections import deque
path = [[[inf, inf] for _ in range(W)] for _ in range(H)]
d = deque([[ch, cw]])
path[ch][cw] = [0, 0]
while d:
    vh, vw = d.popleft()
    warp = False
    for h, w in get_near(vh, vw):        
        if graph[h][w] != '#':
            if (path[h][w][1] < path[vh][vw][1]):
                d.append([h, w])
                path[h][w] = [path[vh][vw][0] + 1, path[vh][vw][1]]
            elif (path[h][w][0] > path[vh][vw][0] + 1):
                d.append([h, w])
                path[h][w] = [path[vh][vw][0] + 1, path[vh][vw][1]]
        else:
            warp = True
    if warp:
        for h, w in get_far(vh, vw):
            if graph[h][w] != '#':
                if (path[h][w][1] > path[vh][vw][1] + 1):
                    d.append([h, w])
                    path[h][w] = [path[vh][vw][0], path[vh][vw][1] + 1]
ans = path[dh][dw][1]
if ans == inf:
    print(-1)
else:
    print(ans)

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-1, cw-1))
    c[(ch - 1, cw - 1)] = 0
    nq = deque()
    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 <= i < h and 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 = list(map(int, input().split()))
Ch, Cw = list(map(int, input().split()))
Dh, Dw = list(map(int, input().split()))
S = [[o for o in input()] for i in range(H) ]

def dfs(y, x, c):
    S[y][x] = c
    for dy, dx in [(-1,0), (1,0), (0,1), (0,-1)]:
            ny = y+dy
            nx = x+dx
            if nx>=0 and nx<W and ny>=0 and ny<H and S[ny][nx]=='.':
                dfs(ny, nx, c)

c = 0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            dfs(i, j, c)
            c+=1

arr = {i:[] for i in range(c)}

for i in range(H):
    for j in range(W):
        cla = S[i][j]
        if cla!='#':
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx = j+dx
                    ny = i+dy
                    if nx>=0 and nx<W and ny>=0 and ny<H and S[ny][nx]!='#':
                        if S[ny][nx]!=cla and S[ny][nx] not in arr[cla]:
                            arr[cla].append(S[ny][nx])

current = S[Ch-1][Cw-1]
goal = S[Dh-1][Dw-1]
dis = {current:0}
queue = [current]
cnt = 1
while queue:
    now = queue.pop(0)
    if arr[now]!=[]:
        for one in arr[now]:
            if one not in dis:
                dis[one] = cnt
                queue.append(one)
    cnt+=1
if goal in dis:
    print(dis[goal])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
import heapq as hq
import functools, collections
import math, random
from collections import Counter, defaultdict
import threading

# threading.stack_size(2**27)
# sys.setrecursionlimit(10**6 + 5)

# available on Google, not available on Codeforces
# import numpy as np
# import scipy


# https://codeforces.com/blog/entry/80158?locale=en
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


def dijkstra(G, s):
    n = len(G)
    visited = [False]*n
    weights = [math.inf]*n
    path = [None]*n
    queue = []
    weights[s] = 0
    hq.heappush(queue, (0, s))
    while len(queue) > 0:
        g, u = hq.heappop(queue)
        visited[u] = True
        for v, w in G[u]:
            if not visited[v]:
                f = g + w
                if f < weights[v]:
                    weights[v] = f
                    path[v] = u
                    hq.heappush(queue, (f, v))
    return path, weights


def solve(grid, sx, sy, ex, ey):  # fix inputs here
    console("----- solving ------")

    grid = [[0 if cell == "#" else 1 for cell in row] for row in grid]
    grid = [[0] * len(grid[0])]*2 + grid + [[0] * len(grid[0])]*2
    grid = [[0,0] + row + [0,0] for row in grid]
    sx, sy, ex, ey = sx+1, sy+1, ex+1, ey+1

    labels = [[False for _ in row] for row in grid]
    diffs = [(-1,0), (1,0), (0,-1), (0,1)]

    g = defaultdict(set)

    # @bootstrap
    @functools.lru_cache()
    def dfs(var):
        x,y,cur_label = var
        for dx,dy in diffs:
            xx, yy = x+dx, y+dy
            if labels[xx][yy]:
                continue
            if grid[xx][yy] == 0:
                continue
            labels[xx][yy] = cur_label
            var2 = xx,yy,cur_label
            dfs(var2)

    cur_label = 0
    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if labels[i][j]:
                continue
            if cell == 0:
                continue
            cur_label += 1
            labels[i][j] = cur_label
            var = i,j,cur_label
            dfs(var)
            
    console("label")
    console(labels)


    start = labels[sx][sy]
    end = labels[ex][ey]
    console("start and end", start, end)
    if start == end:
        return 0

    connections = defaultdict(set)

    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if cell == 0:
                continue
            for dx in [-2,-1,0,1,2]:
                for dy in [-2,-1,0,1,2]:
                    if labels[i][j] != False and labels[i+dx][j+dy] != False:
                        if labels[i][j] != labels[i+dx][j+dy]:
                            connections[labels[i][j]].add(labels[i+dx][j+dy])
                            connections[labels[i+dx][j+dy]].add(labels[i][j])

    console("connections", connections)

    G = [[] for _ in range(cur_label+1)]

    for k,lst in connections.items():
        G[k].extend([(x,1) for x in lst])

    console("G", G)

    _, result = dijkstra(G, start)
    
    console("result", result)

    if result[end] > 10**4:
        return -1
    return result[end]



def console(*args):  # the judge will not read these print statement
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return

# fast read all
# sys.stdin.readlines()

def main():
    # read line as a string
    # strr = input()

    # read line as an integer
    # k = int(input())
    
    # read one line and parse each word as a string
    # lst = input().split()

    # read one line and parse each word as an integer
    nrows, w = list(map(int,input().split()))
    sx, sy = list(map(int,input().split()))
    ex, ey = list(map(int,input().split()))

    # read matrix and parse as integers (after reading read nrows)
    # lst = list(map(int,input().split()))
    # nrows = lst[0]  # index containing information, please change
    grid = []
    for _ in range(nrows):
        grid.append(list(input()))

    res = solve(grid, sx, sy, ex, ey)  # please change
    
    # Google - case number required
    # print("Case #{}: {}".format(case_num+1, res))

    # Codeforces - no case number required
    print(res)

main()
# t = threading.Thread(target=main)
# t.start()
# t.join()

Submission status: Wrong Answer

Solution code:
# D - Wizard in Maze
from collections import deque
import sys
INF = 10000000

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]
C = [[INF]*W for _ in range(H)]
C[Ch-1][Cw-1] = 0
que = deque([(Ch,Cw)])
now = set()
tmp = 0

while True:
    while len(que)>0:
        i,j = que.popleft()
        now.add((i,j))
        for (h,w) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 1<=h<=H and i<=w<=W and S[h-1][w-1]=='.' and C[h-1][w-1]>tmp:
                C[h-1][w-1] = tmp
                que.append((h,w))
    for i,j in now:
        for h in range(i-2,i+3):
            for w in range(j-2,j+3):
                if 1<=h<=H and 1<=w<=W and S[h-1][w-1]=='.' and C[h-1][w-1]>tmp+1:
                    C[h-1][w-1] = tmp+1
                    que.append((h,w))
    now = set()
    tmp += 1
    if C[Dh-1][Dw-1]!=INF:
        print(C[Dh-1][Dw-1])
        break
    if len(que)==0:
        print(-1)
        break

Submission status: Wrong Answer

Solution code:
import copy

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

meiro = [ ['#'] * (w+4)]
meiro += [ ['#'] * (w+4)]
meiro += [['#'] * 2 + list(input()) + ['#'] * 2 for _ in range(h)]
meiro += [ ['#'] * (w+4)]
meiro += [ ['#'] * (w+4)]

moved = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def label(row, column):
    meiro[row][column] = num
    for i,j in moved:
        if meiro[row+i][column+j] == '.':
            check.append([row+i, column+j])
            label(row+i, column+j)

row = ch + 1
column = cw + 1

num = 0
check = [[row, column]]
label(row, column)

while True:
    num += 1
    check_copy = copy.deepcopy(check)
    check = []
    for i,j in check_copy:
        for s in range(-2, 3):
            for t in range(-2, 3):
                if meiro[i+s][j+t] == '.':
                    label (i+s,j+t)

    if len(check) == 0:
        break

if meiro[dh+1][dw+1] == '.':
    print(-1)
else:
    print(meiro[dh+1][dw+1])

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True

BLOCK = '#'
ROAD = '.'

warps = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) not in [(-1, 0), (0, 1), (1, 0), (0, -1), (0, 0)]:
            warps.append((i, j))

def bfs(graph, initial, goal, H, W):
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    q = deque([(initial, 0)])
    visited = [[False for i in range(W)] for i in range(H)]
    dist = [[-1 for i in range(W)] for i in range(H)]
    visited[initial[0]][initial[1]] = True

    while len(q) != 0:
        p, cnt = q.popleft()
        has_block = False

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j]:
                if graph[i][j] != BLOCK:
                    visited[i][j] = True
                    q.append(((i, j), cnt))

                    if goal[0] == i and goal[1] == j:
                        return cnt
                else:
                    has_block = True

        if has_block:
            for d in warps:
                i = p[0] + d[0]
                j = p[1] + d[1]

                if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] != BLOCK:
                    tmp = cnt + 1
                    visited[i][j] = True
                    q.append(((i, j), tmp))

                    if goal[0] == i and goal[1] == j:
                        return tmp
    return -1


def main():
    H, W = MI()
    CH, CW = MI()
    DH, DW = MI()
    graph = [None] * H
    CH -= 1
    CW -= 1
    DH -= 1
    DW -= 1

    for i in range(H):
        graph[i] = list(S())

        for j in range(W):
            if graph[i][j] == 'S':
                pass

    ret = bfs(graph, (CH, CW), (DH, DW), H, W)
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from itertools import combinations
import sys
from collections import defaultdict, deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
DDX = (-1, 0, 1, 0, -1, -1, 1, 1)
DDY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DDX[:4]
DY = DDY[:4]


H, W = map(int, input().split())
Cx, Cy = map(int, input().split())
Dx, Dy = map(int, input().split())

grid = ["#" * (W + 2)]
for _ in range(H):
    inp = "#" + input().strip() + "#"
    grid.append(inp)
grid.append("#" * (W + 2))


area = [[-1] * (W + 2) for _ in range(H + 2)]
cnt = 0
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == "#" or area[i][j] != -1:
            continue
        cnt += 1
        node = [(i, j)]
        area[i][j] = cnt
        while node:
            x, y = node.pop()
            for dx, dy in zip(DX, DY):
                nx = x + dx
                ny = y + dy
                if grid[nx][ny] == "#":
                    continue
                if area[nx][ny] == -1:
                    area[nx][ny] = cnt
                    node.append((nx, ny))

if area[Cx][Cy] == area[Dx][Dy]:
    print(0)
    exit()


used = defaultdict(int)

edge = [[] for _ in range(cnt + 1)]
for i in range(1, H + 1):
    for j in range(1, W + 1):
        if grid[i][j] == ".":
            continue
        memo = set()
        for dx, dy in zip(DDX, DDY):
            if area[i + dx][j + dy] == -1:
                continue
            memo.add(area[i + dx][j + dy])
        for x, y in combinations(memo, 2):
            if x > y:
                x, y = y, x
            if used[(x, y)]:
                continue
            edge[x].append(y)
            edge[y].append(x)
            used[(x, y)] = 1


dist = [-1] * (cnt + 1)
ci = area[Cx][Cy]
di = area[Dx][Dy]
dist[ci] = 0
node = deque([ci])
while node:
    s = node.popleft()
    for t in edge[s]:
        if dist[t] != -1:
            continue
        dist[t] = dist[s] + 1
        node.append(t)

print(dist[di])

Submission status: Wrong Answer

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(lambda s: int(s) - 1, input().split())
Dh, Dw = map(lambda s: int(s) - 1, input().split())
S = [input() for i in range(H)]

N = [[1000000007] * W for i in range(H)]
visited = [[False] * W for i in range(H)]
q = deque([(Ch, Cw)])
N[Ch][Cw] = 0
while len(q) > 0:
    Ph, Pw = q.popleft()
    if visited[Ph][Pw]:
        continue
    visited[Ph][Pw] = True
    for dh, dw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nh = Ph + dh
        nw = Pw + dw
        if not 0 <= nh < H or not 0 <= nw < W or S[nh][nw] == '#':
            continue
        N[nh][nw] = min(N[nh][nw], N[Ph][Pw])
        if not visited[nh][nw]:
            q.append((nh, nw))
    for dh in range(-2, 3):
        nh = Ph + dh
        if not 0 <= nh < H:
            continue
        for dw in range(-2, 3):
            nw = Pw + dw
            if not 0 <= nw < W or S[nh][nw] == '#':
                continue
            N[nh][nw] = min(N[nh][nw], N[Ph][Pw] + 1)
            if not visited[nh][nw]:
                q.append((nh, nw))

print(N[Dh][Dw] if visited[Dh][Dw] else -1)

Submission status: Wrong Answer

Solution code:
import collections

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

Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

dist = [[-1 for _ in range(W)] for _ in range(H)]
dist[Ch][Cw] = 0

q = collections.deque([(Ch, Cw)])
q2 = collections.deque()
while q:
    while q:
        y, x = q.pop()

        walk = False
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                if S[ny][nx] == '.':
                    q.append((ny, nx))
                    dist[ny][nx] = dist[y][x]
                    walk = True

        if not walk:
            q2.append((y, x))

    while q2:
        y, x = q2.pop()
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                ny = y + dy
                nx = x + dx
                if 0 <= ny < H and 0 <= nx < W and dist[ny][nx] == -1:
                    if S[ny][nx] == '.':
                        q.appendleft((ny, nx))
                        dist[ny][nx] = dist[y][x] + 1

print(dist[Dh][Dw])

Submission status: Wrong Answer

Solution code:
def resolve():
    H, W = list(map(int, input().split()))
    Ch, Cw = list(map(lambda x: int(x)-1, input().split()))
    Dh, Dw = list(map(lambda x: int(x)-1, input().split()))
    S = [list(input()) for _ in range(H)]
    warps = [[-1 for _ in range(W)] for __ in range(H)]
    warpcnt = 0
    import collections
    warp_to = set()
    q = collections.deque([(Ch, Cw)])
    while q:
        while q:
            h, w = q.pop()
            if warps[h][w] != -1:
                continue
            warps[h][w] = warpcnt
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nh = h+dh
                nw = w+dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and warps[nh][nw] == -1:
                    q.appendleft((nh, nw))
            for dh, dw in [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2)
                        ,(-1, -2), (-1, -1),          (-1, 1), (-1, 2)
                        ,(0, -2),                              (-1, 2)
                        ,(1, -2),  (1, -1),           (1, 1),  (1, 2)
                        ,(2, -2),  (2, -1),  (2, 0),  (2, 1),  (2, 2)]:
                nh = h+dh
                nw = w+dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and warps[nh][nw] == -1:
                    warp_to.add((nh, nw))
        q = collections.deque(list(warp_to))
        warp_to = set()
        warpcnt += 1
    print(warps[Dh][Dw])

if '__main__' == __name__:
    resolve()

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 _ in range(h)]

ch-=1
cw-=1
dh-=1
dw-=1

dy=[1, 0, -1, 0]
dx=[0, 1, 0 ,-1]
mx=[-2, -2, -2, -2, -2, -1, -1, -1, -1, -1,  0,  0, 0, 0,  1,  1, 1, 1, 1,  2,  2,  2,  2,  2]
my=[-2, -1,  0,  1,  2, -2, -1,  0,  1,  2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1,  0,  1,  2]

from collections import deque
ans=0

d=[[-1]*w for _ in range(h)]
queue=deque()
queue.append((ch, cw))
visited=deque()
visited.append((ch, cw))
d[ch][cw]=0

while queue:
    y,x=queue.popleft()

    for d_y, d_x in zip(dy, dx):
        new_y=y+d_y
        new_x=x+d_x
        if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
            continue
        if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
            d[new_y][new_x]=d[y][x]
            queue.append((new_y, new_x))
            visited.append((new_y, new_x))

    if not queue:
        while visited:
            y,x=visited.popleft()
            for m_x, m_y in zip(mx, my):
                new_y=y+m_y
                new_x=x+m_x
                if new_y<0 or h<=new_y or new_x<0 or w<=new_x:
                    continue
                if s[new_y][new_x]=='.' and d[new_y][new_x]==-1:
                    d[new_y][new_x]=d[y][x]+1
                    queue.append((new_y, new_x))

print(d[dh][dw])

Submission status: Wrong Answer

Solution code:
import math
from functools import reduce
from collections import deque
from heapq import heappush, heappop
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def neighbors4(x, y):
  dxy = (0, 1, 0, -1, 0 )
  for i in range(4):
    yield(x + dxy[i], y + dxy[i+1])

def search(cost, sx, sy):
    que = deque()
    que.append((sx,sy))

    reached = []

    while que:
        x,y = que.popleft()

        # 訪れた場所リスト
        reached.append((x,y))

        if cost_map[y][x] <= cost:
            continue
        cost_map[y][x] = cost

        for x2, y2 in neighbors4(x,y):
            if x2<0 or x2>=w or y2<0 or y2>=h:
                continue
            if grid_s[y2][x2] == ".":
                que.append((x2, y2))
    
    return reached

def jump(cost, x, y):
    if cost >= cost_map[y][x]:
        return
    reached = search(cost, x, y)
    
    # ゴールに到達したらおわり
    if cost_map[dh][dw] != INF:
        print(cost_map[dh][dw])
        return
    
    # 1回ジャンプする
    for x,y in reached:
        for y2 in range(max(0, y-2), min(h, y+3)):
            for x2 in range(max(0, x-2), min(w, x+3)):
                if abs(x-x2) + abs(y-y2) < 2:
                    continue
                if grid_s[y2][x2] == "." and cost_map[y2][x2] > cost+1:
                    heappush(jump_heap, (cost+1, x2, y2))



def main():
    global h,w,dh,dw,grid_s,cost_map, jump_heap,INF
    INF = 999999999999999999999999
    MOD = 10**9+7

    h,w = get_nums_l()

    ch,cw = get_nums_l()
    dh,dw = get_nums_l()
    ch -= 1
    cw -= 1
    dh -= 1
    dw -= 1

    grid_s = []
    for i in range(h):
        grid_s.append(input())
    
    cost_map = [[INF] * w for _ in range(h) ]

    jump_heap = [(0, cw, ch)]

    while jump_heap:
        cost, x, y = heappop(jump_heap)
        jump(cost, x, y)
    
    if cost_map[dh][dw] == INF:
        print(-1)

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

que = deque()
memo_que = deque()
que.append([ch - 1, cw - 1, 0])
memo_que.append([ch - 1, cw - 1, 0])
memo = {}
memo[(ch - 1, cw - 1)] = 0
ans = float("inf")
while len(que) != 0:
    while len(que) != 0:
        sh, sw, count = que.popleft()
        #print(sh, sw, count)
        if sh == dh - 1 and sw == dw - 1:
            if ans > count:
                memo[(sh, sw)] = count
                ans = count
            continue
        for ph, pw in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            if 0 <= sh + ph < h and 0 <= sw + pw < w:
                if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count:
                    continue
                if slist[sh + ph][sw + pw] == ".":
                    que.append([sh + ph, sw + pw, count])
                    memo[(sh + ph, sw + pw)] = count
                    memo_que.append([sh + ph, sw + pw, count])

    for sh, sw, count in memo_que:
        #print(sh, sw, count)
        for ph in range(-2, 3):
            for pw in range(-2, 3):
                if [ph, pw] not in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
                    if 0 <= sh + ph < h and 0 <= sw + pw < w:
                        if (sh + ph, sw + pw) in memo and memo[(sh + ph, sw + pw)] <= count + 1:
                            continue
                        if slist[sh + ph][sw + pw] == ".":
                            que.append([sh + ph, sw + pw, count + 1])
                            memo[(sh + ph, sw + pw)] = count + 1
    memo_que.clear()

if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
H,W=[int(i) for i in input().split(" ")]
Ch, Cw=[int(i)+1 for i in input().split(" ")]
Dh,Dw=[int(i)+1 for i in input().split(" ")]
S=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    assert S[h][w]
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(2,H+2):
    for w in range(2,W+2):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while len(nexts)!=0:
    for n in nexts:
        _nexts=[]
        for neigh in neighbor[n]:
            assert neigh!=-1
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
    nexts=set(_nexts)

if dist[goal]==10**10:
    print(-1)
else:
    print(dist[goal])

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)

        ok = False
        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])
                    ok = True
        if not ok:
            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

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

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