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 queue
import heapq

# 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 = []
heapq.heappush(q, (0, (Ch, Cw)))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while q:
    count, coo = heapq.heappop(q)
    uh, uw = coo

    if count > fp[uh][uw]:
        continue

    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

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

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                continue

            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] + 1:
                continue

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


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

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map = []
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
visit = [[-1]*w for i in range(h)]
visit[sy - 1][sx - 1] = 0
warp = []
cnt = 0

for i in range(-2, 3):
    for j in range(-2, 3):
        warp.append([i, j])


for i in range(h):
    s = input()
    map.append(s)

route = deque([[sy - 1, sx - 1]])

while route:
    while route:
        y, x = route.popleft()
        for i, j in move:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] == visit[y][x]:
                        continue
                    visit[k][l] = visit[y][x]
                    route.append([k, l])
    wroute = deque([])
    for i in range(w):
        for j in range(h):
            if visit[j][i] == cnt:
                wroute.append([j, i])
    while wroute:
        y, x = wroute.popleft()
        for i, j in warp:
            k = y + i
            l = x + j
            if 0 <= k < h and 0 <= l < w:
                if map[k][l] == ".":
                    if visit[k][l] != -1:
                        continue
                    visit[k][l] = visit[y][x] + 1
                    route.append([k, l])
        cnt += 1

print(visit[gy - 1][gx - 1])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

H, W = map(int, input().split())
C = [int(i) for i in input().split()]
D = [int(i) for i in input().split()]
maze = [["#"]+[i for i in input()]+["#"] for j in range(H)]
maze = [["#"]*(W+2)] + maze + [["#"]*(W+2)]
dp = [[-1 for i in range(W+2)] for j in range(H+2)]

dir = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dp[C[0]][C[1]] = 0
pos = deque([[C[0], C[1], 0]])

while len(pos) > 0:

    h, w, count = pos.popleft()

    for dh, dw in dir:
        if maze[h+dh][w+dw] == "#":
            continue
        elif dp[h+dh][w+dw] == -1 or count < dp[h+dh][w+dw]:
            dp[h+dh][w+dw] = count
            pos.append([h+dh, w+dw, count])

    for next_h in range(max(0, h-2), min(H, h+2)+1):
        for next_w in range(max(0, w-2), min(W, w+2)+1):
            if maze[next_h][next_w] == "#":
                continue
            elif dp[next_h][next_w] == -1 or count + 1 < dp[next_h][next_w]:
                dp[next_h][next_w] = count + 1
                pos.append([next_h, next_w, count+1])

print(dp[D[0]][D[1]])

Submission status: Wrong Answer

Solution code:
import heapq

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

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

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

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


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

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

                if MP[i][j]=='#':
                    continue
                if score[i][j]>score[y][x]+1:
                    score[i][j]=score[y][x]+1
                    heapq.heappush(q,(j,i,score[y][x]+1))
    for i in score:
        print(i)
    if score[Gy][Gx]==10**10:
        print(-1)
    else:
        print(score[Gy][Gx])
    
resolve()

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 = [[-1]*w for i in range(h)]
dist[sx][sy] = 0

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

    Q = deque(warped)
    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]==-1:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        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
                if abs(dx)+abs(dy)<=1:
                    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==-1:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

input = sys.stdin.readline

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

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    for i,j in q2:
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
    if not q:
        break
    tmp += 1

print(v[dh-1][dw-1])

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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



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


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

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

# ワープ回数
for i in range(1, 1000):
    flag = False
    new_kouho = kouho.copy()
    kouho.clear()
    for n in new_kouho:
        x = n[0]
        y = n[1]
        if floor[y][x] == i:
            warp(x, y, i)
            flag = True

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

    if flag == False:
        print("-1")
        sys.exit()

Submission status: Wrong Answer

Solution code:
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-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)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    else:
                        dist[h2][w2] = min(d,dist[h2][w2])
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and dist[h2][w2] == -1:
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))

Submission status: Wrong Answer

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a

# Union Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# 約数生成
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

h,w = lr()
ch,cw = lr()
ch-=1
cw-=1
dh, dw = lr()
dh-=1
dw-=1
s = [input() for i in range(h)]
visited = [[inf for j in range(w)] for i in range(h)]
revisited = [[False for j in range(w)] for i in range(h)]
visited[ch][cw] = 0
q = deque([[ch, cw]])
dir = [[0,1], [0,-1], [-1,0], [1,0]]
while q:
    y,x = q.popleft()
    c = visited[y][x]
    for dy,dx in dir:
        ny,nx = y+dy,x+dx
        if 0<=ny<h and 0<=nx<w:
            if s[ny][nx] == '.':
                if visited[ny][nx] == inf:
                    visited[ny][nx] = c
                    q.append([ny,nx])
    if len(q) == 0:
        dq = deque([[y, x]])
        revisited[y][x] = True
        while dq:
            y,x = dq.popleft()
            # ワープ処理
            ty, tx = y-2, x-2
            for i in range(5):
                for j in range(5):
                    ny, nx = ty + i, tx + j
                    if 0<=ny<h and 0<=nx<w:
                        if s[ny][nx]=='.':
                            if visited[ny][nx] == inf:
                                visited[ny][nx] = c+1
                                q.append([ny,nx])
                            elif visited[ny][nx] == c and revisited[ny][nx] == False:
                                revisited[ny][nx] = True
                                dq.append([ny,nx])
if visited[dh][dw] != inf:
    print(visited[dh][dw])
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
from collections import deque

h, w = map(int, input().split())
ch,cw = map(int, input().split())
dh, dw = map(int, input().split())
ls = [input() for _ in range(h)]
#print(ls)
widou = []
for i in range(-2,3):
    for j in range(-2, 3):
        widou.append((i, j))
widou.remove((0,0))
widou.remove((1,0))
widou.remove((0,1))
widou.remove((-1,0))
widou.remove((0,-1))
#print(widou)

start = (ch-1, cw-1)
goal = (dh-1, dw-1)

explored = set()
tempexplored = set()

yexp= deque()
yexp.append(start)
ytemp= deque()
ytemp.append(start)
wap =0


while yexp:
    now = yexp.popleft()
    ytemp.popleft()

    if now == goal:
        print(wap)
        exit(0)

    explored.add(now)
    tempexplored.add(now)

    x= now[0]
    y= now[1]

    idou = [(1,0), (0,1), (0,-1), (-1,0)]
    for i, j in idou:
        a = x + i
        b = y + j
        if 0 <= a < h and 0 <= b < w:
            if ls[a][b] == '.':
                if (a, b) not in explored:
                    yexp.append((a,b))
                    ytemp.append((a,b))
                    explored.add((a,b))
                    tempexplored.add((a,b))
    #print(ytemp)
    #print(tempexplored)
    #print(explored)


    if len(ytemp) ==0:
        #print('waap')
        wap += 1
        for a,b in tempexplored:
            for i, j in widou:
                a = x + i
                b = y + j
                if 0 <= a < h and 0 <= b < w:
                    #print(a, b)
                    if ls[a][b] == '.':
                        if (a, b) not in explored:
                            #print('OK')
                            yexp.append((a, b))
                            ytemp.append((a, b))
                            explored.add((a, b))
        tempexplored = set()
print('-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 = [[-1]*w for i in range(h)]
dist[sx][sy] = 0

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

    Q = deque(warped)
    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]==-1:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        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
                if abs(dx)+abs(dy)<=1:
                    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==-1:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
    if not walkchange and not warpchange:
        print(-1)
        exit()

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

edge = [["#" for _ in range(W+2)]]
center = [["#"] + list(input()) + ["#"] for i in range(H)]
A_array = edge + center + edge

#セルをグループ毎に分割
cells_grouped = dict()
group_no = 1

edge = [[1 for _ in range(W+2)]]
center = [[1] + [0 for _ in range(W+2)] + [1] for i in range(H)] #提出用
is_visited = edge + center + edge

edge = [[0 for _ in range(W+2)]]
center = [[0] + [0 for _ in range(W+2)] + [0] for i in range(H)] #提出用
cell_group_dict = edge + center + edge

for i in range(1,H+1):
    for j in range(1,W+1):
        #print(i,j,A_array[i][j])
        if is_visited[i][j] == 0:
            is_visited[i][j] = 1
            
            if A_array[i][j] == ".":
                #function 幅優先探索(v)
                search_target_deque = deque() #    Q ← 空のキュー
                search_target_deque.append((i,j)) #    v を Q に追加
                grouped_cells = set()
                grouped_cells.add((i,j))

                while len(search_target_deque) != 0: #    while Q が空ではない do
                    m,n = search_target_deque.popleft() #        v ← Q から取り出す
                    #        v を処理する
                    cell_group_dict[m][n] = group_no
                    neighbor_nodes = [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]
                    for s,t in neighbor_nodes: #        for each v に接続している頂点 i do
                        if is_visited[s][t] == 0: # if i が未訪問 then
                            is_visited[s][t] = 1 #                iに訪問済みの印を付ける
                            if A_array[s][t] == ".":
                                search_target_deque.append((s,t)) #                i を Q に追加
                                grouped_cells.add((s,t))

                cells_grouped[group_no] = grouped_cells
                group_no += 1

                
#print("cells_grouped")
#print(cells_grouped)

#print("cell_group_dict")
#print(cell_group_dict)
                
#各グループから行けるグループを得る
warpable_group = {i:set() for i in range(group_no)}
for i in range(1,group_no):
    for cell in cells_grouped[i]:
        y = cell[0]
        x = cell[1]
        for m in range(y-2,y+3,1):
            for n in range(x-2,x+3,1):
                if 1<=m<=H and 1<=n<=W and cell_group_dict[m][n]!=0 and cell_group_dict[m][n]!=group_no:
                    warpable_group[i].add(cell_group_dict[m][n])
                        

#print("warpable_group")
#print(warpable_group)

#今度は深さ優先探索
def depthFirstSearch(start):
    visited_group = set()
    stack = list() #stack = Stack()
    visited_group.add(start) #start.setVisited()
    stack.append(start) #stack.push( start )
    
    while len(stack) != 0: #while not stack.empty():
        #print(stack)
        
        node = stack[-1] #    node = stack.top()
        
        if node == cell_group_dict[Dh][Dw] :#    if node == goal:
            return stack
        else:
            childs = warpable_group[node] # child = node.findUnvisitedChild()
            unvisited_childs = []
            for child in childs:
                if child not in visited_group:
                    unvisited_childs.append(child)
                    
            if len(unvisited_childs)==0: #if child == none:
                stack.pop(-1)            #    stack.pop()
            else:                        #else:
                for unvisited_child in unvisited_childs:
                    visited_group.add(unvisited_child) #child.setVisited()
                    stack.append(unvisited_child) #            stack.push( child )
    else:
        return False

#print(cell_group_dict[Ch][Cw])
#print(cell_group_dict[Dh][Dw])

ans = depthFirstSearch(cell_group_dict[Ch][Cw])

if ans == False:
    print(-1)
else:
    print(len(ans)-1)
    #print("Yes")

Submission status: Wrong Answer

Solution code:
from math import trunc
import sys
import copy
from collections import deque
import collections
import itertools
stdin = sys.stdin
import math

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces


h, w = na()
sh, sw = na()
gh, gw = na()

map = []
for _ in range(h):
    s = ns()
    map.append([0 if i=="." else 1 for i in s])

visited = [[100000 for j in range(w)] for i in range(h)]

def warp(nh, nw, now_warp):
    next_p = []
    topleft = [nh-2, nw-2]
    for i in range(5):
        for j in range(5):
            neh = topleft[0]+i
            new = topleft[1]+j
            if  check_position(neh, new):
                if visited[neh][new] > (now_warp+1):
                    next_p.append([neh, new])
    return next_p


def check_position(hi, wi):
    if hi<0 or hi>=h or wi<0 or wi>=w or map[hi][wi]==1:
        return False
    return True


positions = deque()
positions.append([sh-1, sw-1, 0])
while len(positions)>0:
    nh, nw, now_warp = positions.popleft()

    if now_warp >= visited[nh][nw]:
        continue

    visited[nh][nw] = now_warp
    moved = True
    if check_position(nh+1, nw):
        positions.append([nh+1, nw, now_warp])
    else:
        moved = False
    
    if check_position(nh, nw+1):
        positions.append([nh, nw+1, now_warp])
    else:
        moved = False
    
    if check_position(nh-1, nw):
        positions.append([nh-1, nw, now_warp])
    else:
        moved = False
    
    if check_position(nh, nw-1):
        positions.append([nh, nw-1, now_warp])
    else:
        moved = False
    
    if not moved:
        next_warps = warp(nh, nw, now_warp)
        for p in next_warps:
            positions.append([p[0], p[1], now_warp+1])

print(-1 if visited[gh-1][gw-1]==100000 else visited[gh-1][gw-1])

Submission status: Wrong Answer

Solution code:
import copy
from collections import deque

H, W = [int(i) for i in input().split()]
C = tuple([int(i) - 1 for i in input().split()])
D = tuple([int(i) - 1 for i in input().split()])
S = []
for i in range(H):
  s = list(input())
  S.append(s)
  
  
# 領域を計算
def dfs(arr, h, w):
  arr[h][w] = "#"
  region = set([tuple([h, w])])
  for i, j in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
      nh = h + i
      nw = w + j
      if 0 <= nh and 0 <= nw and nh < H and nw < W and arr[nh][nw] == ".":
        region |= dfs(arr, nh, nw)
  return region

regions = []
field = copy.deepcopy(S)

for h in range(H):
  for w in range(W):
    if field[h][w] == ".":
      region = dfs(field, h, w);
      regions.append(region)

s_reg = -1
g_reg = -1

for i in range(len(regions)):
  if C in regions[i]:
    s_reg = i
  if D in regions[i]:
    g_reg = i

count = 0
d = deque()
arrived = set()
d.append(s_reg)
arrived.add(s_reg)

while d:
  pos = d.popleft()
  if pos == g_reg:
    break
  # ワープできる領域を計算
  for p in regions[pos]:
    for h in range(-2, 3):
      for w in range(-2, 3):
        pw = p[0] + h
        ph = p[1] + w
        if pw < 0 or W <= pw or ph < 0 or H <= ph:
          # 欄外
          continue
        for i in range(len(regions)):
          if i not in arrived:
            if tuple([ph, pw]) in regions[i]:
              arrived.add(i)
              d.append(i)
  count += 1
  
if g_reg not in arrived:
  print(-1)
else:
  print(count)

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 = 10*6
for i in range(h):
    s.append(input())
    t.append([m]*w)
c -= 1
d -= 1
t[c][d] = 0
cnt = 0
stc1 = []
stc2 = []
a = 0
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) > a+1):
        a += 1
        c = stc1[a][0]
        d = stc1[a][1]
    else:
        if(len(stc2) > 0):
            stc1 = stc2
            stc2 = []
            a = 0
            c = stc1[0][0]
            d = stc1[0][1]
            cnt += 1
        else:
            break
if(t[e-1][f-1] == m):
    print(-1)
else:
    print(t[e-1][f-1])