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

for i in range(H):
  l=list(input())
  for j in range(len(l)):
    if l[j]=='.':l[j]=-1
    if l[j]=='#':l[j]=-2
  maze.append(l)
update_list=[]
def isIn(h,w):
  if h<0 or h>=H or w<0 or w >=W:return False
  return True
def update(maze,h,w,value):
  global update_list
  vectors=[[-1,0],[1,0],[0,1],[0,-1]]
  maze[h][w]=value
  update_list=[]
  u=[]
  for i in range(25):
    if not isIn(h+i//5,w+i%5):continue
    if maze[h+i//5][w+i%5]>maze[h][w] or maze[h+i//5][w+i%5]==-1:
      if [h+i//5,w+i%5] not in u:
        u.append([h+i//5,w+i%5])
        maze[h+i//5][w+i%5]=value+1
  for vector in vectors:
    if not isIn(h+vector[0],w+vector[1]):continue
    if maze[h+vector[0]][w+vector[1]]>maze[h][w] or maze[h+vector[0]][w+vector[1]]==-1:
      maze[h+vector[0]][w+vector[1]]=maze[h][w]
      update(maze,h+vector[0],w+vector[1],value)
      
  for h,w in u:
    if maze[h][w]==value+1 and not [h,w] in update_list:
      update_list.append([h,w])

update(maze,Ch-1,Cw-1,0)
while update_list:
  for h,w in update_list:
    update(maze,h,w,maze[h][w])
print(maze[Dh-1][Dw-1])

Submission status: Wrong Answer

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

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

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

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

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from collections import deque


def bfs(u, n, g):
    queue = deque([u])
    d = [None] * n  # uからの距離の初期化
    d[u] = 0  # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d


def main():
    h, w = map(int, input().split())
    c_h, c_w = map(lambda x: int(x) - 1, input().split())
    d_h, d_w = map(lambda x: int(x) - 1, input().split())
    s = [None] * h
    for i in range(h):
        s[i] = input()
    area = [[None] * w for i in range(h)]
    area_cnt = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == "#":
                continue

            if i > 0 and area[i - 1][j] is not None:
                area[i][j] = area[i - 1][j]
            elif j > 0 and area[i][j - 1] is not None:
                area[i][j] = area[i][j - 1]
            else:
                area[i][j] = area_cnt
                area_cnt += 1

    c_area = area[c_h][c_w]
    d_area = area[d_h][d_w]

    if c_area == d_area:
        print(0)
        return

    can_move = [set([]) for _ in range(area_cnt)]
    for i in range(h):
        for j in range(w):
            if area[i][j] is None:
                continue
            for k in range(-2, 3):
                if i + k < 0 or area_cnt <= i + k:
                    continue
                for m in range(-2, 3):
                    try:
                        if j + m < 0 or area_cnt <= j + m:
                            continue
                        if area[i + k][j + m] is None:
                            continue
                        if area[i][j] != area[i + k][j + m]:
                            can_move[area[i][j]].add(area[i + k][j + m])
                            can_move[area[i + k][j + m]].add(area[i][j])
                    except:
                        pass
    d = bfs(c_area, area_cnt, can_move)[d_area]
    if d is None:
        print(-1)
    else:
        print(d)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if q == goal:
                        return t
                    parent[q[0]][q[1]] = p
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


############################################################################################

from collections import deque
import sys
input = sys.stdin.readline

road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

"""
4 5
1 2
2 5
#.###
####.
###.#
#..##
"""

Submission status: Wrong Answer

Solution code:
def dfs(xt, yt, S, V, w):
    B = set()
    while(len(S) > 0):
        xi, yi = S.pop()
        A = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if i == 0 and j == 0:
                    continue
                xj, yj = xi + i, yi + j
                if xj < 0 or len(V) <= xj or yj < 0 or len(V[0]) <= yj:
                    continue
                if -1 <= i <= 1 and -1 <= j <= 1 and i * j == 0:
                    A.append((xj, yj))
                else:
                    B.add((xj, yj))

        for xj, yj in A:
            if xj == xt and yj == yt:
                return False, B, V, w
            if V[xj][yj] > 0:
                V[xj][yj] = -1
                S.append((xj, yj))

    B_new = []
    for x, y in B:
        if x == xt and y == yt:
            return False, B, V, w + 1
        if s[x][y] > 0:
            s[x][y] = -1
            B_new.append((x, y))
    return True, B_new, V, w

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 = [list(map(lambda x: int(x == '.'), list(input()))) for _ in range(h)]

flag = True
B = [(ch, cw)]
w = -1
s[ch][cw] = -1
while flag:
    flag, B, s, w = dfs(dh, dw, B, s, w + 1)
    if len(B) == 0:
        print(-1)
        break
else:
    print(w)

Submission status: Wrong Answer

Solution code:
import heapq
H, W = [int(n) for n in input().split()]
ch, cw = [int(n)-1 for n in input().split()]
dh, dw = [int(n)-1 for n in input().split()]
matrix = []
for i in range(H):
  row = []
  word = input()
  for w in word:
    row.append(w)
  matrix.append(row)

visited = {(ch,  cw)}
stack = [[0, ch, cw]]
reached = False
while stack:
  warp, i, j = heapq.heappop(stack)
  if (i, j) == (dh, dw):
    print(warp)
    reached = True
    break
  else:
    for a, b in [(i+1, j+1), (i+1, j), (i, j+1), (i-1, j-1), (i-1, j), (i, j-1)]:
      if 0<=a<H and 0<=b<W and (a, b) not in visited:
        if matrix[a][b] == '.':
          visited.add((a, b))
          heapq.heappush(stack, [warp, a, b])
        else:
          for k in range(-2, 3):
            for kk in range(-2, 3):
              aa, bb = i+k, j+kk
              if (aa, bb) not in visited and 0<=aa<H and 0<=bb<W and matrix[aa][bb] == '.':
                visited.add((aa, bb))
                heapq.heappush(stack, [warp+1, aa, bb])
if not reached:
  print(-1)

Submission status: Wrong Answer

Solution code:
# 2020/08/22
# AtCoder Beginner Contest 176 - D

# Input
h, w = map(int,input().split())
ch, cw = map(int,input().split())
dh, dw = map(int,input().split())
sl = list()
sl.append(['#'] * (w+2))
for i in range(h):
    s = list('#' + input())
    s.append('#')
    sl.append(s)
sl.append(['#'] * (w+2))

wcnt = 0
findflg = False
posq = list()
tl = [[0] * (w+2) for i in range(h+2)]
posq.append([ch, cw])
passq = list()

loopmax = (h // 2) * (w // 2)

for i in range(loopmax):
    while(len(posq) > 0):
        th, tw = posq.pop()
        if th == dh and tw == dw:
            findflg = True
            break
            
        passq.append([th, tw])
    
        if sl[th-1][tw] == '.' and tl[th-1][tw] == 0:
            posq.append([th-1, tw])
            tl[th-1][tw] = 1
        elif sl[th][tw-1] == '.' and tl[th][tw-1] == 0:
            posq.append([th, tw-1])
            tl[th][tw-1] = 1
        elif sl[th+1][tw] == '.' and tl[th+1][tw] == 0:
            posq.append([th+1, tw])
            tl[th+1][tw] = 1
        elif sl[th][tw+1] == '.' and tl[th][tw+1] == 0:
            posq.append([th, tw+1])
            tl[th][tw+1] = 1

    if findflg == True:
        break

    while(len(passq) > 0):
        ph, pw = passq.pop()
        
        for i in range(ph-2, ph+3):
            for j in range(pw-2, pw+3):
                if i > 0 and i <= h and j > 0 and j <= w:
                    if sl[i][j] == '.' and tl[i][j] == 0:
                        posq.append([i, j])
                        tl[i][j] = 1
    wcnt = wcnt + 1

# Output
if findflg == True:
    ans = wcnt
else:
    ans = -1
    
print(ans)

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] > c:
                    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:

# lrud = [[0, -1], [0, 1], [-1, 0], [1, 0], \
#     [1, -1], [1, 1], [-1, -1], [-1, 1]]
lrud = [[0, -1], [0, 1], [-1, 0], [1, 0]]
lrud2 = [[-1, -1], [1, 1], [-1, 1], [1, -1]]
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Ch, Cw = Ch-1, Cw-1
Dh, Dw = map(int, input().split())
Dh, Dw = Dh-1, Dw-1
S = [list(input()) for i in range(H)]

is_visited = [[float('inf') for j in range(W)]for i in range(H)]
is_visited[Ch][Cw] = 0
for i in range(2):
    for x in range(H):
        for y in range(W):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and not (cost and S[nx][ny]=='#'):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            for dx, dy in lrud2:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and cost != int(S[nx][ny]=='#'):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
    for x in range(H-1, -1, -1):
        for y in range(W-1, -1, -1):
            cost = int(S[x][y] == '#')
            for dx, dy in lrud:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and not (cost and S[nx][ny]=='#'):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
            for dx, dy in lrud2:
                nx, ny = x+dx, y+dy
                if 0 <= nx < H and 0 <= ny < W and cost != int(S[nx][ny]=='#'):
                    is_visited[x][y] = min(is_visited[x][y], is_visited[nx][ny]+cost)
# print(is_visited)
if is_visited[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(is_visited[Dh][Dw])

Submission status: Wrong Answer

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

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

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

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

if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def main():
    #l,r,d=map(int,input().split())
    h,w= map(int, input().split())
    cx,cy = map(int, input().split())
    dx,dy = map(int, input().split())
    s=[]
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
    for i in range(h):
        temp=input()
        temp="##"+temp+"##"
        s.append(list(temp))
    s.append(list("#"*(w+4)))
    s.append(list("#"*(w+4)))
#    for i in range(h+4):
#        print(s[i])

    visited = [[0 for i in range(w+4)] for _ in range(h+4)]
    warp = [[INFI for i in range(w+4)] for _ in range(h+4)]
    visited[cx+1][cy+1]=1
    warp[cx+1][cy+1]=0

    walkqueue = deque([])
    warpqueue = deque([])
    warpdire=[[-2,-2],[-1,-2],[0,-2],[1,-2],[2,-2],
           [-2,-1],[-1,-1],[1,-1],[2,-1],
           [-2,0],[2,0],
           [-2,1],[-1,1],[1,1],[2,1],
           [-2,2],[-1,2],[0,2],[1,2],[2,2],
              [0,-1],[-1,0],[1,0],[0,1]]
    walkdire=[[0,-1],[-1,0],[1,0],[0,1]]

    nowx=cx+1
    nowy=cy+1

    for i in warpdire:
        if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] == 0:
            warpqueue.append([nowx + i[0], nowy + i[1]])
            warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
            visited[nowx + i[0]][nowy + i[1]] = 1

    while warpqueue:
        if len(warpqueue) <= 0:
            break
        now = warpqueue.popleft()
        nowx = now[0]
        nowy = now[1]

        for i in warpdire:
            if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] == 0:
                warpqueue.append([nowx + i[0], nowy + i[1]])
                warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy] + 1, warp[nowx + i[0]][nowy + i[1]])
                visited[nowx + i[0]][nowy + i[1]] = 1
    for ii in range(h+4):
        for j in range(w+4):
            if visited[ii][j]>=2 or s[ii][j]=="#":
                continue

            nowx=ii
            nowy=j
            walkvisited=[]
            walkmin=warp[nowx][nowy]

            for i in walkdire:
                if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]] <= 1:
                    walkqueue.append([nowx + i[0], nowy + i[1]])
                    warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])

                    visited[nowx + i[0]][nowy + i[1]] = 2

            while walkqueue:
                if len(walkqueue) <= 0:
                    break
                now = walkqueue.popleft()
                nowx = now[0]
                nowy = now[1]
                walkmin = min(warp[nowx][nowy],walkmin)
                walkvisited.append([nowx,nowy])
                for i in walkdire:
                    if s[nowx + i[0]][nowy + i[1]] == "." and visited[nowx + i[0]][nowy + i[1]]<= 1:
                        walkqueue.append([nowx + i[0], nowy + i[1]])
                        warp[nowx + i[0]][nowy + i[1]] = min(warp[nowx][nowy], warp[nowx + i[0]][nowy + i[1]])
                        visited[nowx + i[0]][nowy + i[1]] = 2
            for i in walkvisited:
                warp[i[0]][i[1]]=walkmin



    if visited[dx+1][dy+1]==0:
        print("-1")
    else:
        print(warp[dx+1][dy+1])

#    for i in range(h+4):
 #       print(visited[i])
 #   for i in range(h+4):
 #       print(warp[i])




if __name__ == "__main__":

    main()

Submission status: Wrong Answer

Solution code:
import sys, math

# input = sys.stdin.readline

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


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


uf = UnionFind(H*W)
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            uf.parents[W*i+j] = math.inf
            continue
        if i != H-1 and S[i + 1][j] == '.':
            uf.union(W*i + j, W*(i+1) + j)
        if j != W-1 and S[i][j+1] == '.':
            uf.union(W*i + j, W*i + j + 1)

groupidx = {k: v for v, k in enumerate(uf.roots())}
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = -1
        else:
            S[i][j] = groupidx[uf.find(W*i+j)]


groups = list(range(len(uf.roots())))
can_reach = [[False]*len(groups) for _ in range(len(groups))]
for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue
        g = set()
        for s in S[i:i+2]:
            g |= set(s[j:j+2])
        if -1 in g:
            g.remove(-1)
        for k in g:
            can_reach[S[i][j]][k] = True
            can_reach[k][S[i][j]] = True
can_reach_ = {}
for i in range(len(groups)):
    can_reach_[i] = [j for j, k in enumerate(can_reach[i]) if k]
ans = 0
s = S[Ch-1][Cw-1]
g = S[Dh-1][Dw-1]
if s==g:
    print(0)
    sys.exit()

reached = set([s])
searched = [False]*len(groups)
ans = 0
while len(reached)>0:
    ans += 1
    new_reached = []
    for p in reached:
        searched[p] = True
    for p in reached:
        for k in can_reach_[p]:
            if k == g:
                print(ans)
                sys.exit()
            if not searched[p]:
                new_reached.append(p)
    reached = list(set(new_reached))

print(-1)