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
sys.setrecursionlimit(10**7)
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():

    movex = (1, 0, -1, 0)
    movey = (0, -1, 0, 1)
    warpx = (-2, -2, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
    warpy = (-2, -1, 0, 1, 2, -2, -1, 0, 1, 2,  -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2)
    def dfs1(cur_coor, r):
        for i1 in range(4):
            nextx = cur_coor[1] + movex[i1]
            nexty = cur_coor[0] + movey[i1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r)
                return
            elif nextg == '.':
                maze[nexty][nextx] = '-'
                dfs1((nexty, nextx), r)
            else:
                pass
        for j1 in range(24):
            nextx = cur_coor[1] + warpx[j1]
            nexty = cur_coor[0] + warpy[j1]
            nextg = maze[nexty][nextx]
            if nextg == 'g':
                rs.append(r + 1)
                return
            elif nextg == '.':
                maze[nexty][nextx] = '-'
                dfs1((nexty, nextx), r + 1)
            else:
                pass
    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
    dummy = ['#'] * (w + 4)
    maze = []
    maze.append(dummy)
    maze.append(dummy)
    for _ in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze.append(row)
    maze.append(dummy)
    maze.append(dummy)
    maze[dh][dw] = 'g'

    rs = []
    dfs1((ch, cw), 0)
    if rs:
        print(min(rs))
    else:
        print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import math

H, W = (int(x) for x in input().split())
Ch, Cw = (int(x) for x in input().split())
Dh, Dw = (int(x) for x in input().split())
maze = []

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

for y in range(H):
        for x in range(W):
            if maze[y][x] == '.':
                maze[y][x] = math.inf

maze[Ch - 1][Cw - 1] = 0
que = deque([[Ch - 1,Cw - 1]])

while que:
    y, x = que.popleft()
    for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
        nexty, nextx = y + i , x + j
        if nexty >= 0 and nexty < H and nextx >= 0 and nextx < W:
            dist = maze[nexty][nextx]
            if dist != '#':
                if dist > maze[y][x]:
                    maze[nexty][nextx] = maze[y][x]
                    que.append([nexty,nextx])
        else:
            for k in range(-2, 3):
                if y + k >= 0 and y + k < H:
                    for l in range(-2, 3):
                        if x + l >= 0 and x + l < W and maze[y + k][x + l] != '#':
                            if maze[y + k][x + l] > maze[y][x] + 1:
                                maze[y + k][x + l] = maze[y][x] + 1
                                que.append([y + k,x + l])

if maze[Dh - 1][Dw - 1] != math.inf:
    print(maze[Dh - 1][Dw - 1])
else:
    print(-1)

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())
S = []
for i in range(H):
    s = input()
    S.append(s)

que = deque()
que.append((Ch-1, Cw-1))
d = {}
d[(Ch-1, Cw-1)] = 0

def check(h, w, dis, c):
    if h < 0 or h >= H or w < 0 or w >= W:
        return
    if dis == 1:
        if S[h][w] == ".":
            if (h,w) in d:
                d[(h, w)] = min(d[(h,w)], c)
            else:
                d[(h, w)] = c
                que.append((h,w))
    else:
        if S[h][w] == ".":
            if (h,w) in d:
                d[(h, w)] = min(d[(h,w)], c+1)
            else:
                d[(h, w)] = c+1
                que.append((h,w))
    

while que:
    h, w = que.popleft()
    c = d[(h,w)]
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0:
                continue
            check(h+i, w+j, abs(i)+abs(j), c)

if (Dh-1, Dw-1) in d:
    print(d[(Dh-1, Dw-1)])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [list(map(str, list(input()))) for i in range(H)]
floor = [[0] * W for i in range(H)]
floor[Ch-1][Cw-1] = 1


def water(x, y):

    if floor[y][x] != 0:

        # 上
        if y + 1 < H:
            if S[y + 1][x] != "#" and floor[y + 1][x] == 0:
                floor[y + 1][x] = floor[y][x]
                water(x, y + 1)
        # 下
        if y - 1 >= 0:
            if S[y - 1][x] != "#" and floor[y - 1][x] == 0:
                floor[y - 1][x] = floor[y][x]
                water(x, y - 1)
        # 右
        if x + 1 < W:
            if S[y][x + 1] != "#" and floor[y][x + 1] == 0:
                floor[y][x + 1] = floor[y][x]
                water(x + 1, y)
        # 左
        if x - 1 >= 0:
            if S[y][x - 1] != "#" and floor[y][x - 1] == 0:
                floor[y][x - 1] = floor[y][x]
                water(x - 1, y)


def warp(x, y, i):
    for Y in range(max(y - 2, 0), min(y + 2, H)):
        for X in range(max(x - 2, 0), min(x + 2, W)):
            if S[Y][X] != "#" and floor[Y][X] == 0:
                floor[Y][X] = i + 1


# スタート地点に水を流す
water(Cw-1, Ch-1)
#print(floor)

# ワープ回数
for i in range(1, 1000):
    for y in range(H):
        for x in range(W):
            if floor[y][x] == i:
                warp(x, y, i)
    for y in range(H):
        for x in range(W):
            if S[y][x] != "#":
                water(x, y)

    if floor[Dh-1][Dw-1] != 0:
        print(floor[Dh-1][Dw-1]-1)
        #print(floor)
        sys.exit()

print("-1")

Submission status: Wrong Answer

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import deque
import sys
def main(H, W, C, D, S):
    INF = 10**6
    dist = [[INF] * W for _ in range(H)]
    dist[D[0]][D[1]] = 0
    q = deque([D])
    while q:
        i, j = q.popleft()
        d = dist[i][j]
        for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
            if 0 <= ni < H and 0 <= nj < W:
                if S[ni][nj] == '.':
                    if dist[ni][nj] > d:
                        dist[ni][nj] = d
                        q.append((ni, nj))
        for di in range(-2, 2 + 1, 1):
            for dj in range(-2, 2 + 1, 1):
                if abs(di) + abs(dj) <= 1: continue
                ni, nj = i + di, i + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                    if dist[ni][nj] > d + 1:
                        dist[ni][nj] = d + 1
                        q.append((ni, nj))

    ans = dist[C[0]][C[1]]
    print(ans if ans < INF else -1)


if __name__ == '__main__':
    input = sys.stdin.readline
    H, W = map(int, input().split())
    C = tuple(map(lambda x: int(x) - 1, input().split()))
    D = tuple(map(lambda x: int(x) - 1, input().split()))
    S = [list(input().rstrip()) for _ in range(H)]
    main(H, W, C, D, S)

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
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="#":
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i in range(max(0,x-3),min(h,x+3)):
            for j in range(max(0,y-3),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black":
                        D[X][Y]=min(D[X][Y],D[x][y]+1)
                        if color[X][Y]=="white":
                            queue.append([X,Y])
                        color[X][Y]="gray"
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black":
                    D[X][Y]=min(D[X][Y],D[x][y])
                    queue.append([X,Y])
                    color[X][Y]="gray"

        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Submission status: Wrong Answer

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R,C = NMI()
    sy, sx = NMI()
    gy, gx = NMI()
    board = [list(input()) for _ in range(R)]

    #座標を0始まりにする
    sx -= 1
    sy -= 1
    gx -= 1
    gy -= 1

    #移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    #すべての点をINFで初期化
    INF = 10**7
    distance = [[INF for _ in range(C)] for _ in range(R)]

    #地点を保存するqueを作成、スタート地点を入れる
    que = deque([])
    que.append((sy,sx))

    #スタート地点の距離は0
    distance[sy][sx] = 0
    
    #テレポート移動のベクトル
    tx = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]
    ty = [-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1, 0, 1, 2,-2,-1, 0, 1, 2]
    

    
    #queが空になるまでループ
    while len(que) != 0:

        #取り出してきた状態がゴールなら探索をやめる
        pop = que.popleft()
        if pop[0]==gy and pop[1]==gx:
            print(distance[gy][gx])
            sys.exit()

        #移動4方向をループ
        for i in range(len(dx)):
            #移動した後の点をny,nxとする
            ny = pop[0]+dy[i]
            nx = pop[1]+dx[i]
            

            #nyが0以上R未満   nxが0以上C未満     まだ訪れたことがない
            if 0<= ny < R and 0 <= nx < C and distance[ny][nx] == INF:
                
                if board[ny][nx]!='#':
                    #つまり壁ではなく移動可能でまだ行ったことがなければqueの左へ入れる
                    que.appendleft((ny,nx))
                    distance[ny][nx] = distance[pop[0]][pop[1]]

                    
                else:

                    #テレポートのループ
                    for j in range(len(tx)):
                        teley = pop[0]+ty[j]
                        telex = pop[1]+tx[j]
                        #nyが0以上R未満   nxが0以上C未満     まだ訪れたことがない
                        if 0<= teley < R and 0 <= telex < C and distance[teley][telex] == INF:
                            if board[teley][telex]!='#': #テレポート先が壁でないならqueの右へ入れる
                                que.append((teley,telex))
                                distance[teley][telex] = distance[pop[0]][pop[1]]+1 #テレポート使用回数を1回加算


    print(-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))

#print(h,w,s1,s2,f1,f2)

s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1

Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1

for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)

#print(V)
count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      #print(node)
      i,j = node[0], node[1]
      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))

      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))

      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))

      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))

    Q = new_Q

  #print(f1,f2)
  if V[f1][f2]==1:
    print(count)
    break
  else:
    #print(V)
    temp = sum(sum(kk) for kk in V) 
    count += 1
    #print(ALL,best,temp)
    part= []
    
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>0 and y>0 and x<h and y<w:
            if G[x][y] == '.':
              V[x][y] = 1
              part.append((x,y))
              
    ALL = part+ALL

    if temp==best:
      print(-1)
      break
    else:
      best = temp

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, 2):
        nh = Ph + dh
        if not 0 <= nh < H:
            continue
        for dw in range(-2, 3, 2):
            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:
from heapq import heapify, heappop, heappush

H, W = map(int, input().split())
Si, Sj = map(int, input().split())
Gi, Gj = map(int, input().split())
matrix = []
for i in range(H):
    matrix.append(list(input()))

que = [(0, Si-1, Sj-1, 0)]
heapify(que)
visited = set()

while que:
    priority, r, c, count = heappop(que)
    if not(0 <= r < H and 0 <= c < W):
        continue
    elif (r, c) in visited:
        continue
    elif matrix[r][c] == '#':
        continue
    elif (r, c) == (Gi-1, Gj-1):
        print(count)
        exit()
    visited.add((r, c))
    for td, lr in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        heappush(que, (priority+1, r+td, c+lr, count))
    for ud, lr in ((-2, 2), (-2, -2), (2, 2), (2, -2)):
        heappush(que, (priority+1+5, r+ud, c+lr, count+1))
print('-1')

Submission status: Wrong Answer

Solution code:
H, W = [int(n) for n in input().split()]
ch, cw = [int(n)-1 for n in input().split()]
dh, dw = [int(n)-1 for n in input().split()]
matrix = []
for i in range(H):
  row = []
  word = input()
  for w in word:
    row.append(w)
  matrix.append(row)
  
res = float('inf')
visited = set()
stack = [[(ch, cw), dh-ch, dw-cw, 0]]
while stack:
  now, id, jd, warp = stack.pop()
  i, j = now
  id = dh - i
  jd = dw - j
  idir = [-1,1][id>0]
  jdir = [-1,1][jd>0]
  if now == (dh, dw):
    res = min(res, warp)
  else:
    visited.add((i, j))
    for a, b in [(i+idir, j+jdir), (i+idir, j), (i, j+jdir)]:
      if 0<=a<=H-1 and 0<=b<=W-1 and (a, b) not in visited:
        if matrix[a][b] == '.':
          stack.append([(a, b), id-idir, jd-jdir, warp])
        else:
          for k in range(1, 3):
            for kk in range(1, 3):
              aa, bb = i+idir*k, j+jdir*kk
              if (aa, bb) not in visited and 0<=aa<=H-1 and 0<=bb<=W-1 and matrix[aa][bb] == '.':
                stack.append([(aa, bb), id-idir*k, jd-jdir*kk, warp+1])
print([-1,res][res != float('inf')])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
H, W = map(int, input().split())
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
gx, gy = map(int, input().split())
gx -= 1
gy -= 1
map = [list(input()) for i in range(H)]
cost_map = [[10**3]*W for i in range(H)]
d = deque()
cost_map[sx][sy] = 0
d.append([sx, sy])
while d:
    cx, cy = d.pop()
    ccost = cost_map[cx][cy]
    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and ccost < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost
                d.append([nx, ny])
    dxy = [[-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]]
    for dx, dy in dxy:
        nx = cx + dx
        ny = cy + dy
        if 0<=nx<H and 0<=ny<W:
            if map[nx][ny]=="." and ccost < cost_map[nx][ny]:
                cost_map[nx][ny] = ccost + 1
                d.appendleft([nx, ny])
if cost_map[gx][gy] == 1000:
    print(-1)
else:
    print(cost_map[gx][gy])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
a,b = map(int,input().split())
c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1

g = []
for _ in range(h):
    s = list(input())
    tmp = []
    for i in s:
        tmp.append(i)
    g.append(tmp)
if g[c][d] =='#':print(-1);exit()
from collections import deque
q = deque([])
dp = [[float('inf')]*w for _ in range(h)]

q.append((a,b,0))
dist = [(1,0),(0,1),(0,-1),(-1,0)]
seen = [[False]*w for _ in range(h)]

dp[a][b] = 0
seen[a][b] = True


while q:
    x,y,cnt = q.popleft()
    seen[x][y] = True
    for dx,dy in dist:
        X = x+dx
        Y = y + dy
        if 0<=X<h and 0<=Y<w and not seen[X][Y] and g[X][Y]=='.':
            if dp[X][Y]>cnt:
                dp[X][Y] = min(dp[X][Y],cnt)
                q.append((X,Y,cnt))
    for dx in range(-2,3,1):
        for dy in range(-2,3,1):
            X = x+dx
            Y = y + dy
            if 0<=X<h and 0<=Y<w and not seen[X][Y] and g[X][Y]=='.':
                if dp[X][Y]>cnt+1:
                    dp[X][Y] = min(dp[X][Y],cnt+1)
                    q.append((X,Y,cnt+1))
# print(dp)
print(dp[c][d] if dp[c][d]!=float('inf') else -1)

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])

Submission status: Wrong Answer

Solution code:
from queue import Queue

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
field = [["#"] * (w + 4)] + \
        [["#"] * (w + 4)] + \
        [list("##" + input() + "##") for i in range(h)] + \
        [["#"] * (w + 4)] + \
        [["#"] * (w + 4)]
sy += 1
sx += 1
gy += 1
gx += 1          
          
dxy1 = [(0,1), (0,-1), (1,0), (-1,0)]
dxy2 = [(1,1), (1,-1), (-1,1), (-1,-1), \
        (-2,-2), (-1,-2), (0,-2), (1,-2), (2,-2), \
        (-2,-1), (2,-1), (-2,0), (2,0), (-2,1), (2,1), \
        (-2,2), (-1,2), (0,2), (1,2), (2,2)]


goal = False
INF = 10**9
cnt = [[INF]*(w+4) for i in range(h+4)]

q = Queue()
q.put([sy, sx])
cnt[sy][sx] = 0

while goal == False and not q.empty():
    y, x = q.get()
    now = cnt[y][x]
    flg = False
    for dy, dx in dxy1:
        ny, nx = y + dy, x + dx
        if ny == gy and nx == gx:
            cnt[ny][nx] = now
            goal = True
            flg = True
            break
        if field[ny][nx] == '#':
            continue
        if cnt[ny][nx] > now:
            q.put([ny, nx])
            cnt[ny][nx] = now
            flg = True
    if not flg:
        for dy, dx in dxy2:
            ny, nx = y + dy, x + dx
            if ny == gy and nx == gx:
                cnt[ny][nx] = now + 1
                goal = True
                break
            if field[ny][nx] == '#':
                continue
            if cnt[ny][nx] > now:
                q.put([ny, nx])
                cnt[ny][nx] = now + 1
print(cnt[gy][gx]) if cnt[gy][gx] < INF else print(-1)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    h,w= map(int, input().split())
    cx,cy = map(int, input().split())
    dx,dy = map(int, input().split())
    s=[]
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
    for i in range(h):
        temp=input()
        temp="##"+temp+"##"
        s.append(list(temp))
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
#    for i in range(h+4):
#        print(s[i])

    visited = [[0 for i in range(w+4)] for _ in range(h+4)]
    warp = [[INFI for i in range(w+4)] for _ in range(h+4)]
    visited[cx+1][cy+1]=1
    warp[cx+1][cy+1]=0

    queue = deque([])
    warpdire=[[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2],
           [-2,-1],[-1,-1],[1,-1],[2,-1],
           [-2,0],[2,0],
           [-2,1],[-1,1],[1,1],[2,1],
           [-2,2],[-1,2],[0,2],[1,2],[2,2]]
    walkdire=[[0,-1],[-1,0],[1,0],[0,1]]

    nowx=cx+1
    nowy=cy+1
    for i in warpdire:
        if s[nowx+i[0]][nowy+i[1]]=="." and visited[nowx+i[0]][nowy+i[1]]==0:
            queue.append([nowx+i[0],nowy+i[1]])
            warp[nowx+i[0]][nowy+i[1]]=min(warp[nowx][nowy]+1,warp[nowx+i[0]][nowy+i[1]])
            visited[nowx + i[0]][nowy + i[1]] = 1
    for i in walkdire:
        if s[nowx+i[0]][nowy+i[1]]=="." and visited[nowx+i[0]][nowy+i[1]]<=1:
            queue.append([nowx+i[0],nowy+i[1]])
            warp[nowx+i[0]][nowy+i[1]]=min(warp[nowx][nowy],warp[nowx+i[0]][nowy+i[1]])
            visited[nowx + i[0]][nowy + i[1]] = 2
    while queue:
        if len(queue) <= 0:
            break
        now = queue.popleft()
        nowx=now[0]
        nowy=now[1]
        for i in walkdire:
            warp[nowx][nowy]=min(warp[nowx - i[0]][nowy - i[1]],warp[nowx][nowy])

        for i in warpdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] == 0:
                queue.append([nowx+i[0],nowy+i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 1
        for i in walkdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] <= 1:
                queue.append([nowx+i[0],nowy+i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 2

    if visited[dx+1][dy+1]==0:
        print("-1")
    else:
        print(warp[dx+1][dy+1])

#    for i in range(h+4):
#        print(visited[i])
 #   for i in range(h+4):
 #       print(warp[i])




if __name__ == "__main__":

    main()