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
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

h,w = mp()
ch, cw = mp()
dh,dw = mp()
ch += 1
cw += 1
dh += 1
dw += 1
grid = []
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))
ans_grid = []
for i in range(h):
    u = ["#", "#"]
    a = list(input())
    for j in range(w):
        u.append(a[j])
    u.append("#")
    u.append("#")
    grid.append(u)
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))

for i in range(h+4):
    ans_grid.append([int(1e8)]*(w+4))
# print(grid)
# print(ans_grid)

from collections import deque
def bfs(x,y):
    q = deque([])
    used = set()
    q.append((x,y))
    used.add((x,y))
    ans_grid[x][y] = 0
    while q:
        here = q.popleft()
        move = [(here[0]-1, here[1]),
                (here[0], here[1]-1),
                (here[0], here[1]+1),
                (here[0]+1, here[1])]
        warp = [(here[0]-2, here[1]-2), (here[0]-2, here[1]-1), (here[0]-2, here[1]), (here[0]-2, here[1]+1), (here[0]-2, here[1]+2),
                (here[0]-1, here[1]-2), (here[0]-1, here[1]-1), (here[0]-1, here[1]), (here[0]-1, here[1]+1), (here[0]-1, here[1]+2),
                (here[0], here[1]-2), (here[0], here[1]-1), (here[0], here[1]+1), (here[0], here[1]+2),
                (here[0]+1, here[1]-2), (here[0]+1, here[1]-1), (here[0]+1, here[1]), (here[0]+1, here[1]+1), (here[0]+1, here[1]+2),
                (here[0]+2, here[1]-2), (here[0]+2, here[1]-1), (here[0]+2, here[1]), (here[0]+2, here[1]+1), (here[0]+2, here[1]+2),]
        for i in range(len(warp)):
            u = warp[i][0]
            v = warp[i][1]
            if grid[u][v] == "." and ans_grid[u][v] > ans_grid[here[0]][here[1]]+1:
                ans_grid[u][v] = min(ans_grid[u][v], ans_grid[here[0]][here[1]]+1)
                q.append((u,v))
        for i in range(len(move)):
            u = move[i][0]
            v = move[i][1]
            if move[i] not in used and grid[u][v] == ".":
                ans_grid[u][v] = min(ans_grid[here[0]][here[1]], ans_grid[u][v])
                q.append((u,v))
                used.add((u,v))


bfs(ch,cw)
ans = ans_grid[dh][dw]
if ans == int(1e8):
    print(-1)
else:
    print(ans)

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 = {}
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==current:
    print(0)
elif goal in dis:
    print(dis[goal])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
def LI(): return list(map(int, input().split()))
def I(): return map(int, input().split())
from collections import deque
mod = 10**9 + 7

def main():
  h, w = I()
  ch, cw = I()
  dh, dw = I()
  s = ['$'*(w+4)]*(h+4)
  for i in range(h):
    s[i+2] = '$$' + input() + '$$'

  dist = [[-1]*(w+4) for _ in range(h+4)]
  dist[ch + 1][cw + 1] = 0
  q = deque()
  q.append((ch+1, cw+1))
  while q:
    x, y = q.popleft() # 探索地点を取り出す

    vx = [-1,0,1,0]
    vy = [0,-1,0,1]
    flag = [False, False, False, False]
    for i in range(4):
      nx = x + vx[i]
      ny = y + vy[i]
      if s[nx][ny] == '$': 
        flag[i] = True
        continue # 壁なら通れないね！
      if s[nx][ny] == '#':
        flag[i] = True
        continue
      if dist[nx][ny] != -1: 
        flag[i] = True
        continue # もう最短距離がわかってるなら飛ばす
      dist[nx][ny] = dist[x][y]
      q.append((nx, ny)) # 新しい地点の周りも探索したいからキューに入れておく
    if not False in flag: # もし4つのflagがTrueの時5×5以内に飛べるか探す
      vvx = [-2,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2]
      vvy = [0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2,1,1,1,1,2,2,2,2,2]
      for i in range(20):
        nnx = x + vvx[i]
        nny = y + vvy[i]
        if s[nnx][nny] == '$': 
          continue # 壁なら通れないね！
        if s[nnx][nny] == '#':
          continue
        if dist[nnx][nny] != -1: 
          continue # もう最短距離がわかってるなら飛ばす
        dist[nnx][nny] = dist[x][y] + 1
        q.append((nnx, nny))
        
  print(dist[dh+1][dw+1])

if __name__ == '__main__':
  main()

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 (h,w) not in now:
                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 sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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
rows,cols = h,w

OK = "."
NG = "#"

from collections import defaultdict

ns = defaultdict(set)
ss = [None] * rows
for i in range(rows):
    s = input()
    ss[i] = s
n = rows * cols
start = (ch,cw)
goal = (dh,dw)
seen = [None]*n
seen[start[0]*w+start[1]] = 0
from heapq import heappop as hpp, heappush as hp
q = [(start, 0, start)] # ワープ回数, 最後の道の位置
dx = [0,1,0,-1]
dy = [1,0,-1,0]
while q:
    (ux,uy),pnum,pprv = hpp(q)
#     print(ux,uy, num, prv)
    for xx,yy in zip(dx,dy):
        x = ux+xx
        y = uy+yy
        num = pnum
        prv = pprv
        if x<0 or y<0 or x>=h or y>=w:
            continue
        if abs(x-prv[0])>=3 or abs(y-prv[1])>=3:
            continue
            
        if ss[x][y]==".":
            prv = (x,y)
        else:
            if abs(x-prv[0]) + abs(y-prv[1]) == 1:
                prv = (ux,uy)
                num += 1

        if seen[x*w+y] is None or seen[x*w+y]>num:
            seen[x*w+y] = num
            hp(q, ((x,y), num, prv))
val = seen[goal[0]*w+goal[1]]
if val is None:
    print(-1)
else:
    print(val)

Submission status: Wrong Answer

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

def inValidRegion(i,j,H,W):
    return i >= 0 and i < H and j >= 0 and j < W


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    # Failed to predict input format
    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.append(list(input()))
    # print(S)
    R = []
    for i in range(H):
        R.append([])
        for j in range(W):
            R[i].append(-1 if S[i][j]=="#" else 0)
    currentId = 1
    for ii in range(H):
        for ij in range(W):
            if R[ii][ij] != 0:
                continue
            init = (ii,ij)
            c = set()
            c.add(init)
            while len(c) > 0:
                i,j = c.pop()
                R[i][j] = currentId
                if inValidRegion(i+1,j,H,W) and R[i+1][j] == 0:
                    c.add((i+1,j))
                if inValidRegion(i,j+1,H,W) and  R[i][j+1] == 0:
                    c.add((i,j+1))
                if inValidRegion(i-1,j,H,W) and R[i-1][j] == 0:
                    c.add((i-1,j))
                if inValidRegion(i,j-1,H,W) and  R[i][j-1] == 0:
                    c.add((i,j-1))
            currentId+=1
    # print(R)
    Connections = [set() for i in range(currentId)]
    Ca = R[Ch-1][Cw-1]
    Da = R[Dh-1][Dw-1]
    # print(Ca,Ch,Cw)
    # print(Da,Dh,Dw)
    if Ca == Da:
        print(0)
    else:
        for i in range(H):
            for j in range(W):
                a = R[i][j]
                for k in range(-2,3):
                    for l in range(-2,3):
                        if inValidRegion(i+k,j+l,H,W):
                            a2 = R[i+k][j+l]
                            if a2 != a and a2 > 0:
                                Connections[a].add(R[i+k][j+l])
        # print(Connections)
        reached = set([Ca])
        nextSet = set([Ca])
        warp = 0
        while len(nextSet) > 0:
            currentSet = nextSet
            nextSet = set()
            warp += 1
            while len(currentSet) > 0:
                current = currentSet.pop()
                for c in Connections[current]:
                    if c not in reached:
                        reached.add(c)
                        nextSet.add(c)
                    if c == Da:
                        print(warp)
                        return
        print(-1)

    pass

if __name__ == '__main__':
    main()

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を作成
    teleque = deque([])
    
    #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:
                    teleque.append((pop[0],pop[1]))
                    #つまり壁だった場合、壁をテレポートでよけて進めるかどうか。進めれて、まだ行ったことがなければqueの右へ入れる
                    
            while len(teleque) != 0:
                telepop = teleque.popleft()
                    #テレポートのループ
                for j in range(len(tx)):
                    teley = telepop[0]+ty[j]
                    telex = telepop[1]+tx[j]
                    #print(teley,telex)
                    #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
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
import copy
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)


class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
A = [input() for i in range(h)]

tree = Uf(h*w)
for i in range(h):
    for j in range(w):
        if A[i][j] == "#":
            continue
        if i > 0 and A[i-1][j] == ".":
            tree.unite(w*i+j, w*(i-1)+j)
        if i < h-1 and A[i+1][j] == ".":
            tree.unite(w*i+j, w*(i+1)+j)
        if j > 0 and A[i][j-1] == ".":
            tree.unite(w*i+j, w*i+(j-1))
        if j < w-1 and A[i][j+1] == ".":
            tree.unite(w*i+j, w*i+(j+1))

# print(tree.p)

par_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            par_list.add(tree.p[w*i+j])

# print(par_list)

node = dict()
for i, e in enumerate(par_list):
    node[e] = i

# print(node)

edge_list = set()
for i in range(h):
    for j in range(w):
        if A[i][j] == ".":
            for a in range(max(0, i - 2), min(h, i+3)):
                for b in range(max(0, j - 2), min(w, j + 3)):
                    if A[a][b] == "." and tree.p[w*i+j] != tree.p[w*a+b]:
                        edge_list.add((node[tree.p[w*i+j]], node[tree.p[w*a+b]]))
                        edge_list.add((node[tree.p[w*a + b]], node[tree.p[w*i + j]]))

start = node[tree.p[w*(ch-1) + cw-1]]
goal = node[tree.p[w*(dh-1) + dw-1]]

g = [[] for i in range(len(node))]
for e in edge_list:
    g[e[0]].append(e[1])

# print(g)

que = deque([(start, 0)])
seen = set()
seen.add(start)
while que:
    cur, time = que.popleft()
    if cur == goal:
        print(cur)
        exit()
    for nxt in g[cur]:
        if nxt not in seen:
            seen.add(nxt)
            que.append((nxt, time+1))

print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1
cw-=1
stack=[(ch,cw)]
dh,dw=map(int,input().split())
dh-=1
dw-=1
b=[w*[-1]for _ in range(h)]
for i in range(h):
  for j,t in enumerate(input()):
    if t=="#":b[i][j]=10**10
b[ch][cw]=0
dxy=((-1,0),(1,0),(0,-1),(0,1))
for ans in range(10):
  for x,y in stack:
    b[x][y]=1
    if x==dh and y==dw:
      print(ans)
      exit()
    for dx,dy in dxy:
      if 0<=x+dx<h and 0<=y+dy<w:
        if b[x+dx][y+dy]==10**10:continue
        if b[x+dx][y+dy]==-1:
          stack.append((x+dx,y+dy))
          b[x+dx][y+dy]=1
  stackk=[]
  for x,y in stack:
    for xx in range(max(0,x-2),min(h,x+3)):
      for yy in range(max(0,y-2),min(w,y+3)):
        if b[xx][yy]==-1:stackk.append((xx,yy))
  stack=stackk
print(-1)

Submission status: Wrong Answer

Solution code:
import heapq

def resolve():
    H,W = map(int,input().split())
    Sy,Sx = [int(i)-1 for i in input().split()]
    Gy,Gx = [int(i)-1 for i in input().split()]

    MP = [input() for i in range(H)]
    q =[]
    score=[[100000000]*W  for i in range(H)]
    score[Sy][Sx] = 0
    heapq.heappush(q,(Sx,Sy,0))
    visited = [[False for j in range(W)] for i in range(H)]

    while q:
        x,y,cs = heapq.heappop(q) 

        if visited[y][x]:
            continue
        visited[y][x]=True


        if y!=0 and MP[y-1][x]=='.' and score[y][x]<score[y-1][x]:
            score[y-1][x]=score[y][x]
            heapq.heappush(q,(x,y-1,cs))
        if y!=H-1 and MP[y+1][x]=='.' and score[y][x]<score[y+1][x]:
            score[y+1][x]=score[y][x]
            heapq.heappush(q,(x,y+1,cs))
  
        if x!=0 and MP[y][x-1]=='.' and score[y][x]<score[y][x-1]:
            score[y][x-1]=score[y][x]
            heapq.heappush(q,(x-1,y,cs))
        if x!=W-1 and MP[y][x+1]=='.' and score[y][x]<score[y][x+1]:
            score[y][x+1]=score[y][x]
            heapq.heappush(q,(x+1,y,cs))

        for i in range(max(0,y-2),min(H,y+3)):
            for j in range(max(0,x-2),min(W,x+3)):

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(j,i,score[y][x]+1))

    if score[Gy][Gx]==100000000:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()

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 field[ny][nx] == '.' and 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 field[ny][nx] == '.' and 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:
from heapq import heapify, heappop, heappush, heappushpop
from collections import deque
import sys
input = sys.stdin.readline

INF = 1e5

class PriorityQueue:
    """
    優先度付きキューの
    """
    def __init__(self, heap):
        self.heap = heap
        heapify(self.heap)
    
    def push(self, item):
        heappush(self.heap, item)
    
    def pop(self):
        return heappop(self.heap)
    
    def pushpop(self, item):
        return heappushpop(self.heap, item)
    
    def __call__(self):
        return self.heap
    
    def __len__(self):
        return len(self.heap)
    
    

def dijkstra(adj, sx, sy):
    Color = [[0]*(W+2) for _ in range(H+2)] # 0: 未訪問 1: Seen 2: Visited
    D = [[INF]*(W+2) for _ in range(H+2)] #始点からの距離(重み)
    # P = [None]*N #親

    D[sx][sy] = 0
    # P[s] = None
    PQ = PriorityQueue([(0, sx, sy)]) #(Cost, Node)を格納し、PQにする。

    while PQ: # PQに候補がある限り

        min_cost, ux, uy = PQ.pop() # 最小コストなノードu

        Color[ux][uy] = 2 # uをVisitedに。

        if D[ux][uy] < min_cost:
            # 更新の必要なし.
            continue

        for adj_x, adj_y, adj_w in adj[(ux, uy)]:
            if Color[adj_x][adj_y] != 2: #訪問済みでないなら
                if D[ux][uy] + adj_w < D[adj_x][adj_y]: #最小コストを更新できるなら、
                    D[adj_x][adj_y] = D[ux][uy] + adj_w
                    # P[adj_idx] = u
                    # PQに(隣接要素のコスト, 隣接要素の番号)を容れる
                    PQ.push((D[adj_x][adj_y], adj_x, adj_y))
                    Color[adj_x][adj_y] = 1
    
    return D


H,W=map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

S = [["#"]*(W+2) for _ in range(H+2)]
for i in range(1,1+H):
    tmp=list(input())
    for j in range(1,1+W):
        S[i][j]=tmp[j-1]

# idxs = []
# for row in range(1, H+1):
#     for col in range(1, W+1):
#         if S[row][col] == ".":
#             idxs.append((row, col))

dxdy = [(1,0), (-1,0), (0,1), (0,-1)]
graph = {}
idxs = []
for x in range(1, H+1):
    for y in range(1, W+1):
        if S[x][y] == "#":
            continue
        idxs.append((x, y))
        graph[(x, y)] = deque()
        for dx, dy in dxdy:
            if S[x+dx][y+dy] == ".":
                graph[(x, y)].append((x+dx, y+dy, 0))

for idx in idxs:
    x = idx[0]
    y = idx[1]
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if x+dx < 1 or x+dx>H or y+dy<1 or y+dy>W:
                continue
            if S[x+dx][y+dy] == ".":
                graph[idx].append((x+dx, y+dy, 1))

D = dijkstra(graph, ch, cw)
if D[dh][dw] == INF:
    print(-1)
else:
    print(D[dh][dw])

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+1, j+1), (i+1, j), (i, j+1), (i-1, j-1), (i-1, j), (i, j-1)]:
      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(-2, 3):
            for kk in range(-2, 3):
              aa, bb = i+k, j+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:
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
    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()