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,hw = map(int, input().split())
dh,dw = map(int, input().split())

sx,sy=ch-1,hw-1
gx,gy=dw-1,dh-1

l = [None]*h
for i in range(h):
    l[i] = list(input())

dist = [[10**9]*w for i in range(h)]
dist[sy][sx] = 0

from collections import deque

def walk(warped,cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque(warped)
#    Q.append(start)

    walked=warped

    changed=False

    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==10**9:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
            #            print("EXITTTTTTTTTTTTT")
            #            print("cnt",cnt)
            #            print("walked:",walked)
                        print(cnt)
                        exit()
    return walked,changed

def warp(walked,cnt):
    warped=[]
    changed=False

    for x,y in walked:
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if dx==0 and dy==0:
                    continue
                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==10**9:
                        changed=True
#                        print(nx,ny)
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
 #                           print("EXITTTTTTTTTTTTT")
                            print(cnt)
 #                           print("warped:",warped)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
#    print(walked)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
#    print(warped)

#    print(walkchange,warpchange)
    if not walkchange and not warpchange:
        print(-1)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
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())
ch-=1
cw-=1
dh-=1
dw-=1
directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
directions_warp = [[-2, -2], [-2, -1], [-2, 0], [-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]]
s = []
for i in range(h):
    sh = input()
    s.append(sh)
gone = [[-1]*w for i in range(h)]
que = deque([[ch, cw]])
gone[ch][cw]=0
boo = True
count = 0
while boo ==True:
    now = []
    while que:
        nh, nw = que.pop()
        now.append((nh, nw))
        for gh, gw in directions:
            if nh+gh<0 or nh+gh>=h or nw+gw<0 or nw+gw>=w:
                pass
            elif gone[nh+gh][nw+gw]==0:
                pass
            else:
                if s[nh+gh][nw+gw]=="#":
                    pass
                else:
                    now.append((nh+gh, nw+gw))
                    gone[nh+gh][nw+gw]=0
                    que.appendleft([nh+gh, nw+gw])
    if gone[dh][dw]==0:
        print(count)
        break
    boo2 = False
    for nh, nw in now:
        for gh, gw in directions_warp:
            if nh+gh<0 or nh+gh>=h or nw+gw<0 or nw+gw>=w:
                pass
            else:
                if s[nh+gh][nw+gw]=="#":
                    pass
                elif gone[nh+gh][nw+gw]==0:
                    pass
                else:
                    boo2 = True
                    gone[nh+gh][nw+gw]=0
                    que.appendleft([nh+gh, nw+gw])
    if boo2 == False:
        print(-1)
        break
    count+=1

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys

mX = [0, 1, 0, -1]
mY = [1, 0, -1, 0]
zX = [2, 2, 2,  2, 2, 1, 1, 1, 1, 0,  0, -1, -1, -1, -1, -2, -2, -2, -2, -2]
zY = [2, 1, 0, -1, 2, 2, 1, -1, -2, 2, -2,  2, -2, 1, -1, 2,  1,  0, -1,  2]


def bfs(u, S, M, H, W):  # u 開始点

    q = deque()
    q.append(u)
    while q:
        u = q.popleft()

        # 徒歩移動
        for i in range(4):
            nx = u[0] + mX[i]
            ny = u[1] + mY[i]
            if nx < 0 or H <= nx:
                continue
            if ny < 0 or W <= ny:
                continue
            if S[nx][ny] == "#":
                continue

            if M[nx][ny] == -1 or M[nx][ny] > M[u[0]][u[1]]:  # state を確認
                M[nx][ny] = M[u[0]][u[1]]  # 徒歩移動
                q.append([nx, ny])

        # 魔法移動
        for i in range(20):
            wx = u[0] + zX[i]
            wy = u[1] + zY[i]
            if wx < 0 or H <= wx:
                continue
            if wy < 0 or W <= wy:
                continue
            if S[wx][wy] == "#":
                continue
            if M[wx][wy] == -1:  # state を確認
                M[wx][wy] = M[u[0]][u[1]] + 1
                q.append([wx, wy])


def main():

    H, W = map(int, sys.stdin.readline().rstrip().split())
    Ch, Cw = map(int, sys.stdin.readline().rstrip().split())
    Dh, Dw = map(int, sys.stdin.readline().rstrip().split())

    S = []
    for i in range(H):
        S.append(sys.stdin.readline().rstrip())

    M = [[-1 for _ in range(W)] for _ in range(H)]

    if M[Ch - 1][Cw - 1] == "#":
        print(-1)
        return

    M[Ch - 1][Cw - 1] = 0
    bfs([Ch - 1, Cw - 1], S, M, H, W)

    print(M[Dh - 1][Dw - 1])


main()

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0, 1, -1, -1, 1], [0, 1, 0, -1, 1, 1, -1, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if i <= 3 and s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.append((nx, ny))
            elif s[ny][nx] == '#' and s[y][x] == '.' and d[ny][nx] > d[y][x] + 1:
                d[ny][nx] = d[y][x] + 1
                que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
#from bisect import bisect_left as bl, bisect_right as br, insort
#from heapq import heapify, heappush, heappop
#from collections import defaultdict as dd, deque, Counter
#from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var) : sys.stdout.write(' '.join(map(str, var))+'\n')
def out(var) : sys.stdout.write(str(var)+'\n')
from decimal import Decimal
#from fractions import Fraction
#sys.setrecursionlimit(100000)
INF = float('inf')
mod = int(1e9)+7


h,w=mdata()
ch,cw=mdata()
dh,dw=mdata()
ch-=1
dh-=1
cw-=1
dw-=1
if ch==dh and cw==dw:
    out(0)
    exit()
S=[data() for i in range(h)]
stack=[(dh,dw)]
steps=[(0,1),(1,0),(-1,0),(0,-1)]
moves={(dh,dw)}
mat=[[0]*w for i in range(h)]
mat1=[[INF]*w for i in range(h)]
mat1[ch][cw]=0
while stack:
    a,b=stack.pop()
    for i,j in steps:
        if 0<=a+i<h and 0<=b+j<w and S[a+i][b+j]=='.' and (a+i,b+j) not in moves:
            moves.add((a+i,b+j))
            stack.append((a+i,b+j))
            mat[a+i][b+j]=mat[a][b]+1
if (ch,cw) in moves:
    out(0)
    exit()
moves1={(ch,cw)}
stack=[(ch,cw)]
set2=set()
while stack:
    stack1=[]
    while stack:
        a, b = stack.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                if 0 <= a + i < h and 0 <= b + j < w and S[a + i][b + j] == '.':
                    if (a + i, b + j) not in moves1:
                        moves1.add((a + i, b + j))
                        stack1.append((a + i, b + j))
                    mat1[a+i][b+j]=min(mat1[a+i][b+j],mat1[a][b]+1)
                    if (i,j) in steps :
                        mat1[a + i][b + j] = min(mat1[a + i][b + j], mat1[a][b])
                    if (a + i, b + j) in moves:
                        set2.add((a+i,b+j))
    stack=stack1
if set2:
    ans=INF
    for (i,j) in set2:
        ans=min(ans,mat1[i][j]+mat[i][j])
    out(ans)
else:
    out(-1)

Submission status: Wrong Answer

Solution code:
#D
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
A= [list(input()) for _ in range(H)]
d= [ [ -1 for _ in range(W) ] for _ in range(H)]
ans=0
cnt=0
v = deque([ [ch,cw] ])
d[ch][cw]=0
move = [(1,0),(-1,0),(0,1),(0,-1)]  #y,xの順

while cnt <=10**3:
    while v:
        a = v.pop()
        for mv in move:
            y = a[0]+mv[0]
            x = a[1]+mv[1]
            if 0<=y<=H-1 and 0<=x<=W-1:
                if d[y][x]== -1:
                    if A[y][x]==".":
                        d[y][x] = d[a[0]][a[1]]
                        v.append([y,x])
                        if y==dh and x==dw:
                            print(d[y][x])
                            exit()
    else:
        cnt +=1
        for i in range(0,W):
            for j in range(0,H):
                if d[j][i]==-1:
                    if A[j][i]==".":
                        d[j][i]=10**6
                        k = max(j-2,0)
                        l = min(j+2,H-1)
                        m = max(i-2,0)
                        n = min(i+2,W-1)
                        for s in range(m,n+1):
                            for t in range(k,l+1):
                                if d[t][s]>=0:
                                    d[j][i] = min(d[j][i],d[t][s]+1)
                        if d[j][i]==10**6:
                            d[j][i]=-2
                        else:
                            v.append([j,i])
                            if j==dh and i==dw:
                                print(d[j][i])
                                exit()

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

Ch +=1
Cw += 1
Dh += 1
Dw += 1

start = (Ch, Cw)
goal = (Dh, Dw)

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] = 1000

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] == 1000:
    now.append((x+1, y))
  if counter[x][y+1] == 1000:
    now.append((x, y+1))
  if counter[x-1][y] == 1000:
    now.append((x-1, y))
  if counter[x][y-1] == 1000:
    now.append((x, y-1))

#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 1000:
  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 > 2000:
    print(-1)
    exit()
print(ans)

Submission status: Wrong Answer

Solution code:
h, w = map(int,input().split())
sx, sy = map(int,input().split())
gx, gy = map(int,input().split())
S = [input() for i in range(h)]

sx-=1
sy-=1
gx-=1
gy-=1

A = [[-1,0],[1,0],[0,-1],[0,1]]
B = []
for i in range(-2,3):
    for j in range(-2,3):
        if i*j != 0:
            B.append([i,j])
# print(B)

# O((V + E)log(V))
# Cは [[スタート頂点, ゴール頂点, 重み], ...] のリスト

M = [[] for i in range(h*w)]

for i in range(h):
    for j in range(w):
        if S[i][j] == ".":
            for a in A:
                ai = i+a[0]
                aj = j+a[1]
                if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                    M[i*w+j].append([ai*w+aj, 0])
            for b in B:
                bi = i+b[0]
                bj = j+b[1]
                if 0 <= bi < h and 0 <= bj < w and S[bi][bj] == ".":
                    M[i*w+j].append([bi*w+bj,1])


# for i in range(len(C)):

#     M[C[i][0]].append([C[i][1], C[i][2]])  # 無向グラフなら両方追加
#     M[C[i][1]].append([C[i][0], C[i][2]])  # 無向グラフなら両方追加

n = h*w

import heapq

D = [float("inf")] * n  # 頂点0からの距離
P = [-1] * n  # 頂点0からの最短距離において、そこの直前の頂点(経路復元に利用)
D[sx*w+sy] = 0
V = [0] * n  # その頂点のD[i]が最短距離と確定したら1
Q = []  # 優先度付きキュー
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            # print(v)
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, [alt, v])
# print(D)
ans = D[gx*w+gy]
if ans == float("inf"):
    ans = -1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import queue

# input
H, W = map(int, sys.stdin.readline().strip().split())
Ch, Cw = map(int, sys.stdin.readline().strip().split())
Dh, Dw = map(int, sys.stdin.readline().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
    s = str(input())
    S.append(list(s))


# solve
q = queue.Queue()
q.put((Ch, Cw))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while True:
    if q.empty():
        break
    uh, uw = q.get()

    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        vh = uh + dh
        vw = uw + dw

        # 盤上にいるか確認
        if vh < 0 or vh >= H:
            continue
        if vw < 0 or vw >= W:
            continue

        # 壁の確認
        if S[vh][vw] == "#":
            continue

        # 到達済みか確認
        if fp[vh][vw] <= fp[uh][uw]:
            continue

        # 探索候補地に追加
        q.put((dh, dw))
        fp[vh][vw] = fp[uh][uw]

    for h in range(-2, 3):
        for w in range(-2, 3):
            vh = uh + h
            vw = uw + w

            # 盤上にいるか確認
            if vh < 0 or vh >= H:
                continue
            if vw < 0 or vw >= W:
                continue

            # 壁の確認
            if S[vh][vw] == "#":
                continue

            # 到達済みか確認
            if fp[vh][vw] <= fp[uh][uw] + 1:
                continue

            # 探索候補地に追加
            q.put((vh, vw))
            fp[vh][vw] = fp[uh][uw] + 1


if fp[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(fp[Dh][Dw])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline


def main():
    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 = [None] * (H + 4)
    S[0] = S[1] = S[-1] = S[-2] = "#" * (W + 4)
    for h in range(2, H + 2):
        S[h] = "".join(["##", input().rstrip(), "##"])

    CC = [[-1] * (W + 4) for _ in range(H + 4)]
    CC_i = 0
    for h in range(2, H + 2):
        for w in range(2, W + 2):
            if CC[h][w] != -1: continue
            if S[h][w] == "#": continue
            queue = deque([(h, w)])
            while queue:
                h, w = queue.popleft()
                CC[h][w] = CC_i
                for i, j in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    y, x = h + i, w + j
                    if CC[y][x] != -1: continue
                    if S[y][x] == "#": continue
                    queue.append((y, x))
            CC_i += 1

    CC_S = CC[Ch][Cw]
    CC_G = CC[Dh][Dw]

    G = [[] for _ in range(CC_i)]
    for h in range(2, H + 2):
        for w in range(2, W + 2):
            if S[h][w] == "#": continue
            CC_from = CC[h][w]
            for i in (-2, -1, 0, 1, 2):
                for j in (-2, -1, 0, 1, 2):
                    y, x = h + i, w + j
                    CC_to = CC[y][x]
                    if CC_to == -1: continue
                    if CC_to != CC_from:
                        if CC_to not in G[CC_from]:
                            G[CC_from].append(CC_to)

    ans = -1
    visited_CC = [False] * CC_i
    queue = deque([(CC_S, 0)])
    while queue:
        cc, n_warp = queue.popleft()
        visited_CC[cc] = True
        if cc == CC_G:
            ans = n_warp
            break
        for dd in G[cc]:
            if visited_CC[dd]: continue
            queue.append((dd, n_warp + 1))

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, 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

maze = []
for _ in range(H):
    row = list(input())
    maze.append(row)

def dfs(i, j, cnt):
    mapped[i][j] = cnt

    for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        x = i + dx
        y = j + dy
        if 0 <= x < H and 0 <= y < W and maze[x][y] == "." and mapped[x][y] == -1:
            dfs(x, y, cnt)
        elif 0 <= x < H and 0 <= y < W and maze[x][y] == "#":
            edges[cnt].add((i, j))

cnt = 0
mapped = [[-1] * W for _ in range(H)]
edges = defaultdict(set)
for i in range(H):
    for j in range(W):
        if maze[i][j] == "." and mapped[i][j] == -1:
            dfs(i, j, cnt)
            cnt += 1

# edges からワープで移動できる島を繋いで、グラフを作る
g = defaultdict(set)
for num in edges:
    for i, j in edges[num]:
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                x = i + dx
                y = j + dy
                if 0 <= x < H and 0 <= y < W and mapped[x][y] != -1 and mapped[x][y] != num:
                    g[num].add(mapped[x][y])
                    g[mapped[x][y]].add(num)

# gでのstart, endの最短距離をbfsで求める
start = mapped[ch][cw]
end = mapped[dh][dw]
q = deque([(start, 0),])
seen = set()

isFind = False
while q:
    size = len(q)
    for _ in range(size):
        node, d = q.popleft()
        seen.add(node)
        if node == end:
            print(d)
            isFind = True
            break
        for adj in g[node]:
            if adj not in seen:
                q.append((adj, d+1))

if not isFind:
    print(-1)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W = LMIIS()
    Ch,Cw = LMIIS()
    Ch -= 1
    Cw -= 1
    Dh,Dw = LMIIS()
    Dh -= 1
    Dw -= 1
    S = []
    for i in range(H):
        S.append(input())
    
    num_warp = []
    for i in range(H):
        num_warp.append([-1]*W)
    num_warp[Ch][Cw] = 0
    
    targets_walk = deque([(Ch,Cw)])
    targets_warp = deque([(Ch,Cw)])

    def check_and_move(y,x,n):
        if 0 <= y < H and 0 <= x < W and num_warp[y][x] == -1 and S[y][x] == '.':
            num_warp[y][x] = n
            return True
        return False

    # BFS
    while targets_walk:
        #　歩いて行ける範囲を全部いく
        while targets_walk:
            y,x = targets_walk.pop()
            num_currrent_warp = num_warp[y][x]
            for y2,x2 in [(y-1,x),(y,x+1),(y+1,x),(y,x-1)]:
                if check_and_move(y2,x2,num_currrent_warp):
                        # 歩きの探索対象に追加
                        targets_walk.append((y2,x2))
                        # ワープの探索対象に追加
                        targets_warp.append((y2,x2))




        # ワープで行ける範囲を1巡
        while targets_warp:
            y,x = targets_warp.pop()
            num_currrent_warp = num_warp[y][x]
            for y2,x2 in[
                    (y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),
                    (y-1,x-2),(y-1,x-1),(y-1,x+1),(y-2,x+2),
                    (y,x-2),(y,x+2),
                    (y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),
                    (y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2)
                ]:

                if check_and_move(y2,x2,num_currrent_warp+1):
                    # 歩きの探索対象に追加
                    targets_walk.append((y2,x2))
        
        

    ans = num_warp[Dh][Dw]
    print(-1 if ans == INF else ans)


    
main()

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([])
    line=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    line.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 1:
        while len(queue)>0:
            x,y=queue.popleft()
            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])
                        line.append([X,Y])
                        color[X][Y]="gray"
            color[x][y]="black"

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

    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:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def valid(a, b):
    return 0 <= a < n and 0 <= b < m


n, m = sp()
sx, sy = sp()
ex, ey = sp()
sx -= 1
sy -= 1
ex -= 1
ey -= 1
mat = [list(data()) for i in range(n)]
answer = 10 ** 10
q = deque()
q.append([sx, sy, 0])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
vis = [[0] * m for _ in range(n)]
vis[sx][sy] = 1
while q:
    sx, sy, jm = q.popleft()
    if sx == ex and sy == ey:
        answer = min(answer, jm)
        continue
    cnt = 0
    for i in range(4):
        tx, ty = sx + x[i], sy + y[i]
        if valid(tx, ty) and mat[tx][ty] == ".":
            if tx == ex and ty == ey:
                answer = min(answer, jm)
                cnt += 1
            elif not vis[tx][ty]:
                q.append([tx, ty, jm])
                vis[tx][ty] = 1
                cnt += 1
    if cnt == 0:
        jm += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                tx, ty = sx + i, sy + j
                if valid(tx, ty) and mat[tx][ty] == ".":
                    if tx == ex and ty == ey:
                        answer = min(answer, jm)
                    elif not vis[tx][ty]:
                        q.append([tx, ty, jm])
                        vis[tx][ty] = 1
if answer == 10 ** 10:
    print(-1)
    exit()
print(answer)

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

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)

count = 0
best = 0

while True:
  while Q:
    new_Q = []
    for node in Q:
      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

  if V[f1][f2]==1:
    print(count)
    break
  else:
    temp = sum(sum(kk) for kk in V) 
    count += 1
    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>-1 and y>-1 and x<h and y<w:
            if G[x][y] == '.':
              part.append((x,y))
       
    ALL = list(set(part))

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