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())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="
 
genzai=deque()
wapu=deque()
genzai.append([c_h-1,c_w-1])
wapu.append([c_h-1,c_w-1])
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append([gyou,retu])
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
                wapu.append([gyou+i,retu])
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
                wapu.append([gyou,retu+i])

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append([gyou+i,retu+j])

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.popleft()
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.popleft()
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])

Solution (Python):

def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        
        
        
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()

Solution (Python):
from collections import deque

h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="
 
genzai=deque()
wapu=deque()
genzai.append((c_h-1,c_w-1))
wapu.append((c_h-1,c_w-1))
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append((gyou,retu))
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append((gyou+i,retu))
                wapu.append((gyou+i,retu))
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append((gyou,retu+i))
                wapu.append((gyou,retu+i))

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append((gyou+i,retu+j))

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.popleft()
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.popleft()
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])

Solution (Python):
def resolve():
  H, W = map(int, input().split(" "))
  Ch, Cw = map(int, input().split(" "))
  wiz_pos = [Ch-1, Cw-1]
  Dh, Dw = map(int, input().split(" "))
  goal_pos = [Dh-1, Dw-1]

  cell_or_wall = []
  count = 0
  for _ in range(H):
    cell_or_wall.append([x == "." for x in list(input())])

  cost_of_cells = [[None] * W for i in range(H)]
  next_cells = set([tuple(wiz_pos)])
  cells_of_wall_side = []

  cost = 0
  
  while len(next_cells) != 0:
    temp_next_cells = set()
    for target_cell in next_cells:
      cost_of_cells[target_cell[0]][target_cell[1]] = cost
      
      adjacents = [
        [target_cell[0] - 1, target_cell[1]],
        [target_cell[0] + 1, target_cell[1]],
        [target_cell[0], target_cell[1] - 1],
        [target_cell[0], target_cell[1] + 1]
      ]

      for adjacent in adjacents:
        h = adjacent[0]
        w = adjacent[1]
        if h < 0 or h >= H:
          continue
        if w < 0 or w >= W:
          continue

        
        if not cell_or_wall[h][w]:
          
          if len(cells_of_wall_side) == 0:
            cells_of_wall_side.append(target_cell)
          elif cells_of_wall_side[-1][0] != target_cell[0] or cells_of_wall_side[-1][1] != target_cell[1]:
            cells_of_wall_side.append(target_cell)
          
          
        elif cost_of_cells[h][w] is None:
          temp_next_cells.add((h, w))
    
    
    next_cells = temp_next_cells

    if len(next_cells) != 0:
      continue

    
    
    for target_cell in cells_of_wall_side:
      
      for h in range(target_cell[0] - 2, target_cell[0] + 3):
        if h < 0 or h >= H:
          continue
        for w in range(target_cell[1] - 2, target_cell[1] + 3):
          if w < 0 or w >= W:
            continue
          if cell_or_wall[h][w] and cost_of_cells[h][w] is None:
            next_cells.add((h, w))
    cells_of_wall_side = []
    cost += 1
  
  
  
  
  
  
  
  
  

  if cost_of_cells[goal_pos[0]][goal_pos[1]] is None:
    print(-1)
  else:
    print(cost_of_cells[goal_pos[0]][goal_pos[1]])

if __name__ == "__main__":
  resolve()

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

lim = 10**6

S = ['
S.append('
for k in range(H):
  S.append('
S.append('
S.append('

foo = [[-1 for _ in range(W+4)] for _ in range(H+4)]
rev = [[-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] == '.':
      foo[k][j] = lim
      rev[k][j] = lim



foo[Ch][Cw] = 0
rev[Dh][Dw] = 0
jump = [(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)]
mv = [(1,0),(-1,0),(0,1),(0,-1)]
now = deque([])
new = deque([(Ch, Cw)])
while len(new) > 0:
  item = new.pop()
  now.append(item)
  x = item[0]
  y = item[1]
  for m in mv:
    mx = x + m[0]
    my = y + m[1]
    if rev[mx][my] == 0:
      print(0)
      exit()
    else:
      if foo[mx][my] == lim:
        foo[mx][my] = 0
        new.append((mx, my))

now_rev = deque([])
new_rev = deque([(Dh,Dw)])
while len(new_rev) > 0:
  item = new_rev.pop()
  now_rev.append(item)
  x = item[0]
  y = item[1]
  for m in mv:
    mx = x + m[0]
    my = y + m[1]
    if rev[mx][my] == lim:
      rev[mx][my] = 0
      new_rev.append((mx, my))


start = 0
while True:
  if len(now) == 0:
    print(-1)
    exit() 
  start += 1
  while len(now) > 0:
    item = now.pop()
    x = item[0]
    y = item[1]
    for j in jump:
      jx = x + j[0]
      jy = y + j[1]
      if 0 <= rev[jx][jy] < lim:
        print(foo[x][y]+rev[jx][jy]+1)
        exit()
      else:
        if foo[jx][jy] > start:
          foo[jx][jy] = start
          new.append((jx,jy))
  while len(new) > 0:
    item = new.pop()
    now.append(item)
    x = item[0]
    y = item[1]
    for m in mv:
      mx = x + m[0]
      my = y + m[1]
      if 0 <= rev[mx][my] < lim:
        print(foo[x][y] + rev[mx][my])
        exit()
      else:
        if foo[mx][my] == lim:
          foo[mx][my] = start
          new.append((mx, my))

  if len(now_rev) == 0:
    print(-1)
    exit() 
  while len(now_rev) > 0:
    item = now_rev.pop()
    x = item[0]
    y = item[1]
    for j in jump:
      jx = x + j[0]
      jy = y + j[1]
      if 0 <= foo[jx][jy] < lim:
        print(rev[x][y]+foo[jx][jy]+1)
        exit()
      else:
        if rev[jx][jy] > start:
          rev[jx][jy] = start
          new_rev.append((jx,jy))

  while len(new_rev) > 0:
    item = new_rev.pop()
    now_rev.append(item)
    x = item[0]
    y = item[1]
    for m in mv:
      mx = x + m[0]
      my = y + m[1]
      if 0 <= foo[mx][my] < lim:
        print(rev[x][y] + foo[mx][my])
        exit()
      else:
        if rev[mx][my] == lim:
          rev[mx][my] = start
          new_rev.append((mx, my))

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array





sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    H, W = il()
    Ch, Cw = il()
    Dh, Dw = il()
    grid = [iss() for _ in range(H)]
    visited = [[INF] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    que = collections.deque()

    que.appendleft((Ch - 1, Cw - 1, 0))
    visited[Ch - 1][Cw - 1] = 0
    while que:
        h, w, c = que.popleft()
        for mh, mw in move:  
            ch, cw = h + mh, w + mw
            if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '
                visited[ch][cw] = c
                que.appendleft((ch, cw, c))
        for wh in range(-2, 3):  
            for ww in range(-2, 3):
                ch, cw = h + wh, w + ww
                if 0 <= ch < H and 0 <= cw < W and grid[ch][cw] != '
                    visited[ch][cw] = c + 1
                    que.append((ch, cw, c + 1))

    ret = visited[Dh - 1][Dw - 1]
    print(-1 if ret == INF else ret)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

h,w = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
S = [list(input()) for _ in range(h)]

seen = [[0]*w for _ in range(h)]
cost = [[-1]*w for _ in range(h)]
cost[C[0]-1][C[1]-1]=0
cost_base = 0
for i in range(h):
    for j in range(w):
        if S[i][j]=='
            cost[i][j]=-2

ok = True

q=deque()
q.append(C)
                
while len(q)>0:
    
    now = q.popleft()
    if seen[now[0]-1][now[1]-1] == 1:
        continue
    costnow = cost[now[0]-1][now[1]-1]
    seen[now[0]-1][now[1]-1] = 1

    for i in range(-1,2,2):
        if now[0]+i<1 or now[0]+i>h:
            continue
        if cost[now[0]+i-1][now[1]-1]==-1 or cost[now[0]+i-1][now[1]-1]>costnow:
            cost[now[0]+i-1][now[1]-1]=costnow
            q.appendleft([now[0]+i,now[1]])
    for i in range(-1,2,2):
        if now[1]+i<1 or now[1]+i>w:
            continue
        if cost[now[0]-1][now[1]+i-1]==-1 or cost[now[0]-1][now[1]+i-1]>costnow:
            cost[now[0]-1][now[1]+i-1]=costnow
            q.appendleft([now[0],now[1]+i])

    
    for i in range(-2,3):
        for j in range(-2,3):
            if now[0]+i<1 or now[0]+i>h:
                continue
            if now[1]+j<1 or now[1]+j>w:
                continue

            if cost[now[0]+i-1][now[1]+j-1]==-1:
                cost[now[0]+i-1][now[1]+j-1]=costnow+1
                q.append([now[0]+i,now[1]+j])

print(cost[D[0]-1][D[1]-1])

Solution (Python):
from collections import deque

H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

S = [None]*W
S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

wx = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]

def distance(i,j):
    not_visited = [[-1]*W for i in range(H)]
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j))

    stack2 = deque()
    stack2.append((i,j))

    while stack2 != deque([]):

        while stack != deque([]):
            y,x = stack.popleft()
            for i in range(4):
                if 0<= x+dx[i] <W and 0<= y+dy[i] <H and S[y+dy[i]][x+dx[i]] != "
                    not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x]
                    stack.append((y+dy[i],x+dx[i]))
                    stack2.append((y+dy[i],x+dx[i]))

        y,x = stack2.popleft()
        for i in range(25):
            if 0<= x+wx[i] <W and 0<= y+wy[i] <H and S[y+wy[i]][x+wx[i]] != "
                not_visited[y+wy[i]][x+wx[i]] =  not_visited[y][x] + 1
                stack.append((y+wy[i],x+wx[i]))
                stack2.append((y+wy[i],x+wx[i]))
        
        """
        for i in range(H):
            print(not_visited[i])
        print()
        """
    return not_visited[gy-1][gx-1]
    
print(distance(sy-1,sx-1))

Solution (Python):
def main():
    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 = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                    if m[y + s][x + t] == '
                        edge.append((y, x))
                        continue
                    q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if vis[y + s][x + t]:
                        continue
                    if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                        if m[y + s][x + t] == '
                            continue
                        nx += walk(y + s, x + t)
                        if vis[dh][dw]:
                            return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-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)
    ]
    S[CH-1][CW-1] = 0
    q = deque()
    q.appendleft((CH-1, CW-1))
    while q:
        
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                q.appendleft((ny, nx))
                S[ny][nx] = d0
        
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0+1):
                q.append((ny, nx))
                S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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(map(str, input())) for _ in range(H)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])

Solution (Python):
import zlib,base64
exec(zlib.decompress(base64.b85decode("c-oy(%Wi`(5WMphE>(q%O(Z9$L~-tXgM}&zCUFGDyh`}{E(F}F>Zu2Im+^RJY`JLb3U$MWZR<>R9nzJp+dlN

Solution (Python):
def main():
    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 = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                    continue
                if m[y + s][x + t] == '
                    edge.append((y, x))
                    continue
                q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if not 0 <= y + s <= h - 1 or not 0 <= x + t <= w - 1:
                        continue
                    if vis[y + s][x + t]:
                        continue
                    if m[y + s][x + t] == '
                        continue
                    nx += walk(y + s, x + t)
                    if vis[dh][dw]:
                        return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

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


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-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)
    ]
    q = deque()
    q.appendleft((CH-1, CW-1, 0))
    while q:
        
        y0, x0, d0 = q.popleft()
        if 0 <= S[y0][x0] < d0:
            continue
        S[y0][x0] = d0
        
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.appendleft((ny, nx, d0))
        
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.append((ny, nx, d0+1))
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Solution (Python):

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

from collections import deque

h,w = ip()
ax,ay = ip()
bx,by = ip()
ax -= 1; ay -= 1; bx -= 1; by -= 1
mat = [input().strip() for i in range(h)]
dist = [[float('inf')]*w for i in range(h)]
dist[ax][ay] = 0
dx,dy = [1,-1,0,0],[0,0,-1,1]
dq = deque()
dq.append([ax,ay])
while dq:
    cx,cy = dq.popleft()
    for i in range(4):
        nx,ny = cx+dx[i], cy+dy[i]
        if 0 <= nx < h and 0 <= ny < w and mat[nx][ny] == '.':
            if dist[nx][ny] > dist[cx][cy]:
                dist[nx][ny] = dist[cx][cy]
                dq.appendleft([nx,ny])
    for i in range(cx-2,cx+3):
        for j in range(cy-2,cy+3):
            if 0 <= i < h and 0 <= j < w and mat[i][j] == '.':
                if dist[i][j] > dist[cx][cy]+1:
                    dist[i][j] = dist[cx][cy]+1
                    dq.append([i,j])
if dist[bx][by] == float('inf'): dist[bx][by] = -1
print(dist[bx][by])

Solution (Python):
from collections import*
I=9**9
(h,w),(s,t),(f,g)=eval('map(int,input().split()),'*3)
m=[input()for _ in range(h)]
d=[[I]*w for _ in range(h)]
q=deque([(s-1,t-1,1)])
while q:
  y,x,c=q.popleft()
  if d[y][x]<I:continue
  d[y][x]=c
  for i,j in(y-1,x),(y,x-1),(y,x+1),(y+1,x):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='
  for i,j in(y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),(y-1,x-2),(y-1,x-1),(y-1,x+1),(y-1,x+2),(y,x-2),(y,x+2),(y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),(y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2):
    if h>i>-1<j<w<I==d[i][j]!=m[i][j]!='
print(d[f-1][g-1]%I-1)

Solution (Python):
import sys, math, heapq


def move(Maps, dists, stack):
    """
    deque = []
    heapq.heappush(deque, [ dists[start_y][start_x], start_x, start_y])
    """

    deque_jump = []

    while( len(stack) >0 ):
        dist_pos = stack.pop()

        x, y = [dist_pos[1], dist_pos[2] ]
        if(dists[y][x] < dist_pos[0]):
            continue
        Flag = -1 
        N_Flag = 0
        for dx, dy, i in ( (-1, 0, 0), (1, 0, 1), (0, -1, 2), (0, 1, 3) ):
            if( x+ dx < 0 or x+ dx > W-1 or y+ dy < 0 or y+ dy > H-1):
                continue
            if(Maps[y+dy][x+dx]=="
                Flag = i
                N_Flag += 1
                continue

            next = [x+ dx, y+ dy]
            
            if(dists[next[1] ][next[0] ] > dists[y][x]):
                dists[next[1] ][next[0] ] = dists[y][x]
                stack.append( [dists[next[1] ][next[0] ], next[0], next[1] ])

        if(N_Flag>1):

            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])


        elif(N_Flag > 0):
            
            dy_max = min(H-y, 3)
            dy_min = max(-y, -2)
            dx_min = max(-x, -2)
            dx_max = min(W-x, 3)
            if(Flag == 3):
                dy_min = 1
            elif(Flag == 2):
                dy_max = 0
            elif(Flag == 1):
                dx_min = 1
            else:
                dx_max = 0

            for dy in range( dy_min, dy_max ):
                for dx in range( dx_min, dx_max ):
                    next = [x+ dx, y+ dy]
                    if(Maps[y+dy][x+dx] == "." and dists[next[1] ][next[0] ] == inf):
                        dists[next[1] ][next[0] ] = dists[y][x]+1
                        deque_jump.append( [dists[next[1] ][next[0] ], next[0], next[1] ])
    return deque_jump

if(__name__ == "__main__"):
    """
    N = int( input().strip() )
    Length = list( map(int, input().strip().split() ) )
    """
    H, W= map(int, input().strip().split() )
    start = list( map(int, input().strip().split() ) ) 
    goal = list( map(int, input().strip().split() ) ) 
    for i in range(2):
        start[i] -= 1
        goal[i] -= 1
    Maps = [ [] for _ in range(H) ]
    for i in range(H):
        Maps[i] = input().strip()

    inf = 10**7

    dists = [ [inf for _ in range(W) ] for _ in range(H)] 
    dists[start[0]][start[1]] = 0


    y, x = start[0], start[1]
    deque_jump = [ [ dists[y][x], x, y] ]

    while( True ):
        deque_jump = move(Maps, dists, deque_jump)
        if( dists[goal[0]][goal[1]]<inf ):
            print(dists[goal[0]][goal[1]])
            break
        elif( len(deque_jump)==0 ):
            print(-1)
            break
        


    
    """
    if( dists[goal[0]][goal[1]]==inf ):
        pass
    else:
        print(dists[goal[0]][goal[1]])
    """

Solution (Python):
from collections import deque

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
Maze = [[_ for _ in input()] for __ in range(H)]
Q = deque()
Q.append((sy, sx, 0))
Cost = [[float('inf')] * W for _ in range(H)]
Cost[sy][sx] = 0
Move = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if i == j == 0:
            continue
        Move.append((i, j))
Walk = ((-1, 0), (1, 0), (0, 1), (0, -1))
while Q:
    y, x, cost = Q.popleft()
    if Cost[y][x] >= Cost[gy][gx]:
        break
    if cost > Cost[y][x]:
        continue
    for wy, wx in Walk:
        ny = y + wy
        nx = x + wx
        if ny < 0 or ny >= H or nx < 0 or nx >= W or Maze[ny][nx] == '
            continue
        if Cost[ny][nx] > cost:
            Q.appendleft((ny, nx, cost))
            Cost[ny][nx] = Cost[y][x]

    for my, mx in Move:
        ny = y + my
        nx = x + mx
        if ny < 0 or ny >= H or nx < 0 or nx >= W or Maze[ny][nx] == '
            continue
        if Cost[ny][nx] <= Cost[y][x] + 1:
            continue
        Cost[ny][nx] = Cost[y][x] + 1
        Q.append((ny, nx, cost+1))

if Cost[gy][gx] == float('inf'):
    Cost[gy][gx] = -1
print(Cost[gy][gx])

Solution (Python):

import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline


def valid(a,b):
	
	if 0<=a<=h-1 and 0<=b<=w-1 and arr[a][b] == ".":
		return True
	else:
		return False


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
arr = [input() for i in range(h)]

can_vis = []
dist = [[10**10]*w for i in range(h)]
q = deque()
ans = float("inf")
q.append((ch,cw))
dist[ch][cw] = 0

while q:
	
	
	curx , cury = q.popleft()
	
	for dx,dy in [[1,0],[0,1],[-1,0],[0,-1]]:
		if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury]:
			dist[curx+dx][cury+dy] = dist[curx][cury]
			q.appendleft((curx+dx, cury+dy))
	for dx in range(-2,3):
		for dy in range(-2,3):
			if valid(curx+dx, cury+dy) and dist[curx+dx][cury+dy] > dist[curx][cury] + 1:
				dist[curx+dx][cury+dy] = dist[curx][cury] + 1 
				q.append((curx+dx, cury+dy))


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