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: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.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:
        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.appendleft((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
        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 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.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: Accepted

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
WarpX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
WarpY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(ch, cw)])
que2 = deque()
while que or que2:
    while que:
        y, x = que.popleft()
        for i in range(4):
            ny = y + NY[i]
            nx = x + NX[i]
            if 0 <= ny < h and 0 <= nx < w:
                if S[ny][nx] != "#" and grid[ny][nx] == -1:
                    grid[ny][nx] = grid[y][x]
                    que.append((ny, nx))
                elif S[ny][nx] == "#":
                    que2.append((y, x))
    while que2:
        y, x = que2.popleft()
        for i in range(20):
            ny = y + WarpY[i]
            nx = x + WarpX[i]
            if 0 <= ny < h and 0 <= nx < w:
                if S[ny][nx] != "#" and grid[ny][nx] == -1:
                    grid[ny][nx] = grid[y][x] + 1
                    que.append((ny, nx))

print(grid[dh][dw])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8))
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

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

start = (Ch, Cw)

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

counter = [[-1 for _ in range(W+4)] for _ in range(H+4)]
for k in range(2, H+2):
  for j in range(2, W+2):
    if S[k][j] == '.':
      counter[k][j] = 10**7

counter[Ch][Cw] = 0

#print(counter)
#print(S)

now = [start]
now_2 = [start]
while len(now_2) > 0:
  new = []
  for item in now_2:
    x = item[0]
    y = item[1]
    if counter[x+1][y] == 10**7:
      counter[x+1][y] = 0
      new.append((x+1, y))
    if counter[x][y+1] == 10**7:
      counter[x][y+1] = 0
      new.append((x, y+1))
    if counter[x-1][y] == 10**7:
      counter[x-1][y] = 0
      new.append((x-1, y))
    if counter[x][y-1] == 10**7:
      counter[x][y-1] = 0
      new.append((x, y-1))
  now += new
  now_2 = new
#print(now)
#print(counter)
if counter[Dh][Dw] == 0:
  print(0)
  exit()
ans = 0
while counter[Dh][Dw] == 10**7:
  if len(now) == 0:
    print(-1)
    exit() 
  nextlist = []
  ans += 1
  for item in now:
    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))
    if counter[x-1][y-1] > ans:
      counter[x-1][y-1] = ans
      nextlist.append((x-1, y-1))
    if counter[x-1][y+1] > ans:
      counter[x-1][y+1] = ans
      nextlist.append((x-1, y+1))
    if counter[x+1][y+1] > ans:
      counter[x+1][y+1] = ans
      nextlist.append((x+1, y+1))
    if counter[x+1][y-1] > ans:
      counter[x+1][y-1] = ans
      nextlist.append((x+1, y-1))
      
  
  now_2 = nextlist
  while len(now_2) > 0:
    new = []
    for item in now_2:
      x = item[0]
      y = item[1]
      if counter[x+1][y] == 10**7:
        counter[x+1][y] = 0
        new.append((x+1, y))
      if counter[x][y+1] == 10**7:
        counter[x][y+1] = 0
        new.append((x, y+1))
      if counter[x-1][y] == 10**7:
        counter[x-1][y] = 0
        new.append((x-1, y))
      if counter[x][y-1] == 10**7:
        counter[x][y-1] = 0
        new.append((x, y-1))
    nextlist += new
    now_2 = new
  now = nextlist
  #print(now)
  if ans > 10**7:
    print(-1)
    exit()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys

def BFS(task, ct):
  D = [(1,0), (0,1), (-1,0), (0,-1)]
  semi_visited = set()
  task_n = deque([])
  for s in task:
    semi_visited.add(s)
  while task:
    s = task.popleft()
    #print(s, ct, 1, task)
    if s == (hg, wg):
      print(ct)
      sys.exit()
    x = s[0]
    y = s[1]
    for d in D:
      s_n = (x+d[0], y+d[1])
      #print(s_n, s_n not in semi_visited)
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1 and (s_n not in semi_visited) and S[s_n[0]][s_n[1]] == ".":
        task.append(s_n)
        semi_visited.add(s_n) 
        visited.add(s_n)
  #print(semi_visited)   
  for s in semi_visited:
    warp(s, task_n)
  return (ct+1, task_n)

def warp(p, task_n):
  #print(p)
  x = p[0]
  y = p[1]
  for dh in range(-2,3):
    for dw in range(-2,3):
      s_n = (x+dh, y+dw)
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1:
        #print(s_n, visited)
        if S[s_n[0]][s_n[1]] == "." and s_n not in visited:
          task_n.append(s_n)
          visited.add(s_n)
  return task_n

H, W = map(int, input().split())
hs, ws = map(int, input().split())
hs -= 1
ws -= 1
hg, wg = map(int, input().split())
hg -= 1
wg -= 1

S = [input() for _ in range(H)]

task = deque([(hs, ws)])
visited = {(hs, ws)}
semi_visited = {(hs, ws)}
ct = 0

while task:
  #print(ct)
  ct, task = BFS(task, ct)
  #print(task, ct)
  
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    S = [list(map(str, input())) for _ in range(H)]

    q = deque()
    q.append((ch - 1, cw - 1, 0))

    pathA = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    pathB = []
    for i in range(5):
        for j in range(5):
            pathB.append((i - 2, j - 2))
    visited = [[-1] * W for _ in range(H)]

    while q:
        h, w, d = q.popleft()
        if visited[h][w] !=-1:
            continue
        visited[h][w] =d


        for h1, w1 in pathA:
            newh = h + h1
            neww = w + w1
            if newh >= 0 and newh < H and neww >= 0 and neww < W and S[newh][neww] == ".":
                if visited[newh][neww] == -1:
                    q.appendleft((newh, neww, d))

        for h1, w1 in pathB:
            newh = h + h1
            neww = w + w1
            if newh >= 0 and newh < H and neww >= 0 and neww < W and S[newh][neww] == ".":
                q.append((newh, neww, d + 1))

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
INF=10**10
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
m=[list(input()) for _ in range(H)]
s=(Ch-1,Cw-1)
g=(Dh-1,Dw-1)
d=[[INF]*W for _ in range(H)]
d[s[0]][s[1]]=0
q=deque()
q.append(s)
while q:
    y,x=q.pop()
    for dy,dx in [(0,1),(1,0),(0,-1),(-1,0)]:
        ny=y+dy
        nx=x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if m[ny][nx]=='.' and d[ny][nx]>d[y][x]:
            q.append((ny,nx))
            d[ny][nx]=d[y][x]
    for dy in range(-2,3):
        for dx in range(-2,3):
            if abs(dy)+abs(dx)<=1:
                continue
            ny=y+dy
            nx=x+dx
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if m[ny][nx]=='.' and d[ny][nx]>d[y][x]+1:
                q.appendleft((ny,nx))
                d[ny][nx]=d[y][x]+1
ans=d[g[0]][g[1]]
if ans<INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True, fastmath=True, parallel=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
import sys

f_inf = float("inf")

# Input#
# n = int(input())
h, w = map(int, input().split())
c_h, c_w = map(int, input().split())
d_h, d_w = map(int, input().split())

grid = []

d = deque()


for i in range(h + 1):
    if i == 0:
        array_tmp = "#" * w
    else:
        array_tmp = str(input().strip())
    array_tmp = "#" + array_tmp
    grid.append(list(array_tmp))


grid[c_h][c_w] = 0

d.append((c_h, c_w))


def check(tar_h, tar_w):
    if tar_h > h or tar_h < 1:
        return -1
    if tar_w > w or tar_w < 1:
        return -1
    if grid[tar_h][tar_w] == ".":
        return f_inf
    if grid[tar_h][tar_w] == "#":
        return -1
    else:
        return grid[tar_h][tar_w]


while len(d) != 0:
    tar_h, tar_w = d.popleft()
    tar_num = grid[tar_h][tar_w]
    if tar_num == "#":
        continue

    for i in range(5):
        for j in range(5):
            checknum = check(tar_h + i - 2, tar_w + j - 2)
            if checknum > tar_num:
                if (
                    (i == 2 and j == 1)
                    or (i == 2 and j == 3)
                    or (i == 1 and j == 2)
                    or (i == 3 and j == 2)
                ):
                    grid[tar_h + i - 2][tar_w + j - 2] = tar_num
                    d.appendleft((tar_h + i - 2, tar_w + j - 2))
                    if tar_h == d_h and tar_w == d_w:
                        print("{}".format(tar_num))
                        sys.exit()
                else:
                    if checknum > tar_num + 1:
                        grid[tar_h + i - 2][tar_w + j - 2] = tar_num + 1
                        d.append((tar_h + i - 2, tar_w + j - 2))

if check(d_h, d_w) == f_inf:
    ans = -1
else:
    ans = check(d_h, d_w)

print("{}".format(ans))

Submission status: Accepted

Solution code:
from collections import deque
import math
import copy

def main():
    hh,ww = list(map(int,input().split()))
    ch, cw = list(map(int,input().split()))
    dh, dw = list(map(int,input().split()))
    maze=[list(input()) for l in range(hh)]
    segid = 0

    # Maze preprocess
    for y in range(hh):
        for x in range(ww):
            if maze[y][x]=='.':
                maze[y][x]=math.inf
            elif maze[y][x] == '#':
                maze[y][x]=int(-1)
# segmentation
    for m in range(hh):
        for n in range(ww):
            if maze[m][n] == math.inf:
                maze[m][n] = segid
                que = deque([[m,n]])
                while que:
#                    print(que, maze)
                    current_hh, current_ww = que.popleft()
                    for i, j in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        next_hh, next_ww = current_hh + i, current_ww + j
                        if (next_hh >= 0) and (next_ww >= 0) and (next_hh < hh) and (next_ww < ww):
                            dist = maze[next_hh][next_ww]
                            if dist == math.inf:
                                maze[next_hh][next_ww] = segid
                                que.append([next_hh, next_ww])
                segid += 1
#                print(segid)

#create graph
    flag_segid = [1]*segid
    graph = [[] for _ in range(segid)]
    for m in range(hh):
        for n in range(ww):
            current_segid = maze[m][n]
            if (current_segid >= 0 ) and (flag_segid[current_segid] == 1):
                que = deque([[m, n]])
                while que:
#                    print(que, maze)
                    current_hh, current_ww = que.popleft()
                    for i in [-2, -1, 0, 1, 2]:
                        for j in [-2, -1, 0, 1, 2]:
                            # print([i,j])
                            if (i == 0 and j == 0):
                                continue
                            next_hh, next_ww = current_hh + i, current_ww + j
                            if (next_hh >= 0) and (next_ww >= 0) and (next_hh < hh) and (next_ww < ww):
                                next_segid = maze[next_hh][next_ww]
                                if (next_segid != -1) and (next_segid != current_segid):
                                    if not (next_segid in graph[current_segid]):
                                        graph[current_segid].append(next_segid)
#                                        print(graph)
                #flag_segid[current_segid] = 0

#solve graph https://qiita.com/ta-ka/items/a023a11efe17ab097433
#https://qiita.com/shizuma/items/e08a76ab26073b21c207
#https://zalgo-official.com/blog/research-blog/competition-programming/bfs-and-dijkstra



    start_graph = maze[ch-1][cw-1]
    end_graph = maze[dh-1][dw-1]


#   print(graph)
#   print(start_graph, end_graph)

    qq = deque()
    cost = [math.inf] * segid
    cost[start_graph] = 0
    qq.append(start_graph)
    while qq:
        v = qq.popleft()
        for i in graph[v]:
            newcost = cost[v] + 1
            if cost[i] > newcost:
                cost[i] = newcost
                qq.append(i)
#    print(cost)
    if cost[end_graph] == math.inf:
        print(-1)
    else:
        print(cost[end_graph])

main()

Submission status: Accepted

Solution code:
from collections import deque
 
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ddh,ddw=map(int,input().split())
s=[[c for c in input()] for _ in range(h)]

q=deque([(ch-1,cw-1,0)])
visit=[[0]*w for _ in range(h)]

while len(q)>0:
    uh,uw,cnt=deque.popleft(q)
    if visit[uh][uw]==1:
        continue

    stack=[(uh,uw)]
    stack2=[(uh,uw)]
    while len(stack)>0:
        vh,vw=stack.pop()

        visit[vh][vw]=1

        if vh==ddh-1 and vw==ddw-1:
            print(cnt)
            exit(0)

        for dh,dw in ((0,1),(0,-1),(1,0),(-1,0)):
            nh=vh+dh
            nw=vw+dw
            if 0<=nh<h and 0<=nw<w and visit[nh][nw]==0 and s[nh][nw]=='.':
                stack.append((nh,nw))
                stack2.append((nh,nw))

    
    while len(stack2)>0:
        vh,vw=stack2.pop()

        for dh in range(-2,3):
            for dw in range(-2,3):
                nh=vh+dh
                nw=vw+dw

                if 0<=nh<h and 0<=nw<w and visit[nh][nw]==0 and s[nh][nw]=='.':
                    deque.append(q,(nh,nw,cnt+1))
                
print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import deque, defaultdict

readline = stdin.readline

def main():
    H, W = map(int, readline().rstrip().split())
    CH, CW = map(lambda x: int(x) - 1, readline().rstrip().split())
    DH, DW = map(lambda x: int(x) - 1, readline().rstrip().split())
    S = [readline().rstrip() for _ in range(H)]
    v = defaultdict(lambda : False)
    dq = deque([(0, CH, CW)])
    while dq:
        d, h, w = dq.popleft()
        # print(f'{c} : {h} : {w} : {S[h][w]}')
        if (h, w) == (DH, DW):
            print(d)
            exit()
        if v[(h, w)]:
            continue
        v[(h, w)] = True
        for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nh = mh + h
            nw = mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                dq.appendleft([d, nh, nw])
        for mh in range(-2, 3):
            for mw in range(-2, 3):
                if mh == mw == 0:
                    continue
                nh = mh + h
                nw = mw + w
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[(nh, nw)]:
                    dq.append([d + 1, nh, nw])
    print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

H, W = map(int, input().split())
CH, CW = map(lambda x: int(x) - 1, input().split())
DH, DW = map(lambda x: int(x) - 1, input().split())
S = [input().rstrip() for _ in range(H)]
v = [[False] * W for _ in range(H)]
dq = deque([(0, CH, CW)])
while dq:
    d, h, w = dq.popleft()
    if (h, w) == (DH, DW):
        print(d)
        exit()
    if v[h][w]:
        continue
    v[h][w] = True
    for mh, mw in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nh, nw = mh + h, mw + w
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
            dq.appendleft([d, nh, nw])
    for mh in range(-2, 3):
        for mw in range(-2, 3):
            if mh == mw == 0:
                continue
            nh, nw = mh + h, mw + w
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and not v[nh][nw]:
                dq.append([d + 1, nh, nw])
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
ch, cw, dh, dw = ch - 1, cw - 1, dh - 1, dw - 1
s = [list(input()) for i in range(h)]
d = [[-1] * w for i in range(h)]
Q = deque([(ch, cw, 0)])
while Q:
    x, y, broken = Q.popleft()
    if d[x][y] != -1:
        continue
    d[x][y] = broken
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if 0 <= x + dx < h and 0 <= y + dy < w and s[x + dx][y + dy] == "." and d[x + dx][y + dy] == -1:
                if abs(dx) + abs(dy) == 1:
                    Q.appendleft((x + dx, y + dy, broken))
                else:
                    Q.append((x + dx, y + dy, broken + 1))
print(d[dh][dw])