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

Solution (Python):
from collections import deque

def solve(h, w, ch, cw, dh, dw, s):
    W, H = w+5, h+5
    def pos(r, c):
        return (r+2)*W + c+2
    G = [0] * (W*H)
    label = 0
    for r in range(h):
        for c in range(w):
            if (s[r][c] == '.') and (G[pos(r,c)] == 0):
                label += 1
                que = deque([(r, c)])
                G[pos(r,c)] = label
                while que:
                    cr, cc = que.popleft()
                    for dr, dc in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                        nr, nc = cr+dr, cc+dc
                        if (0 <= nr < h) and (0 <= nc < w) and (s[nr][nc] == ".") and (G[pos(nr,nc)] == 0):
                            G[pos(nr,nc)] = label
                            que.append((nr, nc))

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

    neighbors = [(dr*W+dc) for dc in range(-2, 3) for dr in range(-2, 3) if abs(dr) + abs(dc) > 0]
    used = [True] * (W*H)
    for r in range(h):
        for c in range(w):
            used[pos(r,c)] = (s[r][c] == "
    que = deque([(start, 0)])
    label_dist_mapping = [-1] * (label + 1)
    used[start] = True
    label_dist_mapping[G[start]] = 0
    while que:
        cpos, n = que.popleft()
        if cpos == goal:
            return n
        for d in neighbors:
            npos = cpos + d
            if not used[npos]:
                used[npos] = True
                m = label_dist_mapping[G[npos]]
                if (G[npos] == G[cpos]) or (n == m): 
                    que.appendleft((npos, n))
                else:
                    label_dist_mapping[G[npos]] = n + 1
                    que.append((npos, n+1))
    return -1

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

Solution (Python):
import sys


def get_index(s):
	return int(s) - 1


def search_nearby(h, w):

	search(h + 1, w, False)
	search(h - 1, w, False)
	search(h, w + 1, False)
	search(h, w - 1, False)


def search_using_warp(h, w):
  
  for i in range(-2, 3):
    search(h - 2, w + i)
    search(h + 2, w + i)

  for i in range(-2, 3):
    if i != 0:
      search(h - 1, w + i)
      search(h + 1, w + i)

  search(h, w + 2)
  search(h, w - 2)


def search(h, w, is_using_warp = True):
  global is_reached
  global que
  global next_que

  if can_reach(h, w):
	  is_reached[h][w] = True
	  next_que.append([h, w])

	  if not is_using_warp:
	    que.append([h, w])


def can_reach(h, w):
	global H
	global W
	global maze

	if h < 0 or h >= H or w < 0 or w >= W:
		return False
	elif maze[h][w] == '
		return False
	elif is_reached[h][w]:
		return False
	else:
		return True


from collections import deque
import copy

H, W = map(int, input().split())
Ch, Cw = map(get_index, input().split())
Dh, Dw = map(get_index, input().split())

maze = []

for _ in range(H):
	maze.append(input())

is_reached = [[False] * W for _ in range(H)]

next_que = deque()
next_que.append([Ch, Cw])
mp = 0

while len(next_que) > 0:
  que = copy.deepcopy(next_que)

	
  while len(que) > 0:
    h, w = que.popleft()
    is_reached[h][w] = True

    search_nearby(h, w)

  if is_reached[Dh][Dw]:
    print(mp)
    exit()

  que = copy.deepcopy(next_que)
  next_que.clear()
  mp += 1

	
  while len(que) > 0:
    h, w = que.popleft()
    is_reached[h][w] = True

    search_using_warp(h, w)

  if is_reached[Dh][Dw]:
    print(mp)
    exit()

print(-1)

Solution (Python):
h, w = list(map(int, input().split()))
si, sj = list(map(int, input().split()))
ti, tj = list(map(int, input().split()))
s = [None] * h
for i in range(h):
    s[i] = input()


d_a = [(-1,0), (0,-1),(1,0),(0,1)]

d_b = [ (i, j) for j in range(-2, 3) for i in range(-2, 3)]



INF = int(1e9)

dist = [[INF for j in range(w+2)] for i in range(h+2)]


for i in range(h+2):
    dist[i][0] = 0
    dist[i][-1] = 0
for j in range(w+2):
    dist[0][j] = 0
    dist[-1][j] = 0
for i in range(h):
    for j in range(w):
        if s[i][j]=='



from collections import deque
q = deque()


dist[si][sj] = 0
q.append((si,sj))

while (len(q)>0):
    i, j = q[0]
    d = dist[i][j]
    q.popleft()
    
    for v in range(len(d_a)):
        di, dj = d_a[v][0]+i, d_a[v][1]+j
        if (di, dj) == (ti, tj):
            print(d)
            exit(0)
        if (dist[di][dj]<=d):
            continue 
        dist[di][dj] = d
        q.appendleft((di, dj))
    
    for v in range(len(d_b)):
        
        di, dj = (d_b[v][0]+i)%(h+2), (d_b[v][1]+j)%(w+2)
        if (dist[di][dj]<=d):
            continue 
        dist[di][dj] = d+1
        q.append((di, dj))

ans = dist[ti][tj]
if ans == INF:
    ans = -1
print(ans)

Solution (Python):
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]


dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])

Solution (Python):
from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]


dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])

Solution (Python):
from collections import deque
H, W = map(int, input().split())
cy, cx = map(int, input().split())
dy, dx = map(int, input().split())
maze = ['
for hh in range(H):
    maze.append('
maze.append('

stepx = [-1, 0, 1, 0]
stepy = [0, -1, 0, 1]
visited = [[0]*(W+2) for _ in range(H+2)]

deque2 = deque()
def floodfill(comp, src):
    count = 0
    while len(src) > 0:
        stak = []
        for (sy, sx) in src:
            
            visited[sy][sx] = comp
            count += 1
            deque2.append((sy, sx))
            for i in range(4):
                ny, nx = sy + stepy[i], sx + stepx[i]
                if nx > 0 and nx <= W and ny > 0 and ny <= H\
                        and visited[ny][nx] == 0 and maze[ny][nx] == '.':
                    visited[ny][nx] = -1
                    stak.append((ny, nx))
        src = stak

    return count


def findnextz():
    nxt = []
    while len(deque2) > 0:
        (h, w) = deque2.popleft()
        for ii in range(-2, 3):
            nh = h + ii
            if nh > 0 and nh <= H:
                for jj in range(-2, 3):
                    nw = w + jj
                    if nw > 0 and nw <= W and visited[nh][nw] == 0 and maze[nh][nw] == '.':
                        visited[nh][nw] = -1
                        nxt.append((nh, nw))
    return nxt

def findnext(comp):
    count = 0
    nxt = []
    for h in range(1, H+1):
        for w in range(1, W+1):
            if visited[h][w] == comp:
                for ii in range(-2, 3):
                    nh = h + ii
                    if nh > 0 and nh <= H:
                        for jj in range(-2, 3):
                            nw = w + jj
                            if nw > 0 and nw <= W and visited[nh][nw] == 0 and maze[nh][nw] == '.':
                                visited[nh][nw] = -1
                                nxt.append((nh, nw))

    return nxt

ans = 0
total = 0
comp = 1


if maze[cy][cx] == '.' and visited[cy][cx] == 0:
    count = floodfill(comp, [(cy, cx)])









while count > 0 and visited[dy][dx] <= 0:
    total += count
    
    src = findnextz()
    comp += 1
    if len(src) > 0:
        count = floodfill(comp, src)
    else: count = 0

print(visited[dy][dx] - 1)

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)


h, w = map(int, input().split())
maze = [[-1 for i in range(w)] for j in range(h)]
ch, cw = map(int, input().split())
ch, cw = ch-1, cw-1
dh, dw = map(int, input().split())
dh, dw = dh-1, dw-1


ans = 0
for i in range(h):
    maze[i] = input()

INF = h*w
distance = [[INF for i in range(w)] for j in range(h)]

queue0 = deque()
queue0.append((ch,cw))
distance[ch][cw] = 0

queue1 = deque()

while queue0 or queue1:

    if queue0:
        y, x = queue0.popleft()
    elif queue1:
        y, x = queue1.popleft()

    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y+dy, x+dx
            if dy == dx == 0: continue
            elif abs(dy) + abs(dx) == 1:
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '
                            queue0.append((ny, nx))
                            distance[ny][nx] = distance[y][x]
            else:
                if 0 <= nx < w and 0 <= ny < h:
                    if maze[ny][nx] != '
                            queue1.append((ny, nx))
                            distance[ny][nx] = distance[y][x]+1


ans = distance[dh][dw]
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque

def main():
    H, W = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    
    
    
    
    
    s = ["
    s.append("
    for i in range(H):
        s.append("
    s.append("
    s.append("

    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "
                ans[i][j] = -2
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    ans[ch][cw] = 0
    
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    magic = [[-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]]
    
    mylist = deque([[ch, cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x, y = mylist.popleft()
        mylist2.append([x, y])
        for p, q in move:
            v1, v2 = x+p, y+q
            
            if ans[v1][v2] == -1:
                mylist.append([v1, v2])
                ans[v1][v2] = ans[x][y]
        
        if len(mylist) == 0:
            
            while len(mylist2) > 0:
                x2, y2 = mylist2.popleft()
                for v1, v2 in magic:
                    i, j = x2+v1, y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i, j])
    print(ans[dh][dw])
if __name__ == "__main__":
    main()

Solution (Python):
from itertools import product
from collections import deque
from sys import stdin
input = 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 = [None]*H
for i in range(H):
    S[i] = list(input())

moveA = ((1,0),(0,1),(-1,0),(0,-1))
moveB = []
for i,j in product((-2,-1,0,1,2), repeat=2):
    if (i,j) not in moveA:
        moveB.append((i,j))

mapmatrix = [[-1]*W for _ in range(H)]
queue = deque()
queue.append((Cw,Ch))
mapmatrix[Ch][Cw] = 0

worpqueue = deque()
worpqueue.append((Cw,Ch))
while queue or worpqueue:
    while queue:
        x,y = queue.popleft()
        worpnum = mapmatrix[y][x]

        for dx, dy in moveA:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if mapmatrix[Y][X] == -1 and S[Y][X] == '.':
                    mapmatrix[Y][X] = worpnum
                    queue.append((X,Y))
                    worpqueue.append((X,Y))
                    
    nextworpqueue = deque()
    while worpqueue:
        x,y = worpqueue.popleft()
        worpnum = mapmatrix[y][x]

        for dx, dy in moveB:
            X = x + dx; Y = y + dy
            if X >= 0 and X < W and Y >= 0 and Y < H:
                if mapmatrix[Y][X] == -1 and S[Y][X] == '.':
                    mapmatrix[Y][X] = worpnum + 1
                    queue.append((X,Y))
                    nextworpqueue.append((X,Y))
    
    while nextworpqueue:
        x,y = nextworpqueue.popleft()
        worpqueue.append((x,y))
        
print(mapmatrix[Dh][Dw])

Solution (Python):
from collections import deque


if __name__ == '__main__':

    H, W = map(int, input().split())
    s_h, s_w = map(int, input().split())
    e_h, e_w = map(int, input().split())

    s_h -= 1
    s_w -= 1
    e_h -= 1
    e_w -= 1

    M = []

    for i in range(H):
        s = input()
        M.append(s)

    found = False

    dq = deque()
    dist = [[0 for _ in range(W)] for _ in range(H)]

    for i in range(H):
        for j in range(W):
            dist[i][j] = int(1e7)

    dist[s_h][s_w] = 0

    dq.append((s_h, s_w))

    while dq:
        h, w = dq.pop()
        
        if h == e_h and w == e_w:
            found = True
            break
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                nh = h + dx
                nw = w + dy
                if dx == 0 and dy == 0:
                    continue
                if nh >= H or nh < 0 or nw >= W or nw < 0:
                    continue
                d = 1
                if M[nh][nw] == '
                    continue
                if (abs(dx) == 1 and abs(dy) == 0) or (abs(dy) == 1 and abs(dx) == 0):
                    d = 0
                if dist[nh][nw] > dist[h][w] + d:
                    dist[nh][nw] = dist[h][w] + d
                    if d == 0:
                        dq.append((nh, nw))
                    else:
                        dq.appendleft((nh, nw))
    if not found:
        dist[e_h][e_w] = -1
    print(dist[e_h][e_w])

Solution (Python):
from collections import deque
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())
M = [input() for _ in range(H)]

cnt = 0
Q = deque()
Q.appendleft((ch, cw, cnt))
VISITED = set()
answer = 0
while Q:
    curh, curw, cnt = Q.popleft()
    if (curh, curw) in VISITED:
        continue
    else:
        answer = max(answer, cnt)
        VISITED.add((curh, curw))
    if (curh,curw) == (dh,dw):
        print(answer)
        break
    minh = curh-2 if curh-2 >= 0 else 0
    minw = curw-2 if curw-2 >= 0 else 0
    maxh = curh+2 if curh+2 <= H-1 else H-1
    maxw = curw+2 if curw+2 <= W-1 else W-1

    for h in range(minh, maxh+1):
        for w in range(minw, maxw+1):
            if M[h][w] == "
                continue
            else:
                Q.append((h,w,cnt+1))
    for a, b in [(-1,0), (1,0), (0,-1), (0,1)]:
        h,w = curh+a, curw+b
        if (0 <= h < H) and (0 <= w < W) and not M[h][w] == "
            Q.appendleft((h,w,cnt))
else:
    print(-1)

Solution (Python):
from collections import deque


def main():
    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)]
    d = [[-1 for _ in range(W)] for _ in range(H)]

    q = deque([])
    q.appendleft((0, Ch - 1, Cw - 1))

    while len(q):
        worp_count, x, y = q.popleft()

        if d[x][y] != -1:
            continue
        d[x][y] = worp_count

        for i, j in ((a, b) for a in range(-2, 3) for b in range(-2, 3)):
            nx = x + i
            ny = y + j
            if 0 <= nx < H and 0 <= ny < W and S[nx][ny] == '.':
                if i == 0 and j == 0:
                    continue
                elif abs(i) + abs(j) == 1:
                    q.appendleft((worp_count, nx, ny))
                else:
                    q.append((worp_count + 1, nx, ny))

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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
INF = float("inf")

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

dist = [[INF] * w for _ in range(h)]
dist[ch][cw] = 0
q = deque([(cw, ch)])

while q:
    x, y = q.popleft()
    for _x in range(-2, 3):
        for _y in range(-2, 3):
            if _x == _y == 0:
                continue
            next_x, next_y = x + _x, y + _y
            if not 0 <= next_x < w:
                continue
            if not 0 <= next_y < h:
                continue
            if S[next_y][next_x] == "
                continue
            if abs(_x) + abs(_y) <= 1:
                if dist[next_y][next_x] <= dist[y][x]:
                    continue
                q.appendleft((next_x, next_y))
                dist[next_y][next_x] = dist[y][x]
            else:
                if dist[next_y][next_x] <= dist[y][x] + 1:
                    continue
                q.append((next_x, next_y))
                dist[next_y][next_x] = dist[y][x] + 1

if dist[dh][dw] != INF:
    print(dist[dh][dw])
else:
    print(-1)

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline

def solve():
    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)]
    visited = [[False] * W for _ in range(H)]
    dq = deque([(0, Ch, Cw)])

    while dq:
        d, i, j = dq.popleft()
        if (i, j) == (Dh, Dw):
            print(d)
            exit()
        if visited[i][j]:
            continue
        visited[i][j] = True
        for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
                dq.appendleft((d, ni, nj))
        for di in range(-2, 3):
            for dj in range(-2, 3):
                if di == dj == 0:
                    continue
                ni, nj = i + di, j + dj
                if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                    dq.append((d + 1, ni, nj))
    print(-1)

if __name__ == "__main__":
    solve()

Solution (Python):
from collections import deque
H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S=[input() for _ in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

P = [[float('inf')] * W for _ in range(H)]
a = [(1,0), (0,1), (-1,0), (0,-1)]
q=deque()
q.append((Ch,Cw,0))

while q:
  dq=deque()
  hh, ww, d = q.popleft()
  if type(P[hh][ww]) is int:
    continue
  dq.append((hh,ww))
  P[hh][ww]=d
  V=[]
  while dq:
    h, w = dq.popleft()
    V.append((h,w))
    for n in a:
      nh=h+n[0]
      nw=w+n[1]

      if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and type(P[nh][nw]) is float:
        P[nh][nw] = min(P[nh][nw], P[h][w])
        dq.append((nh,nw))

  for h,w in V:
    for x in range(-2, 3):
      for y in range(-2, 3):
        nh = h + x
        nw=w+y
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.' and type(P[nh][nw]) is float:
          q.append((nh,nw,d+1))

ans = P[Dh][Dw]
print(ans if type(ans) is int else -1)

Solution (Python):



import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    deq = np.empty(H * W + 100, np.int64)
    dist[S] = 0
    deq[0], l, r = S, 0, 1
    while l < r:
        v, l = deq[l], l + 1
        vx, vy = divmod(v, W)
        
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'

print(main(wall, Sx, Sy, Tx, Ty))

Solution (Python):
import base64
import subprocess
import gzip


exe_bin = b'\x1f\x8b\x08\x00\x9d0J_\x02\xff\xed\xbdY\x8f\xb2J\x170\xfa[\x0cj\x1cb\x82\x88\xa2QPQT\x14AP\x10\xb9P\xc1\x01q\x9eG\xf4\xb7\x9f\xa2\xe8~\xe8\xed\xd3\xee\xb3\xbf\xe4\xcb\xb98y\xbd\xe8.kQ\x8b\xaa5\xd7\xb4\x9c\xe4\xf38\x86\x1e\x10\tG\xbd\xcf\xe39\x0b\xa0\x92\x94\x89WFE!\x00\xab\x1a\xab^\xd0\x0fK\xb3H[\xdex\xcf6Vz@\xc3\xa8<\x9b\xcb<\xf2\x9d{\xbc_8\xa4\xe2\x02\xaf\xe3^\x8b\xdfJ\x83[U\x1e\xbc\x95\xb0\xd5"\x9b\xfe\xea\xc1CJ@,,\x9aJ]`\xd5o\xa5\xf4\xabo\xb7\xdfJ\xb0\xe3^)\xbe\xdd\xcc\x93\xe8\xbf~d\xde\x17D\xdeJ(\x1a\xa7\xbb?\xb08\xc3:$\x9f\xb8\xfb\xdeC\xf2UM\xbe\x95t4A\xc8\xb0\x14\xd15n\xfb\x8e\xe5p`1\x88\x85\x08\x95sn\x15\x11b^\xdd\xb7R\xb2$\xc6\xd8\xb7\x92G\x17H\x12\xf8GBQ\xdc\x1d\xe5o%.{\xa9\x85\xdfJ\xb0\x19,\xb5^\xafp\x05~m\x05|C\xcb\xad\xfb\xa5d\xbd\x0e\xb1\xe3[\xc9\xc3"Jb\xa1\nG\x84\xfe\x1f\x7f\x92\xa5\xf4\xb5\xeab9\x1c\xe25\x88\xf4\xdf\xa9\xdb\x16\xba\x8b\xd4[\xc9\xe3t\xa5\xb1\x94\xd9\x9a\x16"R\xdd\xaao\xcfj\xe6\xae\xba\x1b\x1d\x9a\xdb\x06\xa8\xc3K\x9aO\n\x19\xf0\x1d\xee{\x9df\xcd>\x8a\xfb=Y\x83\xec\xf1\x06\x98\xd2\xbb\xc5\x06\x04\xc0\xe7\xc8E\x1a\xb7\x17\xa9g\xa0m,\xfd\xc78\xcf\x0c"2\xa6.S/\xd8,

exe_bin = base64.b85decode(gzip.decompress(exe_bin))

with open("./kyomu", 'wb') as f:
    f.write(exe_bin)

subprocess.run(["chmod +x ./kyomu"], shell=True)
subprocess.run(["./kyomu"], shell=True)

Solution (Python):

import sys
from collections import deque
import itertools

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

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="
    elif 0<=i-1 and s[i-1][j]=="
    elif j+1<w and s[i][j+1]=="
    elif 0<=j-1 and s[i][j-1]=="

wpg=[(i,j) for i,j in hhww if wpg2[i][j]>=1 ]
                
for i,j in wpg:
    gg[i][j]=[(i+ii,j+jj) for ii,jj in wpij if (0<=i+ii and i+ii<h and 0<=j+jj and j+jj<w and s[i+ii][j+jj]==".")]

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:

        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Solution (Python):

import sys
from collections import deque
import itertools

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

icase=0
if icase==0:
    h,w=map(int,input().split())
    ch,cw=map(int,input().split())
    ch-=1
    cw-=1
    dh,dw=map(int,input().split())
    dh-=1
    dw-=1
    s=[[] for i in range(h)]
    for i in range(h):
        s[i]=input()
        
ij=[(1,0),(-1,0),(0,1),(0,-1)]
wpij=[(1,1),(-1,-1),(-1,1),(1,-1),
      (2,-2),(2,-1),(2,0),(2,1),(2,2),
      (-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),
      (1,2),(0,2),(-1,2),(1,-2),(0,-2),(-1,-2)]

hh=[i for i in range(h)]
ww=[i for i in range(w)]

g=[[[] for i in range(w)] for i in range(h)]
gg=[[[] for i in range(w)] for i in range(h)]
wpg2=[[0]*w for i in range(h)]
wpg=[]

hhww=[(i,j) for i,j in itertools.product(hh,ww) if s[i][j]=="."]
                
for i,j in hhww:
    g[i][j]=[(i+ii,j+jj) for ii,jj in ij if (0<=(i+ii)<h and 0<=(j+jj)<w and s[i+ii][j+jj]==".")] 
    if i+1<h and s[i+1][j]=="
    elif 0<=i-1 and s[i-1][j]=="
    elif j+1<w and s[i][j+1]=="
    elif 0<=j-1 and s[i][j-1]=="

for i,j in hhww:
    if wpg2[i][j]>=1:
        wpg.append((i,j))
                
for i,j in wpg:
    for ii,jj in wpij:
         if 0<=i+ii and i+ii<h and 0<=j+jj \
            and j+jj<w and s[i+ii][j+jj]==".":
                gg[i][j].append((i+ii,j+jj))        

q=deque([(ch,cw)])
qq=deque()
parent=[[-1]*w for i in range(h)]
parent[ch][cw]=0
dist=[[-1]*w for i in range(h)]
dist[ch][cw]=0
while True:
    while q:

        hi,wi = q.popleft()
        if len(gg[hi][wi])>0:
            qq.append((hi,wi))
        for hj,wj in g[hi][wi]:
            if parent[hj][wj] !=-1:
                continue
            else:
                parent[hj][wj]=(hi,wi)
                dist[hj][wj]=dist[hi][wi]+1
                q.append((hj,wj))
                if hj==dh and wj==dw:
                    print(dist[dh][dw]//(10**7))   
                    sys.exit()

    while qq:
        hi,wi = qq.popleft()
        for hj,wj in gg[hi][wi]:
            if parent[hj][wj]!=-1:
                continue
            parent[hj][wj]=(hi,wi)
            dist[hj][wj]=dist[hi][wi]+10**7
            q.append((hj,wj))
            if hj==dh and wj==dw:
                print(dist[dh][dw]//(10**7))   
                sys.exit()

    if len(q)==0:
        break
print(-1)

Solution (Python):
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

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '
            S[i][j] = WALL
        else:
            S[i][j] = INI

directions = [[0, -1], [-1, 0], [0, 1], [1, 0]]

d = deque()
d.appendleft((Ch, Cw, 0))

while len(d):
    y, x, c = d.popleft()
    
    if S[y][x] != INI:
        continue
    S[y][x] = c
    if y == Dh and x == Dw:
        break
    for dy, dx in directions:
        ny = y + dy
        nx = x + dx
        if ny >= 0 and ny < h and nx >= 0 and nx < w:
            if S[ny][nx] == INI:
                d.appendleft((ny, nx, S[y][x]))
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny = y + dy
            nx = x + dx
            if ny >= 0 and ny < h and nx >= 0 and nx < w:
                if S[ny][nx] == INI:
                    d.append((ny, nx, S[y][x] + 1))

print(S[Dh][Dw])