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
import math
H,W=map(int, input().split())
Ch, Cw=map(int, input().split())
Dh, Dw=map(int, input().split())
maze=[]
for _ in range(H):
    RRR=(input().replace(".","0")).replace("#","1")
    maze.append(list(map(int, RRR)))
#print(maze)
dis=[[H**2*W**2 for _ in range(W+1)]for _ in range(H+1)]
start=(Ch,Cw,0)
goal=(Dh,Dw)
walk=[(1,0),(-1,0),(0,1),(0,-1)]
wap=[(2,0),(2,1),(2,2),(2,-1),(2,-2),(1,-2),(1,2),(0,2),(0,-2),(-1,2),(-1,-2),(-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2)]
cand=[start]
dis[start[0]][start[1]]=0
done=[]
flag=False
while len(cand)>0:
    #print(cand)
    place=cand.pop()
    hh,ww,cost=place
    w_cand=[]
    if hh==Dh and ww==Dw:
        flag=True
        break
    for each in walk:
        h1,w1=hh+each[0],ww+each[1]
        if h1>=1 and w1>=1 and h1<=H and w1<=W and dis[h1][w1]>cost:
            if maze[h1-1][w1-1]==0:
                dis[h1][w1]=cost
                cand.append((h1,w1,cost))
            else:
                for each in wap:
                    h1,w1=hh+each[0],ww+each[1]
                    if h1>=1 and w1>=1 and h1<=H and w1<=W and maze[h1-1][w1-1]==0 and dis[h1][w1]>cost+1:
                        dis[h1][w1]=cost+1
                        cand.append((h1,w1,cost+1))
if flag:
    print(dis[Dh][Dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict as dd,deque as dq
import sys
inf=100000
input=sys.stdin.readline
n,m=map(int,input().split())
cx,cy=map(int,input().split())
cx-=1
cy-=1
dx,dy=map(int,input().split())
dx-=1
dy-=1
ll=[]
for i in range(n):
    ll.append(input())
q=dq([cx*m+cy])
dis=[]
xx=[0,-1,0,1]
yy=[1,0,-1,0]
des=dx*m+dy
d=[]
for x in range(n):
    for y in range(m):
        d.append([])
        dis.append(inf)
        for i in range(4):
            X=x+xx[i]
            Y=y+yy[i]
            if(X<n and X>=0 and Y<m and Y>=0 and ll[X][Y]=='.'):
                d[x*m+y].append((X*m+Y,0))
        X=x-2
        Y=Y-2
        for i in range(5):
            for j in range(5):
                if(X+i>=0 and X+i<n and Y+j>=0 and Y+j<m and ll[X+i][Y+j]=='.'):
                    d[x*m+y].append(((X+i)*m+Y+j,1))
dis[q[0]]=0
lol=0
while q:
    curr=q.pop()
    #print(curr)
    if(curr==des):
        print(dis[curr])
        lol=1
        break
    for j in d[curr]:
        temp,val=j
        if(dis[temp]>dis[curr]+val):
            dis[temp]=dis[curr]+val
            if(val==0):
                q.append(temp)
            else:
                q.appendleft(temp)
if(lol==0):
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

input=sys.stdin.readline

H,W=list(map(int,input().split()))

sh,sw = list(map(int,input().split()))
gh,gw = list(map(int,input().split()))

sh-=1
sw-=1
gh-=1
gw-=1

c=[]
seen=[]
for i in range(H):
    c+=[input()]
    seen+=[[False]*W]

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

hop=0
ans=10000000

def dfs(c,h,w,hop):
    global seen,dx,dy,H,W,ans
    seen[h][w]=True
    print(h,w,hop)

    for i in range(4):
        nh=h+dy[i]
        nw=w+dx[i]

        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if c[nh][nw] == "#":
            for j in range(-2,3):
                for k in range(-2,3):
                    if 0<=h+j and h+j<H and 0<=w+k and w+k<W:
                        if c[h+j][w+k]=="." and seen[h+j][w+k]==False:
                            nh=h+j
                            nw=w+k
                            hop+=1
                            if nh==gh and nw==gw:
                                seen[nh][nw]=True
                                if ans>hop:
                                    ans=hop
                                return True
                            else:
                                dfs(c,nh,nw,hop)    
            continue
        if seen[nh][nw]:
            continue
        if nh==gh and nw==gw:
            seen[nh][nw]=True
            if ans>hop:
                ans=hop
            return True
        if dfs(c,nh,nw,hop):
            return True

dfs(c,sh,sw,hop)
if seen[gh][gw]:
    print(ans)
else:
    print("-1")

Submission status: Wrong Answer

Solution code:
from collections import deque
h,w=1000,1000
ch,cw=1,1
dh,dw=1000,1000

maze = [["."]*1000 for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.append([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
    flag=False
    for i in range(x-2,x+3):
      if flag:
        break
      for j in range(y-2,y+3):
        if 0<=i<w and 0<=j<h:
          if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
            ans[j][i]=(ans[y][x]+1)
            qu.append([i,j])
            break

bfs(ans)
print(ans[dh-1][dw-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

start = (Ch, Cw)

S = ['#'*(W+4)]
S.append('#'*(W+4))
for k in range(H):
  S.append('##' + input() + '##')
S.append('#'*(W+4))
S.append('#'*(W+4))

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10000
print(counter)
counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
for item in now:
  x = item[0]
  y = item[1]
  counter[x][y] = 0
  if counter[x+1][y] == 10000:
    now.append((x+1, y))
  if counter[x][y+1] == 10000:
    now.append((x, y+1))
  if counter[x-1][y] == 10000:
    now.append((x-1, y))
  if counter[x][y-1] == 10000:
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10000:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    if item == (Dh, Dw):
      print(ans)
      exit()
    x = item[0]
    y = item[1]
    if counter[x+2][y+2] > ans:
      counter[x+2][y+2] = ans
      nextlist.append((x+2, y+2))
    if counter[x+2][y+1] > ans:
      counter[x+2][y+1] = ans
      nextlist.append((x+2, y+1))
    if counter[x+2][y] > ans:
      counter[x+2][y] = ans
      nextlist.append((x+2, y))
    if counter[x+2][y-1] > ans:
      counter[x+2][y-1] = ans
      nextlist.append((x+2, y-1))
    if counter[x+2][y-2] > ans:
      counter[x+2][y-2] = ans
      nextlist.append((x+2, y-2))
    if counter[x+1][y+2] > ans:
      counter[x+1][y+2] = ans
      nextlist.append((x+1, y+2))
    if counter[x+1][y-2] > ans:
      counter[x+1][y-2] = ans
      nextlist.append((x+1, y-2))
    if counter[x][y+2] > ans:
      counter[x][y+2] = ans
      nextlist.append((x, y+2))
    if counter[x][y-2] > ans:
      counter[x][y-2] = ans
      nextlist.append((x, y-2))
    if counter[x-2][y+2] > ans:
      counter[x-2][y+2] = ans
      nextlist.append((x-2, y+2))
    if counter[x-2][y+1] > ans:
      counter[x-2][y+1] = ans
      nextlist.append((x-2, y+1))
    if counter[x-2][y] > ans:
      counter[x-2][y] = ans
      nextlist.append((x-2, y))
    if counter[x-2][y-1] > ans:
      counter[x-2][y-1] = ans
      nextlist.append((x-2, y-1))
    if counter[x-2][y-2] > ans:
      counter[x-2][y-2] = ans
      nextlist.append((x-2, y-2))
    if counter[x-1][y+2] > ans:
      counter[x-1][y+2] = ans
      nextlist.append((x-1, y+2))
    if counter[x-1][y-2] > ans:
      counter[x-1][y-2] = ans
      nextlist.append((x-1, y-2))
  now = nextlist  
  for item in now:
    if item == (Dh, Dw):
      print(ans)
      exit()
    x = item[0]
    y = item[1]
    if counter[x+1][y] > ans:
      counter[x+1][y] = ans
      now.append((x+1, y))
    if counter[x][y+1] > ans:
      counter[x][y+1] = ans
      now.append((x, y+1))
    if counter[x-1][y] > ans:
      counter[x-1][y] = ans
      now.append((x-1, y))
    if counter[x][y-1] > ans:
      counter[x][y-1] = ans
      now.append((x, y-1))
  if ans > 20000:
    print(-1)
    exit()
print(ans)

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, start, goal)

que = deque([(start, 0)])
seen = set()
seen.add(start)
while que:
    cur, time = que.popleft()
    if cur == goal:
        print(time)
        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:
from collections import deque

def f1(x,y,xa,ya):
    if reach[xa][ya] == -1 or reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] == -1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[-1 for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0
sw = 0

while q:
    if sw == 1:
        break
    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        if sw == 1:
            break
        for j in range(-2,3):
            f2(x,y,x+i,y+j)
            
            if x == dx and y == dy:
                sw = 1
                break

print(reach[dx][dy])

Submission status: Wrong Answer

Solution code:
H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
S = [list(input()) for i in range(H)]

# S = [["." if j % 2 == 0 else "#" for j in range(W)] for i in range(H)]
# S[0][0] = "."
# S[DH-1][DW-1] = "."

# for i in range(H):
#     print(S[i])

from collections import deque

q = deque([(CH-1, CW-1)])

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
warp = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2),
        (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
# warp = [(-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)]

M = []
for i in range(H):
    M.append([10**9] * W)
M[CH-1][CW-1] = 0

# for i in range(H):
#     visited.append([False] * W)
# visited[CH-1][CW-1] = True

visited = deque([(CH-1, CW-1)])
while q:
    h, w = q.popleft()
    for dh, dw in directions:
        if 0 <= h+dh < H and 0 <= w+dw < W and S[h+dh][w+dw] == ".":
            if M[h+dh][w+dw] > M[h][w]:
                M[h+dh][w+dw] = M[h][w]
                q.append((h+dh, w+dw))
                visited.append((h+dh, w+dw))

    if len(q) == 0:
        while visited:
            vh, vw = visited.popleft()
            for wh, ww in warp:
                if 0 <= vh+wh < H and 0 <= vw+ww < W and S[vh+wh][vw+ww] == ".":
                    if M[vh+wh][vw+ww] > M[vh][vw] + 1:
                        M[vh+wh][vw+ww] = M[vh][vw] + 1
                        q.append((vh+wh, vw+ww))

# for i in range(H):
#     print(M[i])

if M[DH-1][DW-1] == 10**9:
    print(-1)
else:
    print(M[DH-1][DW-1])

Submission status: Wrong Answer

Solution code:
h,w = map(int,input().split())
c,d = map(int,input().split())
e,f = map(int,input().split())
s = []
t = []
m = h*w
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = []
stc2 = []
while(1):
    if(c > 0):
        if(s[c-1][d] == '.' and t[c-1][d] > cnt):
            t[c-1][d] = cnt
            stc1.append([c-1,d])
    if(d > 0):
        if(s[c][d-1] == '.' and t[c][d-1] > cnt):
            t[c][d-1] = cnt
            stc1.append([c,d-1])
    if(c < h-1):
        if(s[c+1][d] == '.' and t[c+1][d] > cnt):
            t[c+1][d] = cnt
            stc1.append([c+1,d])
    if(d < w-1):
        if(s[c][d+1] == '.' and t[c][d+1] > cnt):
            t[c][d+1] = cnt
            stc1.append([c,d+1])
    for j in range(-2,3):
        for k in range(-2,3):
            if(abs(j)+abs(k) > 1):
                if(c+j >= 0 and c+j < h and d+k >= 0 and d+k < w):
                    if(s[c+j][d+k] == '.' and t[c+j][d+k] > cnt+1):
                        t[c+j][d+k] = min(t[c+j][d+k],cnt+1)
                        stc2.append([c+j,d+k])
    if(len(stc1) > 1):
        stc1.pop(-1)
        c = stc1[-1][0]
        d = stc1[-1][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            c = stc1[-1][0]
            d = stc1[-1][1]
            cnt += 1
        else:
            break
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-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())
s = []
for _ in range(h):
    s.append(input())
fl = [[100000 for _ in range(w)] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if(s[i][j:j+1] == "#"):
            fl[i][j] = -1

fl[ch-1][cw-1] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
ddx = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1,  2,  2, 2, 2, 2]
ddy = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]
que = [[ch-1, cw-1]]
while(len(que) != 0):
    now = que.pop(0)
    x, y = now[0], now[1]
    for i in range(4):
        if((-1 < x+dx[i] < h) and (-1 < y+dy[i] < w)):
            if(fl[x+dx[i]][y+dy[i]] >= 0):
                if(fl[x+dx[i]][y+dy[i]] > 1000):
                    que.append([x+dx[i], y+dy[i]])
                fl[x+dx[i]][y+dy[i]] = min(fl[x][y], fl[x+dx[i]][y+dy[i]])
                
    for i in range(len(ddx)):
        if((-1 < x+ddx[i] < h) and (-1 < y+ddy[i] < w)):
            if(fl[x+ddx[i]][y+ddy[i]] >= 0):
                if(fl[x+ddx[i]][y+ddy[i]] > 1000):
                    que.append([x+ddx[i], y+ddy[i]])
                fl[x+ddx[i]][y+ddy[i]] = min(fl[x][y]+1, fl[x+ddx[i]][y+ddy[i]])
if(fl[dh-1][dw-1] == 100000):
  print(-1)
else:
  print(fl[dh-1][dw-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())
tizu = [input() for _ in range(h)]

inf = 10 ** 9
check = [[inf for _ in range(w)] for _ in range(h)]
queue = deque()
ch -= 1
cw -= 1
dh -= 1
dw -= 1
walk = [[-1, 0], [1, 0], [0, 1], [0, -1]]
magic1 = [[1, 1], [1, -1], [2, 2], [2, 1], [2, 0], [2, -1], [2, -1]]
magic2 = [[-1, 1], [-1, -1], [-2, 2], [-2, 1], [-2, 0], [-2, -1], [-2, -1]]
magic3 = [[1, 1], [-1, 1], [2, 2], [1, 2], [0, 2], [-1, 2], [-2, 2]]
magic4 = [[1, -1], [-1, -1], [2, -2], [1, -2], [0, -2], [-1, -2], [-2, -2]]

queue.append([ch, cw])
queue.append(0)
while queue:
    pos = queue.popleft()
    dd = queue.popleft()
    if check[pos[0]][pos[1]] <= dd:
        continue
    check[pos[0]][pos[1]] = dd
    flg = [False, False, False, False]
    for dy, dx in walk:
        n_h = pos[0] + dy
        n_w = pos[1] + dx
        if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
            continue
        if check[n_h][n_w] <= dd:
            continue
        if tizu[n_h][n_w] == "#":
            if dy == 1:
                flg[0] = True
            elif dy == -1:
                flg[1] = True
            elif dx == 1:
                flg[2] = True
            else:
                flg[3] = True
            continue
        queue.append([n_h, n_w])
        queue.append(dd)
        
    if flg[0]:
        for dy, dx in magic1:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
        
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[1]:
        for dy, dx in magic2:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[2]:
        for dy, dx in magic3:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)
    if flg[3]:
        for dy, dx in magic4:
            n_h = pos[0] + dy
            n_w = pos[1] + dx
            if n_h < 0 or n_w < 0 or n_h >= h or n_w >= w:
                continue
            if check[n_h][n_w] <= dd + 1:
                continue
            if tizu[n_h][n_w] == "#":
                continue
            check[n_h][n_w] = dd + 1
            queue.append([n_h, n_w])
            queue.append(dd + 1)

if check[dh][dw] == inf:
    print(-1)
else:
    print(check[dh][dw])

Submission status: Wrong Answer

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

import heapq

#点の数が10**5のオーダー以下で使える
#計算量はO(MlogN) M : 辺の数、N　：　頂点数
#頂点sからの各頂点への最短距離を出力
def dijkstra(s, n, edge): #s:始点、n:頂点の数、edge:重み付き辺の配列（edge[i]:iから出るtuple[重み、行き先]の配列)
    INF = 10**20
    d = [INF]*n # d[i]: sと点iとの距離
    used = [True]*n #Trueは未確定
    d[s] = 0 #初期条件
    used[s] = False # 初期条件
    edge_list = []
    for a, b in edge[s]:
        heapq.heappush(edge_list, a*(10**8)+b) #heapqの中に重みと辺の抱き合わせた情報を入れる
    while len(edge_list):
        min_edge = heapq.heappop(edge_list) #まだ使われていない頂点の中から最小の重みのものを取りだす
        if not used[min_edge%(10**8)]: # 確定していたらcontinue、確定していない時のみ以下の処理を行う
            continue
        v = min_edge%(10**8) #行き先の情報を復元
        d[v] = min_edge // (10**8) #重みの情報を復元し、sとvの最短距離d[v]を更新する
        used[v] = False
        for e in edge[v]:
            if used[e[1]]: #その行き先がまだ未確定の場合
                heapq.heappush(edge_list, (e[0]+d[v])*(10**8) + e[1])
        
    return d
#d[i] : 始点から i までの距離
h, w = map(int, input().split())
edge = [[] for _ in range((h+4)*(w+4))] # edge:重み付き辺の配列（edge[i]:iから出るtuple(重み、行き先)の配列)
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
start = (ch, cw)
end = (dh, dw)
g = []
g.append([1]*(w+4))
g.append([1]*(w+4))
for i in range(h):
    s = list(input())
    tmp = [1,1]
    for j in s:
        if j == '.':
            tmp.append(0)
        else:
            tmp.append(1)
    tmp.append(1)
    tmp.append(1)
    g.append(tmp)
g.append([1]*(w+4))
g.append([1]*(w+4))
#print(g)
def pp(height, width):
    return height*(w+4)+width
d = []
for i in range(-2, 3):
    for j in range(-2,3):
        if i < 0 and j < 0:
          continue
        d.append((i, j))
d2 = [(1, 0), (0,1)]

#print(d2)
for i in range(2, h+2):
    for j in range(2, w+2):
        for q in d:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((1, pp(i+x, j+y)))
        for q in d2:
            x, y = q
            if g[i][j] == 0 and g[i+x][j+y] == 0:
                edge[pp(i, j)].append((0, pp(i+x, j+y)))
#print(edge)
                
d = dijkstra(pp(ch+1, cw+1), (h+4)*(w+4), edge)

if d[pp(dh+1, dw+1)] >= 10**20:
    print(-1)
    #print(d[pp(dh+1, dw+1)])
    #print(pp(ch+1, cw+1))
    #print(pp(dh+1, dw+1))
else:
    print(d[pp(dh+1, dw+1)])

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def dfs1(y, x, c):
    dy = [1, 0, -1, 0, 1, -1, 1, -1]
    dx = [0, 1, 0, -1, 1, 1, -1, -1]
    for k in range(8):
        ny = y + dy[k]
        nx = x + dx[k]
        if ny < 0 or H <= ny or nx < 0 or W <= nx:
            continue
        if field[ny][nx] == '.':
            field[ny][nx] = c
    return


def dfs2(y, x, c):
    dy = [2, 2, 2, 2, 2, 1, 1, 0, 0, -1, -1, -2, -2, -2, -2, -2]
    dx = [-2, -1, 0, 1, 2, -2, 2, -2, 2, -2, 2, -2, -1, 0, 1, 2]
    for k in range(16):
        ny = y + dy[k]
        nx = x + dx[k]
        if ny < 0 or H <= ny or nx < 0 or W <= nx:
            continue
        if field[ny][nx] == '.':
            field[ny][nx] = c+1
    return


H, W = map(int, readline().split())
cy, cx = map(int, readline().split())
ey, ex = map(int, readline().split())
cy -= 1
cx -= 1
ey -= 1
ex -= 1

field = [list(readline().decode().rstrip()) for _ in range(H)]


field[cy][cx] = 0
for y in range(cy, H):
    for x in range(cx, W):
        if field[y][x] != '#' and field[y][x] != '.':
            dfs1(y, x, field[y][x])
            dfs2(y, x, field[y][x])

for y in range(cy):
    for x in range(cx):
        if field[y][x] != '#' and field[y][x] != '.':
            dfs1(y, x, field[y][x])
            dfs2(y, x, field[y][x])

print('-1' if field[ey][ex] == '.' else field[ey][ex])

Submission status: Wrong Answer

Solution code:
h, w = map(int, input().split())
c = list(map(int, input().split()))
d = list(map(int, input().split()))
s = ['#'*(w+2)]
for _ in range(h):
  s.append('#' + input() + '#')
s.append('#'*(w+2))

from queue import Queue
q1 = Queue()
q2 = Queue()
q1.put(c)
now = c
count = [[-1 for j in range(w+2)] for i in range(h+2)]
num = 0
while not q1.empty() or not q2.empty():
  while not q1.empty():
    now = q1.get()
    for dxy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
          else:
            count[tar[0]][tar[1]] = -2
            q2.put(tar)
    for dxy in [[1, 1], [-1, -1], [-1, 1], [1, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '#':
            count[tar[0]][tar[1]] = -2
            q2.put(tar)
    if d == now:
      break
            
  num += 1
            
  while not q2.empty():
    now = q2.get()
    for dxy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
    for dxy in [[1, 1], [-1, -1], [-1, 1], [1, -1]]:
      tar = [now[0]+dxy[0], now[1]+dxy[1]]
      if tar[0] > 0 and tar[0] <= h and tar[1] > 0 and tar[1] <= w:
        if count[tar[0]][tar[1]] == -1:
          if s[tar[0]][tar[1]] == '.':
            count[tar[0]][tar[1]] = num
            q1.put(tar)
            
print(count[d[0]][d[1]])

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 not flag and 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:
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()
    flag = 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]
            flag = True
        if next_y == Dh and next_x == Dw:
            is_goal = True

    if not flag:
        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:
    print(S[Dh][Dw])
else:
    print(-1)