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
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


cmd = [[-1,0],[1,0],[0,1],[0,-1]]
H,W = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
Map = [["
for _ in range(H):
    Map.append(["
Map.append(["
Q = deque([[ch,cw]])
Next = deque([])
visidat = [[10**6]*(W+2) for _ in range(H+2)]
num = 0
flag = 0
fl = 0
visidat[ch][cw] = 0
while flag == 0:
    while len(Q) != 0:
        h,w = Q.popleft()
        if h == dh and w == dw:
            print(num)
            flag = 1
            break
        if visidat[h][w] >= num:
            for i in range(-2,3):
                for j in range(-2,3):
                    p,q = h+i,w+j
                    if p < 0 or q < 0 or p > H+1 or q > W+1 or ((abs(i)+abs(j))<=1):
                        continue
                    if Map[p][q] == ".":
                        if visidat[p][q] > num + 1:
                            Next.append([p,q])
                            visidat[p][q] = num + 1
            for cx,cy in cmd:
                newh = cy + h
                neww = cx + w
                if Map[newh][neww] == "
                    continue
                else:
                    if visidat[newh][neww] > num :
                        visidat[newh][neww] = num
                        Q.append([newh,neww])
        else:
            continue
        
    Q = Next
    if len(Q) == 0:
        if flag == 0:
            fl = 1
        break
    Next = deque([])
    num += 1
if fl == 1:
    print(-1)

Solution (Python):
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
import collections
from heapq import *

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

dp=[[float("inf") for _ in range(W)] for _ in range(H)]
st=[Ch-1,Cw-1]
d2=deque()
d = deque()
d2=deque()
d.append(st)
cnt=0
dp[Ch-1][Cw-1]=0
while True:
    while len(d)>0:
        x,y=d.popleft()
        d2.append([x,y])
        
        if x!=0:
            if S[x-1][y]==".":
                if dp[x-1][y]>dp[x][y]:
                    dp[x - 1][y]=dp[x][y]
                    d.append([x-1,y])
        if x!=H-1:
            if S[x+1][y]==".":
                if dp[x+1][y]>dp[x][y]:
                    dp[x + 1][y]=dp[x][y]
                    d.append([x+1,y])
        if y!=0:
            if S[x][y-1]==".":
                if dp[x][y-1]>dp[x][y]:
                    dp[x][y-1]=dp[x][y]
                    d.append([x,y-1])
        if y!=W-1:
            if S[x][y+1]==".":
                if dp[x][y+1]>dp[x][y]:
                    dp[x][y+1]=dp[x][y]
                    d.append([x,y+1])
        
        
    while len(d2)>0:
        x,y=d2.popleft()
        for i in range(max(0,x-2),min(x+3,H)):
            for j in range(max(0,y-2),min(y+3,W)):
                if S[i][j]==".":
                    if dp[i][j] > dp[x][y]+1:
                        dp[i][j]=dp[x][y]+1
                        d.append([i,j])
    
    
    cnt=cnt+1
    if len(d)==0:
        break
if dp[Dh-1][Dw-1]==float("inf"):
    print(-1)
else:
    print(dp[Dh-1][Dw-1])

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(lambda x: int(x)-1, input().split())
    Dh, Dw = map(lambda x: int(x)-1, input().split())
    S = [input() for _ in range(H)]

    adj = [[] for _ in range(W*H)]
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == '
            for k in range(4):
                y = i + dy[k]
                x = j + dx[k]
                if 0 <= y < H and 0 <= x < W:
                    if S[y][x] == '.':
                        adj[W*i + j].append(W*y + x)

    
    worp = [[] for _ in range(W*H)]
    for i in range(H):
        for j in range(W):
            if S[i][j] == '
            for kx in [-2,-1,0,1,2]:
                for ky in [-2,-1,0,1,2]:
                    if kx == ky == 0: continue
                    y = i + ky
                    x = j + kx
                    if W*y + x in adj[W*i + j]: continue
                    if 0 <= y < H and 0 <= x < W:
                        if S[y][x] == '.':
                            worp[W*i + j].append(W*y + x)
    
    start = W*Ch + Cw
    goal = W*Dh + Dw
    queue = deque([start])
    visit = [-1] * (W*H)
    visit[start] = 0
    
    while queue:
        nextq = queue.copy()
        while queue:
            now = queue.popleft()
            for u in adj[now]:
                if visit[u] < 0:
                    queue.append(u)
                    nextq.append(u)
                    visit[u] = visit[now]
        
        while nextq:
            now = nextq.popleft()
            for u in worp[now]:
                if visit[u] < 0:
                    queue.append(u)
                    visit[u] = visit[now]+1
    
    print(visit[goal])

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 = [[s for s in input()]for _ in range(h)]
que = deque([[C[0]-1,C[1]-1]])
que2 = deque([])
dd = [-1,1]
d1 = [-2,-1,0,1,2]
reach = [[False for _ in range(w)]for _ in range(h)]
added = [[False for _ in range(w)]for _ in range(h)]
reach[C[0]-1][C[1]-1]=True
added[C[0]-1][C[1]-1]=True
ans = 0
while que:
    u = que.popleft()
    x,y = u
    if not reach[x][y]:
        reach[x][y] = True
    for d in dd:
        xx = x+d
        yy = y+d
        if 0 <= xx < h:
            if S[xx][y] == '.':
                if not reach[xx][y]:
                    que.append([xx,y])
                    reach[xx][y] = True
                    added[xx][y] = True

        if 0 <= yy < w:
            if S[x][yy] =='.':
                if not reach[x][yy]:
                    que.append([x,yy])
                    reach[x][yy] = True
                    added[x][yy] = True 
    for i in d1:
        for j in d1:
            s,t = x+i,y+j
            if 0<=s<h and 0<=t<w:
                if S[s][t] == '.' and not added[s][t]:
                    que2.append([s,t]) 
                    added[s][t] = True

    if reach[D[0]-1][D[1]-1]:
        print(ans)
        exit()    
    if not que:
        que = que2
        que2 = deque([])
        ans += 1
print(-1)

Solution (Python):
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=[[False for i in range(W+4)],[False for i in range(W+4)]]
for i in range(H):
    S.append([False,False]+[j=='.' for j in input()]+[False,False])
S+=[[False for i in range(W+4)],[False for i in range(W+4)]]

def check(h,w,island_num):
    assert S[h][w]
    block[h][w]=island_num
    if S[h-1][w] and block[h-1][w]==-1:
        check(h-1,w,island_num)
    if S[h+1][w] and block[h+1][w]==-1:
        check(h+1,w,island_num)
    if S[h][w-1] and block[h][w-1]==-1:
        check(h,w-1,island_num)
    if S[h][w+1] and block[h][w+1]==-1:
        check(h,w+1,island_num)

block=[]
for i in range(H+4):
    block.append([-1 for j in range(W+4)])

island_num=0

for h in range(H+4):
    for w in range(W+4):
        if S[h][w] and block[h][w]==-1:
            check(h,w,island_num)
            island_num+=1


neighbor={}
for island in range(island_num):
    neighbor[island]=set()


for h in range(2,H+2):
    for w in range(2,W+2):
        if block[h][w]!=-1:
            for y in range(h-2,h+3):
                for x in range(w-2, w+3):
                    if block[y][x]!=-1 and block[h][w]!=block[y][x]:
                        neighbor[block[h][w]].add(block[y][x])


start=block[Ch][Cw]
goal=block[Dh][Dw]
assert start!=-1
assert goal!=-1



dist=[10**10 for i in range(island_num)]
dist[start]=0

nexts=[start]
while True:
    _nexts=[]
    for n in nexts:
        for neigh in neighbor[n]:
            assert neigh!=-1
            if dist[neigh]>dist[n]+1:
                _nexts.append(neigh)
                dist[neigh]=dist[n]+1
    nexts=set(_nexts)
    if len(nexts)==0:
        break

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

Solution (Python):
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())

s = list()
offsets = list()

for i in range(-2, 3):
    for j in range(-2, 3):
        offsets.append((i, j))


def print_map(m):
    for mm in m:
        print(mm)


def label(num, x, y):
    res = list()
    if not (0 <= x < h and 0 <= y < w):
        return res
    if s[x][y] != ".":
        return res
    s[x][y] = num

    res += label(num, x - 1, y)
    res += label(num, x + 1, y)
    res += label(num, x, y - 1)
    res += label(num, x, y + 1)

    res.append((x, y))

    return res


def find_next(x, y):
    res = list()

    for offset in offsets:
        xx, yy = x + offset[0], y + offset[1]
        if not (0 <= xx < h and 0 <= yy < w):
            continue

        if s[xx][yy] == ".":
            res.append((xx, yy))

    return res


for i in range(h):
    s.append(list(input()))

stage = 0
labeled = label(stage, dh - 1, dw - 1)

stage += 1

while len(labeled) > 0:
    new_labeled = list()
    for l in labeled:
        nexts = find_next(l[0], l[1])
        for n in nexts:
            new_labeled += label(stage, n[0], n[1])

    labeled = new_labeled
    stage += 1

if s[ch - 1][cw - 1] != ".":
    print(s[ch - 1][cw - 1])
else:
    print(-1)

Solution (Python):
from collections import deque

h,w = map(int,input().split())
sh,sw = map(int,input().split())
gh,gw = map(int,input().split())
s = [input() for _ in range(h)]

sh-=1; sw-=1; gh-=1; gw-=1;

dist = [[-1]*w for _ in range(h)]
dist[sh][sw] = 0
q = deque([(0,sh,sw)])
warpq = deque([])

while q or warpq:
    while q:

        d,vsh,vsw = q.popleft()

        flag = 0
        
        for dh,dw in [(-1,0),(1,0),(0,-1),(0,1)]:
            newh = vsh+dh
            neww = vsw+dw
            if newh<0 or h<=newh or neww<0 or w<=neww: continue
            if s[newh][neww] == "
                if flag ==0:
                    warpq.append((d,vsh,vsw))
                    flag = 1
                continue

            if dist[newh][neww] == -1:
                dist[newh][neww] = d
                q.append((d,newh,neww))

    while warpq:

        d,vsh,vsw = warpq.popleft()
        for dh in range(-2,3):
            for dw in range(-2,3):
                newh = vsh+dh
                neww = vsw+dw
                if newh<0 or h<=newh or neww<0 or w<=neww: continue
                if abs(dh)+abs(dw)<=0: continue
                if s[newh][neww] == "

                if dist[newh][neww] == -1:
                    dist[newh][neww] = d+1
                    q.append((d+1,newh,neww))
            
print(dist[gh][gw])

Solution (Python):
import sys
from collections import deque

input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    C_h, C_w = map(int, input().split())
    D_h, D_w = map(int, input().split())
    field = [list(input()) for _ in range(H)]
    direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    F = [[float('inf')] * W for _ in range(H)]
    queue = deque([(C_h - 1, C_w - 1)])
    nextqueue = deque([])
    t = 0
    alr = set()
    while queue:
        i, j = queue.popleft()
        if not (i, j) in alr:
            F[i][j] = min(t, F[i][j])
            if D_h == i + 1 and D_w == j + 1:
                break
            alr.add((i, j))
            for dx, dy in direction:
                nx, ny = i + dx, j + dy
                if 0 <= nx <= H - 1 and 0 <= ny <= W - 1:
                    if field[nx][ny] == '.':
                        queue.append((nx, ny))
            for p in range(i - 2, i + 3):
                for q in range(j - 2, j + 3):
                    if 0 <= p <= H - 1 and 0 <= q <= W - 1:
                        if field[p][q] == '.':
                            nextqueue.append((p, q))
                            F[p][q] = min(F[p][q], t + 1)
        if not queue:
            queue = nextqueue.copy()
            nextqueue.clear()
            t += 1

    if F[D_h-1][D_w-1] == float('inf'):
        print(-1)
    else:
        print(F[D_h - 1][D_w - 1])


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
def main():
    h, w = map(int, input().split())
    S = list(map(lambda x: int(x) - 1, input().split()))
    G = list(map(lambda x: int(x) - 1, input().split()))
    A = [list(input()) for _ in range(h)]
    INF = 100000000
    score = [[INF] * w for _ in range(h)]
    score[S[0]][S[1]] = 0
    visited = [[False] * w for _ in range(h)]
    stack = deque([S])
    dxy = [[1, 0], [-1, 0], [0, -1], [0, 1]]
    while stack:
        y, x = stack.popleft()
        if visited[y][x]:
            continue
        else:
            visited[y][x] = True
        count = 0
        for dx, dy in dxy:
            X = x + dx
            Y = y + dy
            if Y < 0 or Y >= h or X < 0 or X >= w:
                continue
            elif A[Y][X] == '.':
                stack.appendleft([Y, X])
                score[Y][X] = min(score[Y][X], score[y][x])
        if count == 0 and A[y][x] == '.':
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + j
                    Y = y + i
                    if Y < 0 or Y >= h or X < 0 or X >= w:
                        continue
                    if A[Y][X] == '.' and score[Y][X] > score[y][x] + 1:
                        stack.append([Y, X])
                        score[Y][X] = min(score[Y][X], score[y][x] + 1)
    print(score[G[0]][G[1]]) if score[G[0]][G[1]] != INF else print(-1)


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 = [0 for i in range(H+4)]
S[0] = "
S[1] = "
S[H+2] = "
S[H+3] = "
for i in range(2, H+2):
  S[i] = "
  
B = [ [-1 for i in range(W+4)] for i in range(H+4)]

def search(i,j,c):
  global B
  B[i][j] = c
  L = [(-1,0), (1, 0), (0, -1), (0, 1)]
  for X in L:
    if S[i+X[0]][j+X[1]] == '.' and B[i+X[0]][j+X[1]] < 0:
        search(i+X[0],j+X[1],c)
        

c = 0
for i in range(2,H+2):
  for j in range(2,W+2):
    if S[i][j] == '.' and B[i][j] < 0:
      search(i, j, c)
      c += 1

Cc = B[Ch+1][Cw+1]
Dc = B[Dh+1][Dw+1]
dic = {i:set() for i in range(c)}

for i in range(2, H+2):
  for j in range(2, W+2):
    if B[i][j] >= 0:
      for x in range(-2, 3):
        for y in range(-2, 3):
          if S[i+x][j+y] == '.' and B[i][j] != B[i+x][j+y]:
            dic[B[i][j]].add(B[i+x][j+y])

ans = [-1 for i in range(c)]
ans[Cc] = 0
not_check = [1 for i in range(c)]
not_check[Cc] = 0
next_check = {Cc}

t = 0
while len( next_check ):
  t += 1
  tmp = set()
  for i in next_check:
    for j in dic[i]:
      if not_check[j]:
        not_check[j] = 0
        ans[j] = t
        tmp.add( j )
  next_check = {i for i in tmp}

print(ans[Dc])

Solution (Python):
def main():
    import collections
    import sys
    input = sys.stdin.buffer.readline
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    input = sys.stdin.readline
    S = [input() for i in range(H)]

    q = collections.deque()
    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    flag = True

    r = set()
    ss = []
    start = -1
    goal = -1
    
    D = dict()
    for i in range(H):
        for j in range(W):
            if (i, j) in r or S[i][j] == '
                continue
            q.append((i, j))
            ss.append(set([(i, j)]))
            r.add((i, j))
            L = len(ss)
            D[(i, j)] = L-1
            while(q):
                x, y = q.popleft()
                for k, l in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
                    if 0 <= k <= H-1 and 0 <= l <= W-1 and S[k][l] != '
                        r.add((k, l))
                        D[(k, l)] = L - 1
                        q.append((k, l))
                        ss[-1].add((k, l))
            if start == -1 and (Ch, Cw) in ss[-1]:
                start = L - 1
            if goal == -1 and (Dh, Dw) in ss[-1]:
                goal = L - 1

    if D[Ch, Cw] == D[(Dh, Dw)]:
        print(0)
        exit(0)

    G = [set() for i in range(len(ss))]
    for id, X in enumerate(ss):
        for x, y in X:
            for i in range(x-2, x+3):
                if 0 <= i <= H-1:
                    for j in range(y-2, y+3):
                        if 0 <= j <= W-1:
                            if S[i][j] != '
                                G[id].add(D[(i, j)])

    r = set()
    r.add(start)
    q.append((start, 0))
    while(q):
        x, c = q.popleft()
        if x == goal:
            print(c)
            flag = False
            break
        for y in G[x]:
            if y in r:
                continue
            else:
                r.add(y)
                q.append((y, c+1))
    
    if flag:
        print(-1)


main()

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

h,w = m()

c = l()

d = l()

s = [list(input()[:-1]) for i in range(h)]

data = [[-1 for j in range(w)]for i in range(h)]

po = [cl.deque([]) for i in range(h*w // 2 + 1)]

now = 0
po[0] = cl.deque([[c[0]-1,c[1]-1]])
d[0] -= 1
d[1] -= 1
dire = [[1,0],[0,1],[-1,0],[0,-1]]



while True:
    if now >= h*w // 2 + 1:
        break
    if len(po[now]) == 0:
        now += 1
        continue
    else:
        popo = po[now].popleft()
        if data[popo[0]][popo[1]] != -1 and data[popo[0]][popo[1]] < now:
            continue
        else:
            data[popo[0]][popo[1]] = now
            for kkk in dire:
                if (popo[0] + kkk[0] >= 0 and popo[0] + kkk[0] < h) and (popo[1] + kkk[1] >= 0 and popo[1] + kkk[1] < w):
                    if s[popo[0] + kkk[0]][popo[1] + kkk[1]] == "
                        continue
                    if data[popo[0] + kkk[0]][popo[1] + kkk[1]] == -1 or data[popo[0] + kkk[0]][popo[1] + kkk[1]] > now:
                        data[popo[0] + kkk[0]][popo[1] + kkk[1]] = now
                        po[now].append([popo[0]+ kkk[0],popo[1] + kkk[1]])

            for i in range(5):
                i -= 2
                if i + popo[0] < 0 or i + popo[0] >= h:
                    continue
                for j in range(5):
                    j -= 2
                    if j + popo[1] < 0 or j + popo[1] >= w:
                        continue
                    elif s[popo[0]+ i][popo[1] + j] == ".":
                        if data[popo[0]+ i][popo[1] + j] > now+1 or data[popo[0]+ i][popo[1] + j] == -1:
                            if now + 1 <= h*w // 2:
                                data[popo[0]+ i][popo[1] + j] = now+1
                                po[now+1].append([popo[0]+ i,popo[1] + j])


print(data[d[0]][d[1]])

Solution (Python):
import sys
from collections import deque
input = sys.stdin.readline
H, W = map(int, input().split())
sx, sy = map(int, input().split())
gx, gy = map(int, input().split())
sx -= 1
sy -= 1
gx -= 1
gy -= 1

C = [list(input()) for i in range(H)]
inf = float("inf")
for i in range(H):
    for j in range(W):
        if C[i][j] == ".":
            C[i][j] = 0
        else:
            C[i][j] = 1
d0 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
d1 = [[-2, -2], [-2, -1], [-2, 0], [-2, 2], [-1, 2], [0, 2], [-2, 1], [-1, -2], [-1, -1], [-1, 1], [0, -2], [1, -2], [1, -1], [1, 1], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2]]

dist = [[inf] * W for i in range(H)]
dist[sx][sy] = 0
que = deque([[0, sx, sy]])
while que:
    L, x, y = que.popleft()
    
    
    for dx, dy in d0:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and L + C[nx][ny] < dist[nx][ny] and C[nx][ny] == 0:
            dist[nx][ny] = L + C[nx][ny]
            que.appendleft([L, nx, ny])
    for dx, dy in d1:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and L + C[nx][ny] + 1 < dist[nx][ny] and C[nx][ny] == 0:
            dist[nx][ny] = L + C[nx][ny] + 1
            que.append([L + 1, nx, ny])
            

            
            
            
            



ans = dist[gx][gy]
if ans == inf:
    print(-1)
else:
    print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch-=1
cw-=1
stack=[(ch,cw)]
dh,dw=map(int,input().split())
dh-=1
dw-=1
b=[w*[-1]for _ in range(h)]
for i in range(h):
  for j,t in enumerate(input()):
    if t=="
b[ch][cw]=0
dxy=((-1,0),(1,0),(0,-1),(0,1))
for ans in range(10**6):
  for x,y in stack:
    b[x][y]=1
    if x==dh and y==dw:
      print(ans)
      exit()
    for dx,dy in dxy:
      if 0<=x+dx<h and 0<=y+dy<w:
        if b[x+dx][y+dy]==10**10:continue
        if b[x+dx][y+dy]==-1:
          stack.append((x+dx,y+dy))
          b[x+dx][y+dy]=1
  stackk=[]
  for x,y in stack:
    for xx in range(max(0,x-2),min(h,x+3)):
      for yy in range(max(0,y-2),min(w,y+3)):
        if b[xx][yy]==-1:stackk.append((xx,yy))
  stack=stackk
print(-1)

Solution (Python):
from collections import deque

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

walk = [(0, 1), (1, 0), (-1, 0), (0, -1)]
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)]
step = 0
already = set()
already.add((ch,cw))
next = set()
next.add((ch,cw))
while len(next) > 0:
    d = deque(list(next))
    step_already = list(next)
    while len(d) > 0:
        pop = d.popleft()
        for h, w in walk:
            nh, nw = pop[0]+h, pop[1]+w
            if (nh, nw) not in already and nh >= 0 and nh<H and nw >= 0 and nw<W and S[nh][nw] != '
                if nh == dh and nw == dw:
                    print(step)
                    exit()
                already.add((nh, nw))
                step_already.append((nh, nw))
                d.append((nh,nw))
    next = set()
    step += 1
    for h, w in step_already:
        for jh, jw in jump:
            nh, nw = h+jh, w+jw
            if (nh, nw) not in already and nh >= 0 and nh<H and nw >= 0 and nw<W and S[nh][nw] != '
                if nh == dh and nw == dw:
                    print(step)
                    exit()
                next.add((nh,nw))
                already.add((nh,nw))

print(-1)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



H,W = LI()
Ch,Cw = LI()
Dh,Dw = LI()

Q = [list(map(str,input())) for _ in range(H)]
D = [(0,1),(0,-1),(-1,0),(1,0)]

visited = [[-1]*W for _ in range(H)]

s = (Ch-1,Cw-1)
c = 0
visited[Ch-1][Cw-1] = c
S = [s]
Sc = [s]
while True:
    while S:
        v = S.pop()
        for d in D:
            new = (v[0]+d[0],v[1]+d[1])
            if new[0] == Dh-1 and new[1] == Dw-1:
                print(c)
                exit()
            if 0 <= new[0] < H and 0 <= new[1] < W and Q[new[0]][new[1]] == '.' and visited[new[0]][new[1]] == -1:
                visited[new[0]][new[1]] = c
                S.append(new)
                Sc.append(new)
    c += 1
    S = []
    for v in Sc:
        for i in range(-2,3):
            for j in range(-2,3):
                new = (v[0]+i,v[1]+j)
                if new[0] == Dh-1 and new[1] == Dw-1:
                    print(c)
                    exit()
                if 0 <= new[0] < H and 0 <= new[1] < W and visited[new[0]][new[1]] == -1 and Q[new[0]][new[1]] == '.':
                    S.append(new)
                    visited[new[0]][new[1]] = c
    if not S:
        break
    Sc = S[:]
    
print(-1)

Solution (Python):
import sys
input = sys.stdin.readline
import heapq

H,W=map(int,input().split())
sh,sw=map(int,input().split())
gh,gw=map(int,input().split())
MAP=[input().strip() for i in range(H)]

ANS=[[1<<30]*W for i in range(H)]

sh-=1
sw-=1
gh-=1
gw-=1

ANS[sh][sw]=0

def ca(sc,x,y):
    return sc*(10**8)+x*(10**4)+y

def inv(w):
    sc=w//(10**8)
    w%=(10**8)
    x=w//(10**4)
    y=w%(10**4)

    return sc,x,y

Q=[ca(0,sh,sw)]

while Q:
    sc,x,y=inv(heapq.heappop(Q))

    if sc>ANS[x][y]:
        continue

    for i,j in [(x-2,y-2),(x-2,y-1),(x-2,y),(x-2,y+1),(x-2,y+2),(x-1,y-2),(x-1,y-1),(x-1,y),(x-1,y+1),(x-1,y+2),(x,y-2),(x,y-1),(x,y+1),(x,y+2),(x+1,y-2),(x+1,y-1),(x+1,y),(x+1,y+1),(x+1,y+2),(x+2,y-2),(x+2,y-1),(x+2,y),(x+2,y+1),(x+2,y+2)]:
        if 0<=i<H and 0<=j<W:
            if MAP[i][j]=="." and abs(i-x)+abs(j-y)==1 and ANS[i][j]>sc:
                ANS[i][j]=sc
                heapq.heappush(Q,ca(ANS[i][j],i,j))
            elif MAP[i][j]=="." and abs(i-x)+abs(j-y)>1 and ANS[i][j]>sc+1:
                ANS[i][j]=sc+1
                heapq.heappush(Q,ca(ANS[i][j],i,j))

if ANS[gh][gw]==1<<30:
    print(-1)
else:
    print(ANS[gh][gw])

Solution (Python):


from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()

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

Cx, Cy = input().split()
Cx = int(Cx)
Cy = int(Cy)

Dx, Dy = input().split()
Dx = int(Dx)
Dy = int(Dy)

matrix = []

for _ in range(H):
    row = list(input())
    matrix += [row]



from collections import deque


visited = set()

def bfs(x, y, label):
    global visited
    worklist = deque([(x, y)])
    while len(worklist):
        (x, y) = worklist.popleft()
        matrix[x][y] = label
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            new_x, new_y = x+dx, y+dy
            if 0 <= new_x < H and 0 <= new_y < W and matrix[new_x][new_y] == '.' and (new_x, new_y) not in visited:
                worklist.append((new_x, new_y))
                visited.add((new_x, new_y))
    



curr_label = 0
for x in range(0, H):
    for y in range(0, W):
        if matrix[x][y] == '.':
            bfs(x, y, curr_label)
            curr_label += 1






neighbours = []

for _ in range(0, curr_label):
    neighbours += [set()]

for x in range(H):
    for y in range(W):
        u = matrix[x][y]
        if u == '
        for dx in [-2, -1, 0, 1, 2]:
            for dy in [-2, -1, 0, 1, 2]:
                new_x = x + dx
                new_y = y + dy

                if 0 <= new_x < H and 0 <= new_y < W and matrix[new_x][new_y] != '
                    v = matrix[new_x][new_y]
                    if u == v: continue

                    neighbours[u].add(v)
                    neighbours[v].add(u)

Cx -= 1
Cy -= 1

Dx -= 1
Dy -= 1

source = matrix[Cx][Cy]
target = matrix[Dx][Dy]

import sys

if source == '
    print(-1)
    sys.exit(0)

visited = set([source])
frontier = set([source])

if target in frontier:
    print(0)
    sys.exit(0)



count = 1
while len(frontier):
    next_frontier = set()
    for u in frontier:
        for v in neighbours[u]:
            if v not in visited:
                visited.add(v)
                next_frontier.add(v)
    if target in next_frontier:
        print(count)
        count += 1
        sys.exit(0)

    count += 1
    frontier = next_frontier

print(-1)