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

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 = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
            continue
        if S[nh][nw] == '
            continue
        if seen[nh][nw] <= seen[th][tw]:
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1:
                continue
            if S[nh][nw] == '
                continue
            if seen[nh][nw] <= seen[th][tw] + 1:
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

Solution (Python):
from collections import deque

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 = [input() for _ in range(H)]

dh = [-1, 0, 0, 1]
dw = [0, 1, -1, 0]

INF = pow(10, 10)
seen = [[INF] * W for _ in range(H)]
seen[Ch][Cw] = 0
q = deque()
q.append([Ch, Cw])

while q:
    th, tw = q.pop()
    for i in range(4):
        nh = th + dh[i]
        nw = tw + dw[i]
        if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '
            continue
        seen[nh][nw] = seen[th][tw]
        q.append([nh, nw])
    for dh2 in range(-2, 3):
        for dw2 in range(-2, 3):
            if dh2 == 0 and dw2 == 0:
                continue
            nh = th + dh2
            nw = tw + dw2
            if nh < 0 or nh > H - 1 or nw < 0 or nw > W - 1 or S[nh][nw] == '
                continue
            seen[nh][nw] = seen[th][tw] + 1
            q.appendleft([nh, nw])

if seen[Dh][Dw] is INF:
    print(-1)
else:
    print(seen[Dh][Dw])

Solution (Python):
INF = 10**9
from heapq import heappop,heappush
H,W = (int(i) for i in input().split())
Ch,Cw = (int(i)-1 for i in input().split())
Dh,Dw = (int(i)-1 for i in input().split())
S = [input() for i in range(H)]

dist = [[INF]*W for _ in range(H)]
dist[Ch][Cw]= 0
que = [(0,Ch*W+Cw)]
while(que):
    u_dist,u = heappop(que)
    uh,uw = u//W,u%W
    
    
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh = uh + dh
            nw = uw + dw
            if nh<0 or H <= nh or nw < 0 or W <= nw:
                continue
            if S[nh][nw]=="
                continue
            cost = 0 if abs(dh)+abs(dw)<=1 else 1
            if dist[nh][nw] > dist[uh][uw] + cost:
                dist[nh][nw] = dist[uh][uw] + cost
                heappush(que,(dist[nh][nw],nh*W+nw))
if dist[Dh][Dw] == INF:
    print(-1)
else:
    print(dist[Dh][Dw])

Solution (Python):
INF = 10**9
from heapq import heappop,heappush
H,W = (int(i) for i in input().split())
Ch,Cw = (int(i)-1 for i in input().split())
Dh,Dw = (int(i)-1 for i in input().split())
S = [input() for i in range(H)]

dist = [[INF]*W for _ in range(H)]
dist[Ch][Cw]= 0
que = [(0,Ch*W+Cw)]
while(que):
    u_dist,u = heappop(que)
    uh,uw = u//W,u%W
    if dist[uh][uw] < u_dist:
        continue
    for dh in range(-2,3):
        for dw in range(-2,3):
            nh = uh + dh
            nw = uw + dw
            if nh<0 or H <= nh or nw < 0 or W <= nw:
                continue
            if S[nh][nw]=="
                continue
            cost = 0 if abs(dh)+abs(dw)<=1 else 1
            if dist[nh][nw] > dist[uh][uw] + cost:
                dist[nh][nw] = dist[uh][uw] + cost
                heappush(que,(dist[nh][nw],nh*W+nw))
if dist[Dh][Dw] == INF:
    print(-1)
else:
    print(dist[Dh][Dw])

Solution (Python):
h,w=map(int,input().split())
from collections import *
l=[(0,1),(0,-1),(1,0),(-1,0)]
dp=[[float("inf")]*w for i in range(h)]
f=[[False]*w for i in range (h)]
ch,cw=map(int,input().split())
sx,sy=ch-1,cw-1
dh,dw=map(int,input().split())
gx,gy=dh-1,dw-1
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]==".":
            f[i][j]=True
q=deque()
q.append((sx,sy))
dp[sx][sy]=0
while q:
    x,y=q.popleft()
    for a,b in l:
        nx,ny=x+a,y+b
        if 0<=nx<h and 0<=ny<w:
            if f[nx][ny]==True and dp[nx][ny]>dp[x][y]:
                dp[nx][ny]=dp[x][y]
                q.appendleft((nx,ny))
    for nx in range(x-2,x+3):
        for ny in range(y-2,y+3):
            if 0<=nx<h and 0<=ny<w:
                if f[nx][ny]==True and dp[nx][ny]>dp[x][y]+1:
                    dp[nx][ny]=dp[x][y]+1
                    q.append((nx,ny))
if dp[gx][gy]==float("inf"):
    print(-1)
else:
    print(dp[gx][gy])

Solution (Python):

def main():
    import sys
    imput = sys.stdin.readline
    
    
    
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = [input() for _ in range(h)]

    
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    trans_a = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    trans_b = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + trans_a]

    q = deque([])
    q.append((c_h-1, c_w-1, 0))
    dp[c_h-1][c_w-1] = 0

    while q:
        x, y, t = q.popleft()

        for dx, dy in trans_a:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                q.appendleft((nx, ny, t))
                dp[nx][ny] = t

        for dx, dy in trans_b:
            nx, ny = x + dx, y + dy
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                q.append((nx, ny, t+1))
                dp[nx][ny] = t + 1

    answer = dp[d_h-1][d_w-1]

    
    if answer == INF:
        print(-1)
    else:
        print(answer)

    
if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush,heappop
from collections import deque
h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
g=[list(input()) for _ in range(h)]
v=[[0 for j in range(w)] for i in range(h)]
v2=[[0 for j in range(w)] for i in range(h)]
q=deque([])
q.append([0,sx+h*sy])
while q:
    c,xy=q.popleft()
    x=xy%h
    y=xy//h
    if x==gx and y==gy:
        print(c)
        exit()
    if v[x][y]==1:
        continue
    v[x][y]=1
    for a in range(-2,3):
        for b in range(-2,3):
            if a==b==0:
                continue
            if a*b==0 and abs(a+b)==1:
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                    q.appendleft([c,nx+h*ny])
                continue
            nx=x+a
            ny=y+b
            if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                q.append([c+1,nx+h*ny])
                v2[nx][ny]=1
print(-1)

Solution (Python):
from heapq import heappush,heappop
from collections import deque
h,w=map(int,input().split())
sx,sy=map(int,input().split())
sx-=1
sy-=1
gx,gy=map(int,input().split())
gx-=1
gy-=1
g=[list(input()) for _ in range(h)]
v=[[0 for j in range(w)] for i in range(h)]
v2=[[0 for j in range(w)] for i in range(h)]
q=deque([])
q.append([0,sx,sy])
while q:
    c,x,y=q.popleft()
    if x==gx and y==gy:
        print(c)
        exit()
    if v[x][y]==1:
        continue
    v[x][y]=1
    for a in range(-2,3):
        for b in range(-2,3):
            if a==b==0:
                continue
            if a*b==0 and abs(a+b)==1:
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                    q.appendleft([c,nx,ny])
                continue
            nx=x+a
            ny=y+b
            if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0 and v2[nx][ny]==0:
                q.append([c+1,nx,ny])
                v2[nx][ny]=1
print(-1)

Solution (Python):

from functools import reduce
from queue import Queue
from collections import deque
H, W = list(map(int, input().split(" ")))
current_h, current_w = list(map(int, input().split(" ")))
current_h -= 1
current_w -= 1
goal_h, goal_w = list(map(int, input().split(" ")))
goal_h -= 1
goal_w -= 1

table = [list(input()) for _ in range(H)]

class ZeroOneBFS:

    def __init__(self, table):
        self.table = table
        self.cost_table = []
        for _ in range(H):
            self.cost_table.append([-1 for _ in range(W)])

    def delta(self, h, w):
        res = [(h+1, w),
               (h, w-1), (h, w+1),
               (h-1, w)]
        return res

    def warp(self, h, w):
        res = []
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                if dh == 0 and dw == 0:
                    pass
                else:
                    res.append((h+dh, w+dw))
        return res

    def bfs(self, start_h, start_w):
        dq = deque()
        dq.appendleft((start_h, start_w, 0))
        while dq:
            now_h, now_w, now_c = dq.pop()
            if self.table[now_h][now_w] == "
                pass
            else:
                self.cost_table[now_h][now_w] = now_c
                for h, w in self.delta(now_h, now_w):
                    if 0 <= h < H and 0 <= w < W and self.table[h][w] != "
                        dq.append((h, w, now_c))
                for h, w in self.warp(now_h, now_w):
                    if 0 <= h < H and 0 <= w < W and self.table[h][w] != "
                        dq.appendleft((h, w, now_c+1))
        return self.cost_table[goal_h][goal_w]


bfs = ZeroOneBFS(table)
print(bfs.bfs(current_h, current_w))

Solution (Python):
from heapq import heappush,heappop,heapify
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found

mo=10**9+7
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
import sys
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

inf=1<<20
def dijkstra(edge,st):
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(0,st)]
    heapify(q)
    v=[False]*n
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d


show_flg=False
show_flg=True

ans=0

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

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h


nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nbw=[2,2*w+1,2*w+2,w+1,w+2,+2*w,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
nb=[1,w]
d=[-1]*n
g=[[]for i in range(n)]
for i in range(n):
    if m[i]==1:
      continue
    for di in nbw:
        nx=i+di
        if 0<=nx<n and m[nx]!=1:
            g[i]+=(nx,1),
            g[nx]+=(i,1),
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1:
            g[i]+=(nx,0),
            g[nx]+=(i,0),
            
d=dijkstra(g,sh*w+sw)
ans=d[gh*w+gw]
if ans==inf:
    ans=-1
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found

mo=10**9+7
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
import sys
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

inf=1<<20
def dijkstra(edge,st):
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(0,st)]
    heapify(q)
    v=[False]*n
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for x in edge[cur]:
            dst,dist=x>>1,x%2
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d


show_flg=False
show_flg=True

ans=0

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

w+=2
m=[1]*w
for i in range(h):
    s=input()
    m+=[1]+[i=='
m+=[1]*w
h+=2
n=h*w
v=[-1]*w*h


nbw=[-2*w+1,-2*w+2,-w+1,-w+2,2,2*w+1,2*w+2,w+1,w+2,+2*w,-2*w,-2*w-1,-2*w-2,-w-1,-w-2,-2,2*w-1,2*w-2,w-1,w-2]
nbw=[2,2*w+1,2*w+2,w+1,w+2,+2*w,2*w-1,2*w-2,w-1,w-2]
nb=[1,-1,w,-w]
nb=[1,w]
d=[-1]*n
g=[[]for i in range(n)]
for i in range(n):
    if m[i]==1:
      continue
    for di in nbw:
        nx=i+di
        if 0<=nx<n and m[nx]!=1:
            g[i]+=(nx*2+1),
            g[nx]+=(i*2+1),
    for di in nb:
        nx=i+di
        if 0<=nx<n and m[nx]!=1:
            g[i]+=(nx*2),
            g[nx]+=(i*2),
            
d=dijkstra(g,sh*w+sw)
ans=d[gh*w+gw]
if ans==inf:
    ans=-1
print(ans)

Solution (Python):
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
s = sh*3000+sw
g = gh*3000+gw

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
d = []
heapify(d)
heappush(d,s)
ans = float('inf')
while len(d)>0:
  a = heappop(d)
  cnt,a1 = divmod(a,10**7)
  h,w = divmod(a1,3000)
  if cnt>=ans:
    break
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if (h1,w1)==(gh,gw):
      ans = cnt
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        heappush(d,cnt*(10**7)+h1*3000+w1)
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if (h2,w2)==(gh,gw):
      ans = cnt+1
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        heappush(d,(cnt+1)*(10**7)+h2*3000+w2)
ans = ans if ans<float('inf') else -1
print(ans)

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

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
d = []
heapify(d)
heappush(d,(0,sh,sw))
ans = float('inf')
while len(d)>0:
  cnt,h,w = heappop(d)
  if cnt>=ans:
    break
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if (h1,w1)==(gh,gw):
      ans = cnt
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        heappush(d,(cnt,h1,w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if (h2,w2)==(gh,gw):
      ans = cnt+1
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        heappush(d,(cnt+1,h2,w2))
ans = ans if ans<float('inf') else -1
print(ans)

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

S = [0]*(H+4)
S[0] = '*'*(W+4)
S[1] = '*'*(W+4)
S[-2] = '*'*(W+4)
S[-1] = '*'*(W+4)
for h in range(2,H+2):
  S[h] = '**' + input() + '**'

visited = [[float('inf')]*(W+4) for _ in range(H+4)]
dh1 = [0,1,0,-1]
dw1 = [1,0,-1,0]
dh2 = [2,2,2,2,2,1,1,1,1,0,0,-1,-1,-1,-1,-2,-2,-2,-2,-2]
dw2 = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]

from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
d = []
heapify(d)
heappush(d,(0,sh,sw))
ans = float('inf')
while len(d)>0:
  cnt,h,w = heappop(d)
  if cnt>=ans:
    break
  visited[h][w] = cnt
  for i in range(4):
    h1 = h+dh1[i]
    w1 = w+dw1[i]
    if (h1,w1)==(gh,gw):
      ans = min(ans,cnt)
    if S[h1][w1]=='.':
      if visited[h1][w1]>cnt:
        visited[h1][w1]=cnt
        heappush(d,(cnt,h1,w1))
  for i in range(20):
    h2 = h+dh2[i]
    w2 = w+dw2[i]
    if (h2,w2)==(gh,gw):
      ans = min(ans,cnt+1)
    if S[h2][w2]=='.':
      if visited[h2][w2]>cnt+1:
        visited[h2][w2]=cnt+1
        heappush(d,(cnt+1,h2,w2))
ans = ans if ans<float('inf') else -1
print(ans)

Solution (Python):
from collections import deque
INF=1001001001
dy=[0,1,0,-1]
dx=[1,0,-1,0]
my=[-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
mx=[2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]
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=[list(input()) for i in range(h)]
dist=[[INF for i in range(w)] for j in range(h)]
dist[ch][cw]=0
d=deque([])
d.append([ch,cw])

while d:
  nowh,noww=d.popleft()
  for i in range(4):
    th=nowh+dy[i]
    tw=noww+dx[i]
    if 0<=th<=h-1 and 0<=tw<=w-1 and dist[th][tw]>dist[nowh][noww] and s[th][tw]==".":
      d.appendleft([th,tw])
      dist[th][tw]=dist[nowh][noww]
  for i in range(20):
    th=nowh+my[i]
    tw=noww+mx[i]
    if 0<=th<=h-1 and 0<=tw<=w-1 and dist[th][tw]>dist[nowh][noww]+1 and s[th][tw]==".":
      d.append([th,tw])
      dist[th][tw]=dist[nowh][noww]+1

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

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())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  


walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Solution (Python):
from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) 
    visited[sy][sx]=0 
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="
                continue
            if visited[my][mx]>cnt:
                queue.appendleft([my,mx])
                visited[my][mx]=cnt 
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()

Solution (Python):
import sys
readline = sys.stdin.buffer.readline

H, W = list(map(int, readline().split()))
CH, CW = list(map(int, readline().split()))
DH, DW = list(map(int, readline().split()))
S = []
for _ in range(H):
    S.append(list(input()))


CH -= 1
CW -= 1
DH -= 1
DW -= 1

from collections import deque
seen = set()
queue = deque([(0, CH, CW)])
offsets = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while queue:
    move, row, col = queue.popleft()

    

    if (row, col) in seen:
        continue

    if row == DH and col == DW:
        print(move)
        sys.exit(0)

    seen.add((row, col))

    for r_offset, c_offset in offsets:
        new_row = row + r_offset
        new_col = col + c_offset
        if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
            queue.appendleft((move, new_row, new_col))


    for i in range(-2, 3):
        for j in range(-2, 3):
            new_row = row + i
            new_col = col + j

            if 0 <= new_row < H and 0 <= new_col < W and S[new_row][new_col] == '.' and (new_row, new_col) not in seen:
                queue.append((move+1, new_row, new_col))

print(-1)

Solution (Python):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    move = product(range(-2, 3), repeat=2)
    near = [(dx, dy, (abs(dx) + abs(dy) >= 2)) for dx, dy in move]

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy, cnt in near:
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Solution (Python):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    near = list(product(range(-2, 3), repeat=2))

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy in near:
            cnt = (abs(dx) + abs(dy) >= 2)
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Solution (Python):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    near = list(product(range(-2, 3), repeat=2))

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy in near:
            cnt = (abs(dx) + abs(dy) >= 2)
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    else:
        return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Solution (Python):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])
    near = product(range(-2, 3), repeat=2)

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for dx, dy in product(range(-2, 3), repeat=2):
            cnt = (abs(dx) + abs(dy) >= 2)
            i, j = x + dx, y + dy
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    else:
        return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Solution (Python):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y, dist[y][x])])

    while len(que) > 0:
        x, y, d = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for i, j in product(range(-2, 3), repeat=2):
            cnt = (abs(i) + abs(j) >= 2)
            i, j = x + i, y + j
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > d + cnt and s[j][i] == '.'):
                dist[j][i] = d + cnt
                if cnt == 0:
                    que.appendleft((i, j, d + cnt))
                elif cnt == 1:
                    que.append((i, j, d+cnt))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))

Solution (Python):
from collections import deque
from itertools import product


def bfs(x, y):
    dist = [[10 ** 9] * w for _ in range(h)]
    dist[y][x] = 0
    que = deque([(x, y)])

    while len(que) > 0:
        x, y = que.popleft()
        if (x, y) == (Dw - 1, Dh - 1):
            return dist[y][x]

        for i, j in product(range(-2, 3), repeat=2):
            cnt = (abs(i) + abs(j) >= 2)
            i, j = x + i, y + j
            if (0 <= i < w and 0 <= j < h and
                    dist[j][i] > dist[y][x] + cnt and s[j][i] == '.'):
                dist[j][i] = dist[y][x] + cnt
                if cnt == 0:
                    que.appendleft((i, j))
                elif cnt == 1:
                    que.append((i, j))
    return -1


h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
s = [input() for _ in range(h)]

print(bfs(Cw - 1, Ch - 1))