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


import sys
from typing import Any, Callable, Deque, Dict, List, Mapping, Optional, Sequence, Set, Tuple, TypeVar, Union








from collections import deque                






















def main():
    Num = Union[int, float]
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)
    
    
    
    h, w = mi()
    ch, cw = mi_0()
    dh, dw = mi_0()
    grid = [input() for _ in range(h)]
    d = ((-1, 0), (1, 0), (0, 1), (0, -1))

    def bfs(start):
        q = deque()
        q.append((start, 0))    
        visited = [[False] * w for _ in range(h)]
        while q:
            point, num = q.popleft()
            ux, uy = point
            
            if ux == dh and uy == dw:
                return num
            if not visited[ux][uy]:
                visited[ux][uy] = True
                for dx, dy in d:
                    nx, ny = ux + dx, uy + dy
                    if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == '.' and not visited[nx][ny]:
                        q.appendleft(((nx, ny), num))    
                for dx in range(-2, 3):
                    for dy in range(-2, 3):
                        if dx == 0 and dy == 0:
                            continue
                        nx, ny = ux + dx, uy + dy
                        if 0 <= nx < h and 0 <= ny < w and grid[nx][ny] == '.' and not visited[nx][ny]:
                            q.append(((nx, ny), num + 1))    
        return -1
    
    start = (ch, cw)
    print(bfs(start))




if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H, W = map(int, input().split())
c1, c2 = map(int, input().split())
d1, d2 = map(int, input().split())
c1 += 1
c2 += 1
d1 += 1
d2 += 1
S = ["

ans = [[10000000]*(W+4) for _ in range(H+4)]
ans[c1][c2] = 0
q = deque([[c1, c2]])

x = [[-1, 0], [0, -1], [0, 1], [1, 0]]

while q:
    h, w = q.popleft()
    
    for a, b in x:
        nh = h+a
        nw = w+b
        if S[nh][nw] == ".":
            if ans[nh][nw] > ans[h][w]:
                ans[nh][nw] = ans[h][w]
                q.appendleft([nh, nw])
    
    for a in range(-2, 3):
        for b in range(-2, 3):
            nh = h+a
            nw = w+b
            if S[nh][nw] == ".":
                if ans[nh][nw] > ans[h][w]+1:
                    ans[nh][nw] = ans[h][w]+1
                    q.append([nh, nw])

if ans[d1][d2] == 10000000:
    print(-1)
else:
    print(ans[d1][d2])

Solution (Python):

from collections import deque

h, w = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

S = [list(input()) for _ in range(h)]
walk = [[False] * (w) for _ in range(h)]
jump = [[False] * (w) for _ in range(h)]


que = deque([])
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

que.append((sx, sy, 0))
walk[sx][sy] = True
jump[sx][sy] = True

ans = -1
while que:
    nowx, nowy, times = que.popleft()
    if nowx == gx and nowy == gy:
        ans = times
        break
    for i in range(4):
        nx = nowx + dx[i]
        ny = nowy + dy[i]
        if nx < 0 or nx >= h or ny < 0 or ny >= w:
            continue
        if walk[nx][ny]:
            continue
        if S[nx][ny] == ".":
            walk[nx][ny] = True
            que.appendleft((nx, ny, times))
    for ddx in range(5):
        for ddy in range(5):
            nx = nowx + ddx - 2
            ny = nowy + ddy - 2
            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            if jump[nx][ny]:
                continue
            if S[nx][ny] == ".":
                jump[nx][ny] = True
                que.append((nx, ny, times + 1))
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): 
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

def main():
    mod = 1000000007
    

    
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    
    
    S = tuple(input() for i in range(H)) 
    ch-=1;cw-=1;dw-=1;dh-=1
    N=H*W
    def dfs(start,goal):
        q=deque([(start,0)])
        visited=[-1]*N
        while len(q):
            e,d=q.popleft()
            
            if e==goal:
                return d
            if visited[e]!=-1:continue
            
            cx,cy=divmod(e,W)

            visited[e]=d
            for dx,dy in ((-1,0),(1,0),(0,1),(0,-1)):
                if 0<=cx+dx<H and 0<=cy+dy<W and S[cx+dx][cy+dy]==".":
                    ne=(cx+dx)*W+cy+dy
                    q.appendleft((ne,d))
            for dx in range(-2,3):
                for dy in range(-2,3):
                    if 0<=cx+dx<H and 0<=cy+dy<W and S[cx+dx][cy+dy]==".":
                        ne=(cx+dx)*W+cy+dy
                        q.append((ne,d+1))
        return -1
    print(dfs(ch*W+cw,dh*W+dw))

if __name__ == "__main__":
    main()

Solution (Python):
H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
sy,sx = sy-1,sx-1
gy,gx = gy-1,gx-1
S = [input() for i in range(H)]

import heapq
INF = float('inf')
dist = [[INF]*W for i in range(H)]
dist[sy][sx] = 0
hq = [(0,sx+sy*W)]
heapq.heapify(hq)
while hq:
    d,v = heapq.heappop(hq)
    y,x = divmod(v,W)
    for dx in range(-2,3):
        for dy in range(-2,3):
            if dx == dy == 0: continue
            nx,ny = x+dx,y+dy
            if not 0 <= nx < W: continue
            if not 0 <= ny < H: continue
            if S[ny][nx] == '
            if abs(dx)+abs(dy) <= 1:
                if dist[ny][nx] <= dist[y][x]: continue
                dist[ny][nx] = dist[y][x]
                heapq.heappush(hq, (d,nx+ny*W))
            else:
                if dist[ny][nx] <= dist[y][x] + 1: continue
                dist[ny][nx] = dist[y][x] + 1
                heapq.heappush(hq, (d+1, nx+ny*W))
print(-1 if dist[gy][gx]==INF else dist[gy][gx])

Solution (Python):
from collections import deque




d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
d_ = [-2, -1, 0, 1, 2]


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)]
INF = 10 ** 6

ch, cw = ch - 1, cw - 1
dh, dw = dh - 1, dw - 1
visited = [[INF] * w for i in range(h)]

visited[ch][cw] = 0
val = 0
q = deque([(ch, cw, val)])
while q:
    i, j, val = q.popleft()
    if val > visited[i][j]:
        continue
    val = visited[i][j]

    for di, dj in d:
        nxt_i, nxt_j = i + di, j + dj
        if not(0 <= nxt_i < h and 0 <= nxt_j < w):
            continue
        elif s[nxt_i][nxt_j] == "
            continue
        elif visited[nxt_i][nxt_j] > val:
                visited[nxt_i][nxt_j] = val
                q.appendleft((nxt_i, nxt_j, val))

    for di in d_:
        for dj in d_:
            nxt_i, nxt_j = i + di, j + dj
            if not(0 <= nxt_i < h and 0 <= nxt_j < w):
                continue
            elif s[nxt_i][nxt_j] == "
                continue
            elif visited[nxt_i][nxt_j] > val + 1:
                visited[nxt_i][nxt_j] = val + 1
                q.append((nxt_i, nxt_j, val + 1))

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

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

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

d = [[10**20]*w for i in range(h)]

dq = deque([(ch-1,cw-1,0)])
d[ch-1][cw-1] = 0
dx = [0,-1,0,1]
dy = [-1,0,1,0]

while dq:
    nx,ny,nd = dq.popleft()
    if nd < d[nx][ny]:continue
    for delta in range(4):
        tx,ty = nx+dx[delta], ny + dy[delta]
        if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]:
            d[tx][ty] = d[nx][ny]
            dq.appendleft((tx,ty,d[tx][ty]))
    for deltax in range(-2,3):
        for deltay in range(-2,3):
            tx,ty = nx+deltax, ny + deltay
            if 0 <= tx < h and 0 <= ty < w and S[tx][ty] == "." and d[tx][ty] > d[nx][ny]+1:
                d[tx][ty] = d[nx][ny] + 1
                dq.append((tx,ty,d[tx][ty]))

print(d[dh-1][dw-1] if d[dh-1][dw-1] != 10**20 else -1)

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())
s = [input() for _ in range(h)]
vis = [[False] * w for _ in range(h)]
a = [[0] * w for _ in range(h)]
def bfsA(x, y, ai):
    q = deque()
    vis[x][y] = True
    a[x][y] = ai
    q.append((x, y))
    while q:
        u, v = q.popleft()
        for du, dv in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            uu = u + du
            vv = v + dv
            if 0 <= uu < h and 0 <= vv < w and not vis[uu][vv] and s[uu][vv] == '.':
                vis[uu][vv] = True
                a[uu][vv] = ai
                q.append((uu, vv))
c = 0
for x in range(h):
    for y in range(w):
        if vis[x][y] or s[x][y] == '
            continue
        c += 1
        bfsA(x, y, c)
e = [[] for _ in range(c + 3)]
for x in range(h):
    for y in range(w):
        if not vis[x][y] or s[x][y] == '
            continue
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                xx = x + dx
                yy = y + dy
                if 0 <= xx < h and 0 <= yy < w and vis[xx][yy] and s[xx][yy] == '.':
                    e[a[x][y]].append(a[xx][yy])
                    e[a[xx][yy]].append(a[x][y])
vis = [False] * (c + 3)
d = [h * w * 2] * (c + 3)
def bfsB(st):
    q = deque()
    vis[st] = True
    d[st] = 0
    q.append(st)
    while q:
        u = q.popleft()
        for v in e[u]:
            if not vis[v]:
                vis[v] = True
                d[v] = d[u] + 1
                q.append(v)
bfsB(a[ch][cw])
if d[a[dh][dw]] < h * w * 2:
    print(d[a[dh][dw]])
else:
    print(-1)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1
from collections import deque

H,W=map(int,input().split())
sy,sx=map(int1,input().split())
gy,gx=map(int1,input().split())
S=[input() for _ in range(H)]
used=[[False]*W for _ in range(H)]
que=deque([(sy,sx)])
dy,dx=(1,0,-1,0),(0,1,0,-1)
for ans in range(10**6):
    warp=set()
    if not que:
        print(-1)
        exit()
    while que:
        y,x=que.popleft()
        if not used[y][x]:
            used[y][x]=True
            for k in range(4):
                ny,nx=y+dy[k],x+dx[k]
                if 0<=ny<H and 0<=nx<W and not used[ny][nx]:
                    if S[ny][nx]=='.':
                        que.append((ny,nx))
                    else:
                        warp.add((y,x))
    if used[gy][gx]:
        print(ans)
        exit()
    for y,x in warp:
        for i in range(-2,3):
            for j in range(-2,3):
                ny,nx=y+i,x+j
                if not (i==j==0) and 0<=ny<H and 0<=nx<W and not used[ny][nx] and S[ny][nx]=='.':
                    que.append((ny,nx))

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    h,w = map(int,ipt().split())
    ch,cw = map(int,ipt().split())
    dh,dw = map(int,ipt().split())
    board = [input()+"
    board.append("
    board.append("
    t = [[10**18]*w for i in range(h)]
    q = [(ch-1,cw-1)]
    nt = 0
    t[ch-1][cw-1] = 0

    while q:
        wall = set()
        while q:
            qx,qy = q.pop()
            for dx,dy in dir:
                nx = qx+dx
                ny = qy+dy
                if board[nx][ny] == ".":
                    if t[nx][ny] == 10**18:
                        t[nx][ny] = nt
                        q.append((nx,ny))
                else:
                    wall.add((qx,qy))
        nt += 1
        for wx,wy in wall:
            for xs in range(-2,3):
                nx = wx+xs
                for ys in range(-2,3):
                    ny = wy+ys
                    if board[nx][ny] == "." and t[nx][ny] == 10**18:
                        q.append((nx,ny))
                        t[nx][ny] = nt

    if t[dh-1][dw-1] == 10**18:
        print(-1)
    else:
        print(t[dh-1][dw-1])


    return None

if __name__ == '__main__':
    main()

Solution (Python):

H,W = map(int,input().split())

sx,sy = map(int,input().split())
gx,gy = map(int,input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

a = []
for i in range(H):

    tmp = list(input())
    a.append(tmp)

from collections import deque

q = deque([(sx,sy)])
d = [[float("inf")] * W for i in range(H)]
d[sx][sy] = 0

while len(q) > 0:

    nx,ny = q.popleft()
    if a[nx][ny] == "
        continue
    elif nx == gx and ny == gy:
        break

    if nx > 0 and d[nx-1][ny] > d[nx][ny] and a[nx-1][ny] != "
        d[nx-1][ny] = d[nx][ny]
        q.appendleft((nx-1,ny))

    if nx != H-1 and d[nx+1][ny] > d[nx][ny] and a[nx+1][ny] != "
        d[nx+1][ny] = d[nx][ny]
        q.appendleft((nx+1,ny))

    if ny > 0 and d[nx][ny-1] > d[nx][ny] and a[nx][ny-1] != "
        d[nx][ny-1] = d[nx][ny]
        q.appendleft((nx,ny-1))

    if ny != W-1 and d[nx][ny+1] > d[nx][ny] and a[nx][ny+1] != "
        d[nx][ny+1] = d[nx][ny]
        q.appendleft((nx,ny+1))

    for xx in range(-2,3):
        for yy in range(-2,3):

            nex = nx + xx
            ney = ny + yy
            if 0 <= nex < H and 0 <= ney < W and d[nex][ney] > d[nx][ny] + 1:
                d[nex][ney] = d[nx][ny] + 1
                q.append((nex,ney))

if d[gx][gy] == float("inf"):
    print (-1)
else:
    print (d[gx][gy])

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    gh, gw = map(int, input().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    grid = []
    for _ in range(H):
        grid.append(input().rstrip('\n'))

    que = deque()
    que.append(sh * W + sw)
    seen = [[-1] * W for _ in range(H)]
    seen[sh][sw] = 0
    seen2 = [[0] * W for _ in range(H)]
    d = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    while que:
        hw = que.popleft()
        h, w = divmod(hw, W)
        if seen2[h][w]:
            continue
        seen2[h][w] = 1
        
        for dh, dw in d:
            h_new, w_new = h+dh, w+dw
            if 0 <= h_new < H and 0 <= w_new < W:
                if grid[h_new][w_new] == ".":
                    if seen[h_new][w_new] == -1 or seen[h_new][w_new] > seen[h][w]:
                        que.appendleft(h_new * W + w_new)
                        seen[h_new][w_new] = seen[h][w]
        
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                h_new, w_new = h + dh, w + dw
                if 0 <= h_new < H and 0 <= w_new < W:
                    if grid[h_new][w_new] == ".":
                        if seen[h_new][w_new] == -1:
                            que.append(h_new * W + w_new)
                            seen[h_new][w_new] = seen[h][w] + 1
    print(seen[gh][gw])
    


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sy -= 1
sx -= 1
gy -= 1
gx -= 1
a = [list(input())[: -1] for _ in range(H)]
Q = dq([sy * W + sx])
inf = H * W + 1
dp = [inf] * (H * W)
dp[sy * W + sx] = 0
d = [-1, 0, 1, 0]
while len(Q):
  t = Q.popleft()
  y = t // W
  x = t % W
  for k in range(4):
    u = y + d[k]
    v = x + d[-1 - k]
    if u in range(H) and (v in range(W)):
      if a[u][v] == "
      if dp[u * W + v] > dp[t]:
        dp[u * W + v] = dp[t]
        Q.appendleft(u * W + v)

  for i in range(5):
    for j in range(5):
      u = y + i - 2
      v = x + j - 2
      if u in range(H) and (v in range(W)):
        if a[u][v] == "
        if dp[u * W + v] > dp[t] + 1:
          dp[u * W + v] = dp[t] + 1
          Q.append(u * W + v)
if dp[gy * W + gx] != inf: print(dp[gy * W + gx])
else: print(-1)

Solution (Python):
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 = [input() for _ in range(h)]

import heapq
inf = 10 ** 7
d = [[inf]*w for _ in range(h)]
 
def bfs():
    que = [(0, ch, cw)]
    d[ch][cw] = 0
    heapq.heapify(que)
    
    while len(que) > 0:
        dist, qx, qy = heapq.heappop(que)
        if dist > d[qx][qy]:
            continue
        if qx == dh and qy == dw:
            return d[dh][dw]
        for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            px, py = qx+dx, qy+dy
            if 0 <= px < h and 0 <= py < w and s[px][py]=='.' and d[px][py] > d[qx][qy]:
                d[px][py] = d[qx][qy]
                heapq.heappush(que, (d[px][py], px, py))
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                px, py = qx+dx, qy+dy
                if 0 <= px < h and 0 <= py < w and s[px][py]=='.' and d[px][py] > d[qx][qy] + 1:
                    d[px][py] = d[qx][qy] + 1
                    heapq.heappush(que, (d[px][py], px, py))
    
    return -1

ans = bfs()
print(ans)

Solution (Python):
from collections import deque

INF = 10 ** 9

H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())

si += 1
sj += 1
gi += 1
gj += 1

sentinel = [-1] * (W + 4)
MAP = [sentinel, sentinel]
for _ in range(H):
    MAP.append([-1, -1] + [-1 if c == '
MAP.append(sentinel)
MAP.append(sentinel)



MAP[si][sj] = 0
q = deque([(si, sj)])
while q:
    i, j = q.popleft()
    if i == gi and j == gj:
        break
    for di, dj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if MAP[i+di][j+dj] > MAP[i][j]:
            MAP[i+di][j+dj] = MAP[i][j]
            q.appendleft((i+di, j+dj))

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if MAP[i+di][j+dj] > MAP[i][j] + 1:
                MAP[i+di][j+dj] = MAP[i][j] + 1
                q.append((i+di, j+dj))



ans = MAP[gi][gj]
if ans == INF:
    print(-1)
else:
    print(ans)

Solution (Python):
from collections import deque
INF = 10 ** 10
dxdy = ((0, 1), (0, -1), (1, 0), (-1, 0))
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = ['
d = [[INF] * (w + 1) for _ in range(h + 1)]
d[ch][cw] = 0
q = deque([(ch, cw)])
while q:
    y, x = q.pop()
    for dx, dy in dxdy:
        if s[y + dy][x + dx] == '.' and d[y + dy][x + dx] > d[y][x]:
            d[y + dy][x + dx] = d[y][x]
            q.append((y + dy, x + dx))
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == j == 0:
                continue
            elif 1 <= y + i <= h and 1 <= x + j <= w and s[y + i][x + j] == '.' and d[y + i][x + j] > d[y][x] + 1:
                d[y + i][x + j] = d[y][x] + 1
                q.appendleft((y + i, x + j))
ans = d[dh][dw]
if ans == INF:
    print(-1)
else:
    print(ans)

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

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

h, w = na()
ch, cw = na()
dh, dw = na()

b = []
for i in range(h):
    b.append(ns())

q = deque()
q.append((ch-1, cw-1))
ds = [9999999999] * (h*w)
ds[(ch-1)*w+cw-1] = 0

di = ((1, 0), (0, 1), (-1, 0), (0, -1))
while q:
    r, c = q.popleft()
    for k in di:
        nr, nc = r + k[0], c + k[1]
        if 0 <= nr < h and 0 <= nc < w and b[nr][nc] == "." and ds[nr*w+nc] > ds[r*w+c]:
            ds[nr*w+nc] = ds[r*w+c]
            q.appendleft((nr, nc))
    for nr in range(r-2, r+3):
        for nc in range(c-2, c+3):
            if 0 <= nr < h and 0 <= nc < w and b[nr][nc] == "." and ds[nr * w + nc] > ds[r * w + c] + 1:
                ds[nr * w + nc] = ds[r * w + c] + 1
                q.append((nr, nc))

if ds[(dh-1)*w+dw-1] > 9999999:
    print(-1)
else:
    print(ds[(dh-1)*w+dw-1])

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    cy,cx = LI()
    gy,gx = LI()
    s = [input() for _ in range(h)]
    cy -= 1
    cx -= 1
    gy -= 1
    gx -= 1
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    bfs = [[float("inf")]*w for i in range(h)]
    bfs[cy][cx] = 0
    q = deque([(cy,cx)])
    while q:
        y,x = q.popleft()
        b = bfs[y][x]
        if (y,x) == (gy,gx):
            print(b)
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "
                bfs[ny][nx] = b
                q.appendleft((ny,nx))
        nb = b+1
        for dy in range(-2,3):
            for dx in range(-2,3):
                ny,nx = y+dy,x+dx
                if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "
                    bfs[ny][nx] = nb
                    q.append((ny,nx))
    print(-1)
    return


if __name__ == "__main__":
    solve()