Problem:
 Score : 400 points    Problem Statement A maze is composed of a grid of H \times W squares - H vertical, W horizontal.  The square at the i -th row from the top and the j -th column from the left - (i,j) - is a wall if S_{ij} is # and a road if S_{ij} is . .  There is a magician in (C_h,C_w) . He can do the following two kinds of moves:   Move A: Walk to a road square that is vertically or horizontally adjacent to the square he is currently in.  Move B: Use magic to warp himself to a road square in the 5\times 5 area centered at the square he is currently in.   In either case, he cannot go out of the maze.  At least how many times does he need to use the magic to reach (D_h, D_w) ?      Constraints  1 \leq H,W \leq 10^3  1 \leq C_h,D_h \leq H  1 \leq C_w,D_w \leq W  S_{ij} is # or . .  S_{C_h C_w} and S_{D_h D_w} are . .  (C_h,C_w) \neq (D_h,D_w)         Input Input is given from Standard Input in the following format:  H  W  C_h  C_w  D_h  D_w  S_{11}\ldots S_{1W}  \vdots  S_{H1}\ldots S_{HW}       Output Print the minimum number of times the magician needs to use the magic. If he cannot reach (D_h,D_w) , print -1 instead.        Sample Input 1 4 4
1 1
4 4
..#.
..#.
.#..
.#..      Sample Output 1 1  For example, by walking to (2,2) and then using the magic to travel to (4,4) , just one use of magic is enough.  Note that he cannot walk diagonally.       Sample Input 2 4 4
1 4
4 1
.##.
####
####
.##.      Sample Output 2 -1  He cannot move from there.       Sample Input 3 4 4
2 2
3 3
....
....
....
....      Sample Output 3 0  No use of magic is needed.       Sample Input 4 4 5
1 2
2 5
#.###
####.
#..##
#..##      Sample Output 4 2

Solution (Python):
from collections import deque

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

ch-=1
cw-=1
dh-=1
dw-=1

S=[]
for _ in range(h):
  s=input()
  sl=[]
  for i in range(w):
    sl.append(s[i])
  S.append(sl)

def isable(X):
  xh,xw=X[0],X[1]
  if 0<=xh<=h-1 and 0<=xw<=w-1 and S[xh][xw]=='.':
    return True
  else:
    return False

def stepA(X):
  xh,xw=X[0],X[1]
  A=[]
  for p,q in [(-1,0),(0,1),(1,0),(0,-1)]:
    if isable([xh+p,xw+q]):
      A.append([xh+p,xw+q])
  return A
    
def stepB(X):
  xh,xw=X[0],X[1]
  B=[]
  for i in range(-2,3):
    for j in range(-2,3):
      if i==0 and j==0:
        continue
      if isable([xh+i,xw+j]):
        B.append([xh+i,xw+j])
  return B

Q=deque()
Q.appendleft((ch,cw))
cost=[[float('inf') for i in range(w)] for j in range(h)]
cost[ch][cw]=0

while Q:
  ph,pw=Q.popleft()
  for v in stepA([ph,pw]):
    ah,aw=v[0],v[1]
    if isable([ah,aw]):
      if cost[ah][aw]>cost[ph][pw]:
        cost[ah][aw]=cost[ph][pw]
        Q.appendleft([ah,aw])
  for bh,bw in stepB([ph,pw]):
    if isable([bh,bw]):
      if cost[bh][bw]>cost[ph][pw]+1:
        cost[bh][bw]=cost[ph][pw]+1
        Q.append([bh,bw])

if cost[dh][dw]==float('inf'):
  print(-1)
else:
  print(cost[dh][dw])

Solution (Python):

INF = 10**9 + 7


def main():
    from collections import deque
    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())
    A = [input() for i in range(H)]

    def bfs_2d(c, sy, sx, gh, gw, H, W):
        que0 = deque()
        que1 = deque()
        dist = [[INF]*W for i in range(H)]

        dist[sy][sx] = 0
        que0.append((sy, sx))
        while que0 or que1:
            if que0:
                uh, uw = que0.popleft()
            else:
                uh, uw = que1.popleft()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    next_h = uh + dh
                    next_w = uw + dw
                    cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                    if not(0 <= next_h < H and 0 <= next_w < W):
                        continue
                    if c[next_h][next_w] == "
                        continue
                    if dist[next_h][next_w] > dist[uh][uw] + cost:
                        dist[next_h][next_w] = dist[uh][uw] + cost
                        if cost == 0:
                            que0.append((next_h, next_w))
                        else:
                            que1.append((next_h, next_w))
        return dist[gh][gw] if dist[gh][gw] != INF else -1

    ans = bfs_2d(A, Ch, Cw, Dh, Dw, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

INF = 10**9 + 7


def main():
    from collections import deque
    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())
    A = [input() for i in range(H)]

    def bfs_2d(c, sy, sx, gh, gw, H, W):
        que0 = deque()
        que1 = deque()
        dist = [[INF]*W for i in range(H)]

        dist[sy][sx] = 0
        que0.append((sy, sx))
        while que0 or que1:
            if que0:
                uh, uw = que0.popleft()
            else:
                uh, uw = que1.popleft()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    next_h = uh + dh
                    next_w = uw + dw
                    cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                    if not(0 <= next_h < H and 0 <= next_w < W):
                        continue
                    if c[next_h][next_w] == "
                        continue
                    if dist[next_h][next_w] > dist[uh][uw] + cost:
                        dist[next_h][next_w] = dist[uh][uw] + cost
                        if cost == 0:
                            que0.append((next_h, next_w))
                        else:
                            que1.append((next_h, next_w))
        return dist[gh][gw] if dist[gh][gw] != INF else -1

    ans = bfs_2d(A, Ch, Cw, Dh, Dw, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

INF = 10**9 + 7


def main():
    from collections import deque
    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())
    A = [input() for i in range(H)]

    def bfs_2d(c, sy, sx, gh, gw, H, W):
        que = deque()
        dist = [[INF]*W for i in range(H)]

        dist[sy][sx] = 0
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    next_h = uh + dh
                    next_w = uw + dw
                    cost = 0 if abs(dh) + abs(dw) <= 1 else 1
                    if not(0 <= next_h < H and 0 <= next_w < W):
                        continue
                    if c[next_h][next_w] == "
                        continue
                    if dist[next_h][next_w] > dist[uh][uw] + cost:
                        dist[next_h][next_w] = dist[uh][uw] + cost
                        if cost == 1:
                            que.append((next_h, next_w))
                        else:
                            que.appendleft((next_h, next_w))
        return dist[gh][gw] if dist[gh][gw] != INF else -1

    ans = bfs_2d(A, Ch, Cw, Dh, Dw, H, W)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import heapq

h, w = map(int, input().split())
sh, sw = map(lambda x: int(x) - 1, input().split())
gh, gw = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]

inf = 10 ** 10
D = [[inf] * w for i in range(h)]

D[sh][sw] = 0
Q = [(0, (sh, sw))]
heapq.heapify(Q)
while Q:
  _, (curr_h, curr_w) = heapq.heappop(Q)
  for di in range(-2, 3):
    for dj in range(-2, 3):
      next_h, next_w = curr_h + di, curr_w + dj
      if 0 <= next_h < h and 0 <= next_w < w and S[next_h][next_w] == ".":
        nex = int(abs(di) + abs(dj) != 1)
        if D[next_h][next_w] > D[curr_h][curr_w] + nex:
          D[next_h][next_w] = D[curr_h][curr_w] + nex
          heapq.heappush(Q, (D[next_h][next_w], (next_h, next_w)))
if D[gh][gw] >= inf:
  print(-1)
else:
  print(D[gh][gw])

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

    from builtins import max, min, range

    INF = 10 ** 6

    H, W = map(int, readline().split())
    C1, C2 = map(lambda x: int(x) - 1, readline().split())
    D1, D2 = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]



    t = [[INF]*W for _ in range (H)]


    for h in range (H):
        Sh = S[h]
        th = t[h]
        for w in range (W):
            if Sh[w] == '
                th[w] = -1


    q = deque([(C1,C2)])
    a = 0
    t[C1][C2] = a

    while q:
        warpq = []
        while q:
            h,w = q.popleft()
            warpq.append((h,w))
            if 0 < h and t[h-1][w] > a:
                t[h-1][w] = a
                q.append((h-1,w))
            if H-1 > h and t[h+1][w] > a:
                t[h+1][w] = a
                q.append((h+1,w))
            if 0 < w and t[h][w-1] > a:
                t[h][w-1] = a
                q.append((h,w-1))
            if w < W-1 and t[h][w+1] > a:
                t[h][w+1] = a
                q.append((h,w+1))

        if t[D1][D2]!= INF:
            break

        a+=1

        for h,w in warpq:
            for i in range (max(0,h-2),min(H,h+3)):
                ti = t[i]
                for j in range (max(0,w-2),min(W,w+3)):
                    if ti[j] >a:
                        ti[j] = a
                        q.append((i,j))


    if t[D1][D2] == INF:
        print(-1)
    else:
        print(t[D1][D2])

main()

Solution (Python):
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

LARGEST = 999999999
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = [LARGEST] * W
        status.append(tmp)

    q = deque()

    q.append((c0, c1, 0))

    while len(q) > 0:
        hIndex, wIndex, index = q.popleft()

        if index > status[hIndex][wIndex]:
            continue

        sss = [(hIndex, wIndex - 1), (hIndex, wIndex + 1), (hIndex - 1, wIndex), (hIndex + 1, wIndex)]

        for sH, sW in sss:
            if sH < 0 or sH >= h or sW < 0 or sW >= w:
                continue

            if arr[sH][sW] == '
                continue

            tmpIndex = index
            if status[sH][sW] > tmpIndex:
                status[sH][sW] = tmpIndex
                q.insert(0, (sH, sW, tmpIndex))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex < 0) or (_hIndex >= h) or (_wIndex < 0) or (_wIndex >= w):
                    continue

                if arr[_hIndex][_wIndex] == '
                    continue

                tmpIndex = index + 1

                if status[_hIndex][_wIndex] > tmpIndex:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex, tmpIndex))

    if status[d0][d1] == LARGEST:
        print(-1)
    else:
        print(status[d0][d1])


calculate(H, W, C0, C1, D0, D1, ARR)

Solution (Python):
from collections import deque

H, W = map(int, input().split())
C0, C1 = map(int, input().split())
D0, D1 = map(int, input().split())

LARGEST = 999999999
ARR = []

for i in range(H):
    ARR.append(input())


def calculate(h, w, c0, c1, d0, d1, arr):
    c0 = c0 - 1
    c1 = c1 - 1
    d0 = d0 - 1
    d1 = d1 - 1

    status = []
    for i in range(H):
        tmp = [LARGEST] * W
        status.append(tmp)

    status[c0][c1] = 0
    q = deque()

    q.append((c0, c1))

    while len(q) > 0:
        hIndex, wIndex = q.popleft()


        sss = [(hIndex, wIndex - 1), (hIndex, wIndex + 1), (hIndex - 1, wIndex), (hIndex + 1, wIndex)]

        for sH, sW in sss:
            if sH < 0 or sH >= h or sW < 0 or sW >= w:
                continue

            if arr[sH][sW] == '
                continue

            if status[sH][sW] > status[hIndex][wIndex]:
                status[sH][sW] = status[hIndex][wIndex]
                q.insert(0, (sH, sW))

        for _hIndex in range(hIndex - 2, hIndex + 3):
            for _wIndex in range(wIndex - 2, wIndex + 3):
                if (_hIndex < 0) or (_hIndex >= h) or (_wIndex < 0) or (_wIndex >= w):
                    continue

                if arr[_hIndex][_wIndex] == '
                    continue

                tmpIndex = status[hIndex][wIndex]+1
                if status[_hIndex][_wIndex] > tmpIndex:
                    status[_hIndex][_wIndex] = tmpIndex
                    q.append((_hIndex, _wIndex))

    if status[d0][d1] == LARGEST:
        print(-1)
    else:
        print(status[d0][d1])


calculate(H, W, C0, C1, D0, D1, ARR)

Solution (Python):
from collections import deque


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

    from builtins import max, min, range

    INF = 10 ** 6

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

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    a = 0
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        a += 1
        for h, w in warpq:
            for i in range(max(0, h - 2), min(H, h + 3)):
                ti = t[i]
                for j in range(max(0, w - 2), min(W, w + 3)):
                    if ti[j] > a:
                        ti[j] = a
                        q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()

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 = [[-1] * W for _ in range(H)]
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    wark = collections.deque([[Ch - 1, Cw - 1]])
    warp = collections.deque([])

    visited[Ch - 1][Cw - 1] = 0
    while wark:
        h, w = wark.popleft()
        warp.append((h, w))
        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] = visited[h][w]
                wark.append([ch, cw])
        if len(wark) == 0:
            while warp:
                h, w = warp.popleft()
                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] = visited[h][w] + 1
                            wark.append([ch, cw])

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


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
import copy
H,W=map(int, input().split())
Ch,Cw=map(int, input().split())
Dh,Dw=map(int, input().split())
S=[list(str(input())) for i in range(H)]

field2=copy.deepcopy(S)
move=[[1,0],[-1,0],[0,1],[0,-1]]
ans=0
temp=deque()

def dfs2(x,y):
    field2[x][y]='
    temp.append([x,y])
    for i in range(4):
        nx=x+move[i][0]
        ny=y+move[i][1]
        if 0<=nx and nx<H and 0<=ny and ny<W and field2[nx][ny]=='.':
            dfs2(nx,ny)
    return temp

start=dfs2(Ch-1,Cw-1)

while True:
    if field2[Dh-1][Dw-1]=='
        print(ans)
        exit()
    else:
        for i in range(len(start)):
            ttemp=start.popleft()
            for hh in range(-2,3):
                for ww in range(-2,3):
                    nnx=ttemp[0]+hh
                    nny=ttemp[1]+ww
                    if 0<=nnx and nnx<H and 0<=nny and nny<W and field2[nnx][nny]=='.':
                        dfs2(nnx,nny)
        ans+=1
    if len(start)==0:
        print(-1)
        exit()

Solution (Python):
from queue import Queue
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())

S = []
for _ in range(H):
    S.append(list(input()))

path = dict()
cache = set()

Score = [[-1 for _ in range(W)] for __ in range(H)]

Cur = (Cw-1, Ch-1)
Q = deque()
Q.appendleft(Cur)
Score[Cur[1]][Cur[0]] = 0


G = (Dw-1, Dh-1)

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

wdx = []
wdy = []

while not len(Q) == 0:

    node = Q.popleft()
    cx, cy = node

    
    for di in range(4):
        nx = cx + dx[di]
        ny = cy + dy[di]

        if W > nx >= 0 and H > ny >= 0 and S[ny][nx] == '.' and (Score[ny][nx] == -1 or Score[ny][nx] > Score[cy][cx]):
            nt = (nx, ny)
            Q.appendleft(nt)
            Score[ny][nx] = Score[cy][cx]
    
    
    for wdx in range(-2, 3, 1):
        for wdy in range(-2, 3, 1):
            if wdx == wdy == 0:
                continue

            nx = cx + wdx
            ny = cy + wdy
            nt = (nx, ny)

            if W > nx >= 0 and H > ny >= 0 and S[ny][nx] == '.' and (Score[ny][nx] == -1 or Score[ny][nx] > Score[cy][cx] + 1):
                nt = (nx, ny)
                Q.append(nt)
                Score[ny][nx] = Score[cy][cx] + 1

print(Score[G[1]][G[0]])

Solution (Python):
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
from math import ceil, log, floor, sqrt
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]


def valid(a, b):
    return 0 <= a < n and 0 <= b < m


n, m = sp()
sx, sy = sp()
ex, ey = sp()
sx -= 1
sy -= 1
ex -= 1
ey -= 1
mat = [data() for i in range(n)]
inf = 10 ** 10
q = deque()
q.append([sx, sy])
x, y = [-1, 1, 0, 0], [0, 0, -1, 1]
jump = [[inf] * m for _ in range(n)]
jump[sx][sy] = 0
while q:
    sx, sy = q.popleft()
    for i in range(4):
        tx, ty = sx + x[i], sy + y[i]
        if valid(tx, ty) and mat[tx][ty] == ".":
            if jump[tx][ty] > jump[sx][sy]:
                q.appendleft([tx, ty])
                jump[tx][ty] = jump[sx][sy]
    for i in range(-2, 3):
        for j in range(-2, 3):
            tx, ty = sx + i, sy + j
            if valid(tx, ty) and mat[tx][ty] == ".":
                if jump[tx][ty] > jump[sx][sy] + 1:
                    q.append([tx, ty])
                    jump[tx][ty] = jump[sx][sy]+1
if jump[ex][ey] == 10 ** 10:
    print(-1)
    exit()
print(jump[ex][ey])

Solution (Python):
from heapq import *
import sys; input = sys.stdin.readline
inf = int(1e10)
n, m = map(int, input().split())
x, y = map(int, input().split())
dx, dy = map(int, input().split())
x, y, dx, dy = x-1, y-1, dx-1, dy-1
matrix = [list(input().strip()) for _ in range(n)]
v = [[inf for _ in range(m)] for _ in range(n)]
moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def valid(x, y): return (0<=x<n) and (0<=y<m) and (matrix[x][y] != '
v[x][y] = 0
q = [(0, (x, y))]
while q:
	d, node = heappop(q)
	for i in moves:
		xx, yy = node[0]+i[0], node[1]+i[1]
		if valid(xx, yy) and v[xx][yy] > d:
			v[xx][yy] = d
			heappush(q, (v[xx][yy], (xx, yy)))
	for i in range(node[0]-2, node[0]+3):
		for j in range(node[1]-2, node[1]+3):
			if valid(i, j) and v[i][j] > d + 1:
				v[i][j] = d + 1
				heappush(q, (v[i][j], (i, j)))
if v[dx][dy] == inf: print(-1)
else: print(v[dx][dy])

Solution (Python):
from collections import deque

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

c=[]
for i in [0]*H:
    c.append(input())

dic=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dic.append((i,j))
    
INF=10**9
vis=[[INF]*W for _ in [0]*H]

q=deque()
q.appendleft((sx,sy))
vis[sy][sx]=0
res=-1
while q:
    x,y=q.popleft()
    if (x,y)==(gx,gy):
        res=vis[y][x]
    for dx,dy in dic:
        nx,ny=x+dx,y+dy
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if vis[ny][nx]>vis[y][x] and c[ny][nx]!='
                if dx**2+dy**2<2:
                    vis[ny][nx]=vis[y][x]
                    q.appendleft((nx,ny))
                else:
                    vis[ny][nx]=vis[y][x]+1
                    q.append((nx,ny))
        if res>-1:
            break
    if res>-1:
            break
                
print(res)

Solution (Python):
INF = 10**9 + 7


def main():
    from heapq import heappop, heappush
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]

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

    if dist[Dh][Dw] == INF:
        print(-1)
    else:
        print(dist[Dh][Dw])

    
    


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque


h, w = map(int, input().split())
Ch, Cw = map(lambda x: int(x)-1, input().split())
Dh, Dw = map(lambda x: int(x)-1, input().split())
dy, dx = (-1, 0, 1, 0), (0, -1, 0, 1)
maze = [[float('inf') if x == '.' else -float('inf') for x in input()] for _ in range(h)]
maze[Ch][Cw] = 0
que = deque()
que.append((0, Ch, Cw))
while que:
    c, y, x = que.popleft()
    
    if c > maze[y][x]:
        continue
    
    if y == Dh and x == Dw:
        break
    
    for i in range(4):
        y2, x2 = y + dy[i], x + dx[i]
        if 0 <= y2 < h and 0 <= x2 < w and c < maze[y2][x2]:
            maze[y2][x2] = c
            que.appendleft((c, y2, x2))
            
    for i in range(-2, 3):
        for j in range(-2, 3):
            y3, x3, c2 = y + i, x + j, c+1
            if 0 <= y3 < h and 0 <= x3 < w and c2 < maze[y3][x3]:
                maze[y3][x3] = c2
                que.append((c2, y3, x3))

ans = maze[Dh][Dw]
if ans == float('inf'):
    print(-1)
else:
    print(ans)

Solution (Python):
import heapq

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; 

s = []
for _ in range(H):
    s.append(list(input()))
cs = [[1000000 for _ in range(W)] for _ in range(H)]

q = []
heapq.heappush(q, (0, (ch, cw)))

while q:
    c, (h, w) = heapq.heappop(q)
    if cs[h][w] < c:
        continue
    cs[h][w] = c
    for nh, nw in [(h - 1, w), (h + 1, w), (h, w - 1), (h, w + 1)]:
        if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c < cs[nh][nw]:
            cs[nh][nw] = c
            heapq.heappush(q, (c, (nh, nw)))
    for nh in range(h - 2, h + 3):
        for nw in range(w - 2, w + 3):
            if 0 <= nh < H and 0 <= nw < W and s[nh][nw] == '.' and c + 1 < cs[nh][nw]:
                cs[nh][nw] = c + 1
                heapq.heappush(q, (c + 1, (nh, nw)))

print(-1 if cs[dh][dw] == 1000000 else cs[dh][dw])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w = LI()
sy, sx = LI()
gy, gx = LI()
sy -= 1
sx -= 1
gy -= 1
gx -= 1
maze = [input() for _ in range(h)]
dist = [[inf] * w for _ in range(h)]
que = deque([(sy, sx)])
dist[sy][sx] = 0
while que:
    y, x = que.popleft()
    for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]):
        ny, nx = y + dy, x + dx
        if 0 <= ny < h and 0 <= nx < w:
            if maze[ny][nx] == '.' and dist[ny][nx] > dist[y][x]:
                dist[ny][nx] = dist[y][x]
                que.appendleft((ny, nx))
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            ny, nx = y + dy, x + dx
            if 0 <= ny < h and 0 <= nx < w:
                if maze[ny][nx] == '.' and dist[ny][nx] > dist[y][x] + 1:
                    dist[ny][nx] = dist[y][x] + 1
                    que.append((ny, nx))
if dist[gy][gx] == inf:
    print(-1)
else:
    print(dist[gy][gx])

Solution (Python):
from collections import deque

H, W = [int(s) for s in input().split()]
Ch, Cw = [int(s) - 1 for s in input().split()]
Dh, Dw = [int(s) - 1 for s in input().split()]

fields = [list(input()) for _ in range(H)]
fields_num = [[-1] * W for _ in range(H)]
ok_field = '.'


def get_search_obj(i, j):
    ret = []
    moving_range = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    for dx, dy in moving_range:
        if 0 <= i + dx <= (H - 1) and 0 <= j + dy <= (W - 1) and fields[i + dx][j + dy] == ok_field:
            ret.append((i + dx, j + dy))
    return ret


def get_search_obj_cost2(i, j):
    ret = []
    moving_range = ((x, y) for x in range(- 2, 3) for y in range(- 2, 3))
    for dx, dy in moving_range:
        if 0 <= i + dx <= (H - 1) and 0 <= j + dy <= (W - 1) and fields[i + dx][j + dy] == ok_field:
            ret.append((i + dx, j + dy))
    return ret


def bfs(sx, sy):
    start = ((sx, sy), 0)
    dq = deque([start])
    visited = [[False] * W for _ in range(H)]
    while dq:
        (sx, sy), cost = dq.pop()
        if (sx, sy) == (Dh, Dw):
            return cost
        if visited[sx][sy]:
            continue
        else:
            visited[sx][sy] = True
        for x, y in get_search_obj(sx, sy):
            dq.append(((x, y), cost))
        for x, y in get_search_obj_cost2(sx, sy):
            dq.appendleft(((x, y), cost + 1))
    return -1


print(bfs(Ch, Cw))

Solution (Python):
INF=10**20
from heapq import heappop,heappush,heapify
def dijkstra(G,H,W,sh,sw):
    dx=[1,0,-1,0]
    dy=[0,1,0,-1]
    que=[(0,sh*10000+sw)]
    dist=[[INF]*W for i in range(H)]
    dist[sh][sw]=0
    while que:
        mincost,u=heappop(que)
        h,w=u//10000,u%10000
        if(mincost>dist[h][w]):
            continue
        for di in range(4):
            nh=h+dx[di]
            nw=w+dy[di]
            if(nh>H-1 or nh<0 or nw>W-1 or nw<0):
                continue
            if(G[nh][nw]=='
                continue
            if(dist[h][w]<dist[nh][nw]):
                dist[nh][nw]=dist[h][w]
                heappush(que,(dist[nh][nw],nh*10000+nw))
        for nh in range(h-2,h+3):
            for nw in range(w-2,w+3):
                if (nh>H-1 or nh<0 or nw>W-1 or nw<0):
                    continue
                if(G[nh][nw]=='
                    continue
                if dist[h][w]+1<dist[nh][nw]:
                    dist[nh][nw]=dist[h][w]+1
                    heappush(que,(dist[nh][nw],nh*10000+nw))
    return dist

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())
G=[tuple(input()) for i in range(H)]
dist=dijkstra(G,H,W,Ch,Cw)
ans=dist[Dh][Dw]
if ans!=INF:
    print(ans)
else:
    print(-1)