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

mvs = [(-1,0),(1,0),(0,1),(0,-1)]
fs = []

for i in range(H):
    r = list(input())
    fs.append(r)

INF = 1<<50
dps = [[INF]*W for i in range(H)]
dps[ch-1][cw-1] = 0
from collections import deque
q = deque([])
q.append((ch-1,cw-1))
while len(q)>0:
    h,w = q.popleft()
    cnt = dps[h][w]
    # 先に魔法を使っておく
    for dh in range(-2,3):
        for dw in range(-2,3):
            hn = h + dh
            wn = w + dw
            if (dh,dw) in mvs:
                if 0<=hn<H and 0<=wn<W:
                    if dps[hn][wn] <= cnt:continue
                    if fs[hn][wn] == ".":
                        q.append((hn, wn))
                        dps[hn][wn] = min(dps[h][w], cnt)
            else:
                if 0<=hn<H and 0<wn<W:
                    if fs[hn][wn] == ".":
                        if dps[hn][wn] <= cnt:continue
                        q.append((hn,wn))
                        dps[hn][wn] = min(dps[hn][wn], cnt + 1)


ans = dps[dh_-1][dw_-1]
print(ans if ans != INF else -1)

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])
                    if color[X][Y]=="white":
                        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:
from collections import deque
h,w = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
d1 = [-2,-1,0,1,2]
reach = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if y < 0 or x < 0 or y >= w or x >= h:
        continue
    if S[x][y] == '#':
        continue
    else:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
            else:
                for i in d1:
                    for j in d1:
                        s,t = x+i,y+j
                        if 0<=s<h and 0<=t<w:
                            if S[s][t] == '.' and not reach[s][t]:
                                que2.append([s,t])
                                reach[s][t] = True
        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
            else:
                for i in d1:
                    for j in d1:
                        s,t = x+i,y+j
                        if 0<=s<h and 0<=t<w:
                            if S[s][t] == '.' and not reach[s][t]:
                                que2.append([s,t])
                                reach[s][t] = True
    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)

Submission status: Wrong Answer

Solution code:
h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1

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

from collections import deque
stack = deque([(sy,sx)])
maze[sy][sx]=0

checked=[[0]*w for _ in range(h)]


while len(stack)>0:
    (y,x)=stack.pop()
    if checked[y][x]==0:
        checked[y][x]=1
        if (y,x)==(gy,gx):
            print(maze[y][x])
            exit()
        for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#" and maze[ny][nx]>maze[y][x]):
                    stack.appendleft((ny,nx))
                    maze[ny][nx]=maze[y][x]
                #ワープ
                elif maze[ny][nx]=="#":
                    ny+=my
                    nx+=mx
                    if 0<=ny<h and 0<=nx<w:
                        if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                            stack.append((ny,nx))
                            maze[ny][nx]=maze[y][x]+1
        #斜めのワープを入れる
        for (my,mx) in ((1,1),(-1,-1),(-1,1),(1,-1)):
            for k in (1,2):
                ny=my*k+y
                nx=mx*k+x
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                        stack.append((ny,nx))
                        maze[ny][nx]=maze[y][x]+1
        for (my,mx) in ((1,2),(-1,-2),(-1,2),(1,-2),(2,1),(-2,-1),(-2,1),(2,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                    stack.append((ny,nx))
                    maze[ny][nx]=maze[y][x]+1

#for item in maze:
    #print(item)
print(-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=[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))
d[ch][cw]=0
tmp_ans=-1

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))
            tmp_ans=max(tmp_ans, d[new_y][new_x])

    if not queue:
        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))
                tmp_ans=max(tmp_ans, d[new_y][new_x])

print(d[dh][dw])

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w = m()

c = l()

d = l()

s = [list(input()[:-1]) for i in range(h)]

data = [[-1 for j in range(w)]for i in range(h)]

po = [cl.deque([]) for i in range(max(h,w)+1)]

now = 0
po[0] = cl.deque([[c[0]-1,c[1]-1]])
d[0] -= 1
d[1] -= 1
dire = [[1,0],[0,1],[-1,0],[0,-1]]

#data[c[0]-1][c[1]-1] = 0
while True:
    if now >= max(h,w)+1:
        break
    if len(po[now]) == 0:
        now += 1
        continue
    else:
        popo = po[now].popleft()
        if data[popo[0]][popo[1]] != -1 and data[popo[0]][popo[1]] < now:
            continue
        else:
            data[popo[0]][popo[1]] = now
            for kkk in dire:
                if (popo[0] + kkk[0] >= 0 and popo[0] + kkk[0] < h) and (popo[1] + kkk[1] >= 0 and popo[1] + kkk[1] < w):
                    if s[popo[0] + kkk[0]][popo[1] + kkk[1]] == "#":
                        continue
                    if data[popo[0] + kkk[0]][popo[1] + kkk[1]] == -1 or data[popo[0] + kkk[0]][popo[1] + kkk[1]] > now:
                        data[popo[0] + kkk[0]][popo[1] + kkk[1]] = now
                        po[now].append([popo[0]+ kkk[0],popo[1] + kkk[1]])

            for i in range(5):
                i -= 2
                if i + popo[0] < 0 or i + popo[0] >= h:
                    continue
                for j in range(5):
                    j -= 2
                    if j + popo[1] < 0 or j + popo[1] >= w:
                        continue
                    elif s[popo[0]+ i][popo[1] + j] == ".":
                        if data[popo[0]+ i][popo[1] + j] > now+1 or data[popo[0]+ i][popo[1] + j] == -1:
                            if now + 1 <= max(h,w):
                                data[popo[0]+ i][popo[1] + j] = now+1
                                po[now+1].append([popo[0]+ i,popo[1] + j])


print(data[d[0]][d[1]])

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W = LI()
    ch, cw = _LI()
    dh, dw = _LI()
    m = [[0] * W for _ in range(H)]
    for i in range(H):
        s = SI()
        for j in range(W):
            if s[j] == "#":
                m[i][j] = -1

    z = [(ch,cw,1)]
    while z:
        x,y,c = z.pop()
        if m[x][y]: continue
        q = collections.deque()
        q.append((x,y))
        m[x][y] = c
        r = [(x,y)]
        while q:
            x,y = q.popleft()
            if x == dh and y == dw:
                print(c-1)
                return
            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):
                nx = x + dx
                ny = y + dy
                if not(0<= nx < H and 0<= ny < W): continue
                if m[nx][ny]: continue
                m[nx][ny] = c
                q.append((nx,ny))
                r.append((nx,ny))
        for x,y in r:
            for dx in range(-2,3):
                nx = x + dx
                if not(0<= nx < H): continue
                for dy in range(-2,3):
                    ny = y + dy
                    if not(0<= ny < W): continue
                    if m[nx][ny]: continue
                    z.append((nx,ny,c+1))
    print(-1)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import heapq as hq
H,W = map(int,input().split())
Sh,Sw = map(int,input().split())
Sh -= 1
Sw -= 1
Gh,Gw = map(int,input().split())
Gh -= 1
Gw -= 1
S = [list(input()) for _ in range(H)]
D = [[-1 for _ in range(W)] for _ in range(H)]
D[Sh][Sw] = -1

search = [(0, Sh, Sw)]

walk = [(1,0),(-1,0),(0,1),(1,0)]
warp = [(x,y) for x in range(-2,3) for y in range(-2,3) if abs(x) + abs(y) > 1]

def validPosition(h,w):
	return 0 <= h and h < H and 0 <= w and w < W

hq.heapify(search)
while len(search) > 0 and D[Gh][Gw] == -1:
	(d, h, w) = hq.heappop(search)
	if D[h][w] >= 0:
		continue
	D[h][w] = d
	for (x,y) in walk:
		hh,ww = h+x, w+y
		if validPosition(hh, ww) and D[hh][ww] == -1 and S[hh][ww] == ".":
			hq.heappush(search, (d, hh, ww))
	for (x,y) in warp:
		hh,ww = h+x, w+y
		if validPosition(hh, ww) and D[hh][ww] == -1 and S[hh][ww] == ".":
			hq.heappush(search, (d+1, hh, ww))

print(D[Gh][Gw])

Submission status: Wrong Answer

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

#n = int(input())
#l = list(map(int, input().split()))

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''
h,w=map(int, input().split())
start=list(map(int, input().split()))
goal=list(map(int, input().split()))
m = [list(input().rstrip("\n")) for i in range(h)]
start[0]-=1
start[1]-=1
goal[0]-=1
goal[1]-=1
#print(m,start,goal,h,w)

def bfs(h, w, m, start, goal):
    import queue
    d = [[0 for i in range(w)]for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    flg = False

    a = queue.Queue()
    a.put(start)
    canwarp=True
    cnt=0
    while canwarp:
        #print(goal)
        mimi=100000
        k=0
        while not a.empty():
            hh, ww = map(int, a.get())
            #print(hh,ww)
            d[hh][ww]=1
            if hh == goal[0] and ww==goal[1]:
                flg = True
                break
            for i in range(4):
                nx, ny = ww+dx[i], hh+dy[i]
                if 0 <= ny < h and 0 <= nx < w and m[ny][nx] != "#" and d[ny][nx] == 0:
                    a.put([ny, nx])
                    d[ny][nx] = 1
                for i in range(-2,3):
                    for j in range(-2,3):
                        if 0 <= hh+i < h and 0 <= ww+j < w and m[hh+i][ww+j]=="." and mimi>goal[1]-(hh+i)+goal[0]-(ww+j) and d[hh+i][ww+j] == 0:
                            t=[hh+i,ww+j]
                            mimi=goal[1]-(hh+i)+goal[0]-(ww+j)
                            k=1
        if flg==True:
            break

        #mimi=100000
        #k=0
        """
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= hh+i < h and 0 <= ww+j < w and m[hh+i][ww+j]=="." and mimi>goal[1]-(hh+i)+goal[0]-(ww+j) and d[hh+i][ww+j] == 0:
                    t=[hh+i,ww+j]
                    mimi=goal[1]-(hh+i)+goal[0]-(ww+j)
                    k=1"""
        #print(t)
        if k>0:
            a.put(t)
            cnt+=1
        else:
            canwarp=False
            break

    return cnt if flg else -1

print(bfs(h, w, m, start, goal))

Submission status: Wrong Answer

Solution code:
import heapq

def ok(i, j):
    return 0 <= i < H and 0 <= j < W and S[i][j] == '.'

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
C_h -= 1
C_w -= 1
D_h, D_w = map(int, input().split())
D_h -= 1
D_w -= 1
S = []
for _ in range(H):
    row = list(input())
    S.append(row)
if S[D_h][D_w] == '#':
    print(-1)
else:
    queue = [(0, (C_h, C_w))]
    seen = {(C_h, C_w)}
    while queue:
        score, cur = heapq.heappop(queue)
        if cur == (D_h, D_w):
            print(score)
            break
        i, j = cur
        for offset in (1, -1):
            i_next = i + offset
            j_next = j + offset
            if ok(i_next, j) and (score, i_next, j) not in seen:
                heapq.heappush(queue, (score, (i_next, j)))
                seen.add((score, i_next, j))
            if ok(i, j_next) and (score, i, j_next) not in seen:
                heapq.heappush(queue, (score, (i, j_next)))
                seen.add((score, i, j_next))

        for a in [-2, -1, 1, 2]:
            for b in [-2, -1, 1, 2]:
                i_jump = i + a
                j_jump = j + b
                if ok(i_jump, j_jump) and (score + 1, i_jump, j_jump) not in seen:
                    heapq.heappush(queue, (score + 1, (i_jump, j_jump)))
                    seen.add((score + 1, i_jump, j_jump))
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import queue
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
s = ["" for _ in range(h)]
p = [[-1 for _ in range(w)] for _ in range(h)]
for i in range(h):
  si = str(input())
  s[i] = si  
i = 0
flag = False
q = queue.Queue()
q.put((ch,cw))
p[ch][cw] = 0
l = [(ch,cw)]
la = l.append
while True:
  while not q.empty():
    j,k = q.get()
    if j == dh and k == dw:
      print(i)
      exit()
    p[j][k] = i
    for hi,wi in [(-1,0),(1,0),(0,-1),(0,1)]:
      if 0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            la((j+hi,k+wi))
  nl = []
  nla = nl.append
  for j,k in l:
    for hi,wi in [(-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,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2)]:
      if  0 <= j+hi and j+hi < h and 0 <= k+wi and k+wi < w:
        if s[j+hi][k+wi] == ".":
          if p[j+hi][k+wi] == -1:
            q.put((j+hi,k+wi))
            nla((j+hi,k+wi))
            p[j+hi][k+wi] = i+1
  if q.empty():
    print(-1)
    exit()
  l = nl
  i += 1

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+4):
    for w in range(2,W+4):
        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]:
            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:
h,w=map(int,input().split())
sy,sx=map(int,input().split())
sy-=1
sx-=1
gy,gx=map(int,input().split())
gy-=1
gx-=1

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

from collections import deque
stack = deque([(sy,sx)])
maze[sy][sx]=0

checked=[[0]*w for _ in range(h)]


while len(stack)>0:
    (y,x)=stack.pop()
    if checked[y][x]==0:
        checked[y][x]=1
        if (y,x)==(gy,gx):
            print(maze[y][x])
            exit()
        for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#" and maze[ny][nx]>maze[y][x]):
                    stack.appendleft((ny,nx))
                    maze[ny][nx]=maze[y][x]
                #ワープ
                elif maze[ny][nx]=="#":
                    ny+=my
                    nx+=mx
                    if 0<=ny<h and 0<=nx<w:
                        if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                            stack.append((ny,nx))
                            maze[ny][nx]=maze[y][x]+1
        #斜めのワープを入れる
        for (my,mx) in ((1,1),(-1,-1),(-1,1),(1,-1)):
            for k in (1,2):
                ny=my*k+y
                nx=mx*k+x
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+k):
                        stack.append((ny,nx))
                        maze[ny][nx]=maze[y][x]+1
        for (my,mx) in ((1,2),(-1,-2),(-1,2),(1,-2),(2,1),(-2,-1),(-2,1),(2,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+k):
                    stack.append((ny,nx))
                    maze[ny][nx]=maze[y][x]+1

#for item in maze:
    #print(item)
print(-1)

Submission status: Wrong Answer

Solution code:
import copy
import math
import time
import statistics
import math
import itertools
import bisect
import sys
from decimal import *
from collections import deque


def get_int():
    return int(input())

def get_string():
    return input()

def get_int_list():
    return [int(x) for x in input().split()]

def get_string_list():
    return input().split()

def get_int_multi():
    return map(int, input().split())

def get_string_char_list():
    return list(str(input()))

# print("{} {}".format(a, b))
# a_list = [0] * a
sys.setrecursionlimit(10 ** 6)

def main():
    start = time.time()

    h, w = get_int_list()
    sr, sc = get_int_list()
    er, ec = get_int_list()

    d = [[-1] * (w+2) for _ in range(h+2)]

    for i in range(h):
        wk = get_string()
        for ii in range(w):
            if wk[ii] == ".":
                d[i+1][ii+1] = 10 ** 6

    d[sr][sc] = 0
    q = deque([])
    q.append([sr,sc])

    def idou(i,ii,cnt_mahou):
        if d[i][ii] == 10 ** 6:
            q.append([i, ii])
            d[i][ii] = cnt_mahou

    ans = -1
    flg = True
    finish = False
    while flg:
        flg = False
        while q:
            wk = q.popleft()
            i = wk[0]
            ii = wk[1]
            cnt_mahou = d[i][ii]

            idou(i - 1, ii, cnt_mahou)
            idou(i + 1, ii, cnt_mahou)
            idou(i, ii - 1, cnt_mahou)
            idou(i, ii + 1, cnt_mahou)

            if d[er][ec] != 10 ** 6:
                ans = d[er][ec]
                finish = True
                break

        if finish:
            break

        for iii in range(h):
            for iiii in range(w):
                if cnt_mahou == d[iii][iiii]:

                    # 魔法を使う
                    for wk in range(-2, 3):
                        for wk2 in range(-2, 3):
                            if abs(wk) + abs(wk2) > 1:
                                flg = True
                                idou(iii + wk, iiii + wk2, cnt_mahou + 1)




    print(ans)

    print(time.time() - start)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

# ワープを最低で何回使うか
# 上下左右2つ向こうまでの範囲内でワープできる
# 隣接する'.'が領域

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

pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        # 歩いて移動
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            pos.append([ny, nx])
            dp[ny][nx] = dp[y][x]
    # ワープ
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            # 歩いて移動不可能でないと使わない
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and dp[wy][wx] == -1:
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])

Submission status: Wrong Answer

Solution code:

import sys
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
Sh,Sw = map(int,input().split())
Sh -= 1
Sw -= 1
Gh,Gw = map(int,input().split())
Gh -= 1
Gw -= 1
S = [list(input()) for _ in range(H)]
D = [[-1 for _ in range(W)] for _ in range(H)]
D[Sh][Sw] = -1


walk = [(1,0),(-1,0),(0,1),(1,0)]
warp = [(x,y) for x in range(-2,3) for y in range(-2,3) if abs(x) + abs(y) > 1]

def validPosition(h,w):
	return 0 <= h and h < H and 0 <= w and w < W

search = [(0, Sh, Sw)]
V = [[False for _ in range(W)] for _ in range(H)]
while D[Gh][Gw] == -1:
	walked = []
	# walk
	while len(search) > 0:
		(d, h, w) = search.pop()
		if D[h][w] >= 0:
			continue
		V[h][w] = True
		D[h][w] = d
		walked.append((d,h,w))
		for (x,y) in walk:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and S[hh][ww] == "." and D[hh][ww] == -1:
				search.append((d, hh, ww))
	# warp
	next_search=[]
	for (d,h,w) in walked:
		for (x,y) in warp:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and not V[hh][ww] and S[hh][ww] == "." and D[hh][ww] == -1:
				V[hh][ww] = True
				next_search.append((d+1, hh, ww))
	if len(next_search) == 0:
		break
	search = next_search

print(D[Gh][Gw])

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, 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

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

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 visited[h+dh][w+dw]:
                continue
            if M[h+dh][w+dw] > M[h][w]:
                M[h+dh][w+dw] = M[h][w]
                visited[h+dh][w+dw] = True
                q.append((h+dh, w+dw))
    for wh, ww in warp:
        if 0 <= h+wh < H and 0 <= w+ww < W and S[h+wh][w+ww] == ".":
            if M[h+wh][w+ww] > M[h][w] + 1:
                M[h+wh][w+ww] = M[h][w] + 1
                q.append((h+wh, w+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])