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
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    mylist = []
    for i in range(H):
        temp = input().rstrip()
        temp = tuple([True if temp[i]=="." else False for i in range(W)])
        mylist.append(temp)
    mylist = tuple(mylist)

    
    dist = Init(H, W, float('inf'))
    
    dq = deque()
    dq2 = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
    
    while dq:
        while dq:
            x, y = dq.popleft()
            if x == gx and y == gy:
                print(dist[gx][gy])
                sys.exit()


            
            for x2, y2 in move2:
                x2 += x
                y2 += y
                if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] and dist[x2][y2] > dist[x][y]+1:
                    dist[x2][y2] = dist[x][y]+1
                    dq2.append((x2,y2))

            
            for x2, y2 in move1:
                x2 += x
                y2 += y
                if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] and dist[x2][y2] > dist[x][y]:
                    dist[x2][y2] = dist[x][y]
                    dq.append((x2,y2))


        dq = deque(set(dq2))
        dq2 = deque()
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

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())
    base = ["
    base.append("
    for n in range(h):
        base.append("
    base.append("
    base.append("
    ans = [[-1] * (w+4) for _ in range(h+4)]
    for j in range(w+4):
        for i in range(h+4):
            if base[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]]
    move2 = [
        [-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], \
        [-1, -2], [-1, -1], [-1, 0], [-1, 1], [-1, 2], \
        [0, -2], [0, -1], [0, 0], [0, 1], [0, 2], \
        [1, -2], [1, -1], [1, 0], [1, 1], [1, 2], \
        [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]
        ]
    q = deque([[ch, cw]])
    one_time = deque([])
    while len(q) > 0:
        x, y = q.popleft()
        one_time.append([x, y])
        for i, j in move:
            v1, v2 = x+i, y+j
            if ans[v1][v2] == -1:
                ans[v1][v2] = ans[x][y]
                q.append([v1, v2])
        if len(q) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.popleft()
                for i, j in move2:
                    v1, v2 = x2+i, y2+j
                    if ans[v1][v2] == -1:
                        ans[v1][v2] = ans[x2][y2] + 1
                        q.append([v1, v2])
    print(ans[dh][dw])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    
    mylist = [input().rstrip() for i in range(H)]
    dist = Init(H, W, float('inf'))
    
    dq = deque()
    dq2 = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
    while dq:
        while dq:
            x, y = dq.popleft()
            if x == gx and y == gy:
                print(dist[gx][gy])
                sys.exit()


            
            for x2, y2 in move2:
                x2 += x
                y2 += y
                if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]+1:
                    dist[x2][y2] = dist[x][y]+1
                    dq2.append((x2,y2))

            
            for x2, y2 in move1:
                x2 += x
                y2 += y
                if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]:
                    dist[x2][y2] = dist[x][y]
                    dq.append((x2,y2))


        dq = deque(set(dq2))
        dq2 = deque()
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

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

num = 0
if S[0][0] == '
    S[0][0] = -1
else:
    num += 1
    S[0][0] = num

for i in range(1, H):
    if S[i][0] == '
        S[i][0] = -1
    elif S[i-1][0] > 0:
        S[i][0] = S[i-1][0]
    else:
        num += 1
        S[i][0] = num

for j in range(1, W):
    if S[0][j] == '
        S[0][j] = -1
    elif S[0][j-1] > 0:
        S[0][j] = S[0][j-1]
    else:
        num += 1
        S[0][j] = num

for i in range(1, H):
    for j in range(1, W):
        if S[i][j] == '
            S[i][j] = -1
        elif S[i-1][j] < 0 and S[i][j-1] < 0:
            num += 1
            S[i][j] = num
        elif S[i-1][j] < 0:
            S[i][j] = S[i][j-1]
        elif S[i][j-1] < 0:
            S[i][j] = S[i-1][j]
        else:
            S[i][j-1] = min(S[i-1][j], S[i][j-1])
            S[i-1][j] = min(S[i-1][j], S[i][j-1])
            S[i][j] = min(S[i-1][j], S[i][j-1])

G = [{} for _ in range(num)]

for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue

        start_i = max(0, i-2)
        start_j = max(0, j-2)
        end_i = min(H, i+3)
        end_j = min(W, j+3)
        for x in range(start_i, end_i):
            for y in range(start_j, end_j):
                if S[x][y] > 0 and S[x][y] != S[i][j]:
                    G[S[x][y]-1][S[i][j]-1] = 1
                    G[S[i][j]-1][S[x][y]-1] = 1

for i in range(H):
    for j in range(W):
        if S[i][j] == -1:
            continue

        start_i = max(0, i-2)
        start_j = max(0, j-2)
        end_i = min(H, i+3)
        end_j = min(W, j+3)
        for x in range(start_i, end_i):
            for y in range(start_j, end_j):
                if (x, y) in [(i-1, j), (i, j-1), (i+1, j), (i, j+1)]:
                    if S[x][y] > 0 and S[x][y] != S[i][j]:
                        G[S[x][y]-1][S[i][j]-1] = 0
                        G[S[i][j]-1][S[x][y]-1] = 0

from heapq import heapify, heappop, heappush
def dijkstra(s):
    dist = [float('inf')] * num
    dist[s] = 0

    heap = [(s, 0)]
    heapify(heap)
    while heap:
        v, c = heappop(heap)
        if c > dist[v]: continue
        for u, d in G[v].items():
            tmp = d + dist[v]
            if tmp < dist[u]:
                dist[u] = tmp
                heappush(heap, (u, tmp))

    return dist

start = S[Ch-1][Cw-1]-1
end = S[Dh-1][Dw-1]-1
dist = dijkstra(start)

ans = -1 if dist[end] == float('inf') else dist[end]
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())
a = []
for _ in range(h):
    a.append(input())
INF = 10**9
dxdy = [(-1,0), (0,-1), (0,1), (1,0)]
step = [[INF]*w for _ in range(h)]
step[ch-1][cw-1] = 0
q = deque([(ch-1, cw-1)])
nq = deque()
while True:
    while q:
        y, x = q.popleft()
        nq.append((y, x))
        for dy, dx in dxdy:
            if not (0<=x+dx<w and 0<=y+dy<h):
                continue
            if a[y+dy][x+dx]=='
                continue
            if step[y+dy][x+dx]>step[y][x]:
                step[y+dy][x+dx] = step[y][x]
                q.append((y+dy, x+dx))
    while nq:
        y, x = nq.popleft()
        for i in range(25):
            dy = i//5-2
            dx = i%5-2
            if not (0<=x+dx<w and 0<=y+dy<h):
                continue
            if a[y+dy][x+dx]=='
                continue
            if step[y+dy][x+dx]>step[y][x]+1:
                step[y+dy][x+dx] = step[y][x]+1
                q.append((y+dy, x+dx))
    if not q:
        break
if step[dh-1][dw-1]==INF:
    print(-1)
else:
    print(step[dh-1][dw-1])

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))


h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

a = [set() for i in range(2)]
i = 0
a[i].add(start)
dist[start] = 0

while a[i]:
    p = a[i].pop()
    if dist[goal] <= dist[p]:
        break
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        a[i].add(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        a[i-1].add(q)
                        dist[q] = dist[p] + 1
    if not a[i]:
        i = [1,0][i]

print(-1 if dist[goal]==10**10 else dist[goal])

Solution (Python):






from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))
    gen_warp_can_reach = (
        (h, w, (h, w) in can_walk)  
        for h in range(-2, 3) for w in range(-2, 3) if not h == 0 == w)
    warp_can_reach = tuple(gen_warp_can_reach)
    qu = deque()
    qu.append((init_h, init_w, 0))  

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            
            continue
        grid[h][w] = 'R'  

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append((start,0))
dist[start] = 0

while dq:
    p,d = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    if d>dist[p]:
        continue
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dist[q] = dist[p]
                        dq.appendleft((q,dist[q]))
                else:
                    if dist[q]>dist[p]+1:
                        dist[q] = dist[p] + 1
                        dq.append((q,dist[q]))

print(-1 if dist[goal]==10**10 else dist[goal])

Solution (Python):






from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = ((1, 0), (0, 1), (-1, 0), (0, -1))
    gen_warp_can_reach = (
        (h, w, (h, w) in can_walk)  
        for h in range(-2, 3) for w in range(-2, 3) if not h == 0 == w)
    warp_can_reach = set(gen_warp_can_reach)
    qu = deque()
    qu.append((init_h, init_w, 0))  

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            
            continue
        grid[h][w] = 'R'  

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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


def Dijkstra(start, goal, size):
    sy, sx = start
    gy, gx = goal
    dist = [[float('inf')] * W for i in range(H)]
    pos = [(0, sy, sx)]
    heapify(pos)
    dist[sy][sx] = 0

    while len(pos):
        cost, y, x = heappop(pos)

        if y == gy and x == gx:
            return cost
        if dist[y][x] < cost:
            continue
        
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.':
                if dist[ny][nx] > cost:
                    dist[ny][nx] = cost
                    heappush(pos, (cost, ny, nx))
        
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                wy = y + w_y
                wx = x + w_x
                if 0 <= wy < H and 0 <= wx < W and maze[wy][wx] == '.':
                    if dist[wy][wx] > cost + 1:
                        dist[wy][wx] = cost + 1
                        heappush(pos, (cost + 1, wy, wx))
    return dist[gy][gx]

ans = Dijkstra((Ch, Cw), (Dh, Dw), H * W)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

"""
pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            
            
            pos.appendleft([ny, nx])
            dp[ny][nx] = dp[y][x]
    
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and dp[wy][wx] == -1:
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])
"""

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    
    mylist = [input().rstrip() for i in range(H)]
    dist = Init(H, W, float('inf'))
    
    dq = deque()
    dq2 = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
    while dq:
        x, y = dq.popleft()
        if x == gx and y == gy:
            print(dist[gx][gy])
            sys.exit()


        
        for x2, y2 in move2:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]+1:
                dist[x2][y2] = dist[x][y]+1
                dq2.append((x2,y2))

        
        for x2, y2 in move1:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]:
                dist[x2][y2] = dist[x][y]
                dq.append((x2,y2))

        if not dq:
            dq = deque(set(dq2))
            dq2 = deque()
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

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


def Dijkstra(start, goal, size):
    sy, sx = start
    gy, gx = goal
    dist = [[float('inf')] * W for i in range(H)]
    pos = [(0, sy, sx)]
    heapify(pos)
    dist[sy][sx] = 0

    while len(pos):
        cost, y, x = heappop(pos)

        if y == gy and x == gx:
            return cost
        if dist[y][x] < cost:
            continue
        
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < H and 0 <= nx < W and maze[ny][nx] == '.':
                if dist[ny][nx] > cost:
                    dist[ny][nx] = cost
                    heappush(pos, (cost, ny, nx))
        
        for w_y in range(-2, 3):
            for w_x in range(-2, 3):
                wy = y + w_y
                wx = x + w_x
                if 0 <= wy < H and 0 <= wx < W and maze[wy][wx] == '.':
                    if dist[wy][wx] > cost + 1:
                        dist[wy][wx] = cost + 1
                        heappush(pos, (cost + 1, wy, wx))
    return dist[gy][gx]

ans = Dijkstra((Ch, Cw), (Dh, Dw), H * W)
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):






from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                yield (h, w, (h, w) in can_walk)
    warp_can_reach = tuple(gen_warp_can_reach())  
    qu = deque()
    qu.append((init_h, init_w, 0))  

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            
            continue
        grid[h][w] = 'R'  

        for h_delta, w_delta, walking in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if walking:
                        qu.appendleft((new_h, new_w, warps))
                    else:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
import math
from collections import defaultdict, deque
from copy import deepcopy
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    H, W = MI()
    sx, sy = MI()
    gx, gy = MI()
    sx-=1
    sy-=1
    gx-=1
    gy-=1
    
    mylist = [input().rstrip() for i in range(H)]
    dist = Init(H, W, float('inf'))
    
    dq = deque()
    dq2 = deque()
    dq.append((sx, sy))
    move1 = [[1,0],[0,1],[-1,0],[0,-1]]
    move2 = [[i,j] for i in range(-2,3) for j in range(-2,3) if not [i, j ] in move1 and [i, j] != [0, 0]]
    dist[sx][sy] = 0
    while dq:
        x, y = dq.pop()
        
        for x2, y2 in move2:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]+1:
                dist[x2][y2] = dist[x][y]+1
                dq2.append((x2,y2))

        
        for x2, y2 in move1:
            x2 += x
            y2 += y
            if x2 >= 0 and x2 < H and y2 >= 0 and y2 < W and mylist[x2][y2] == "." and dist[x2][y2] > dist[x][y]:
                dist[x2][y2] = dist[x][y]
                dq.append((x2,y2))
                
        if not dq:
            dq = dq2
            dq2 = deque()
        
    
    if dist[gx][gy] == float('inf'):
        print(-1)
    else:
        print(dist[gx][gy])
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    if dist[goal] <= dist[p]:
        break
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1


print(-1 if dist[goal]==10**10 else dist[goal])

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,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[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 collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    can_walk = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                warping = True
                if h == 0 == w:
                    continue
                if (h, w) in can_walk:
                    warping = False
                yield (h, w, warping)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            
            
            continue
        grid[h][w] = 'R'  

        for h_delta, w_delta, warping in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if warping:
                        qu.append((new_h, new_w, warps + 1))
                    else:
                        qu.appendleft((new_h, new_w, warps))
    return -1


if __name__ == '__main__':
    print(main())

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

dq = deque()
dq.append(start)
dist[start] = 0

while dq:
    p = dq.popleft()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        dq.appendleft(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        dq.append(q)
                        dist[q] = dist[p] + 1

print(-1 if dist[goal]==10**10 else dist[goal])