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 = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["
maze.append(["
for i in range(H):
    row = ["
    row.extend(list(input()))
    row.append("
    row.append("
    maze.append(row)
maze.append(["
maze.append(["
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                maze[ny][nx] = "
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = warp[y][x]+1
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])

Solution (Python):
from collections import defaultdict as dd
H, W = map(int, input().split())
Cy, Cx = map(int, input().split())
Dy, Dx = map(int, input().split())
M = [['

num_groups = 0
for y in range(2, H+2):
    L = M[y]
    for x in range(2, W+2):
        if L[x] == '.':
            q = [[y, x]]
            while q:
                ty, tx = q.pop()
                M[ty][tx] = num_groups
                if M[ty-1][tx] == '.':
                    q.append([ty-1, tx])
                if M[ty+1][tx] == '.':
                    q.append([ty+1, tx])
                if M[ty][tx-1] == '.':
                    q.append([ty, tx-1])
                if M[ty][tx+1] == '.':
                    q.append([ty, tx+1])
            num_groups += 1 

ds = [[-2,0], [-2,1], [-1,1], [-2,2], [-1,2], [2,0], [1,1], [2,1], [0,2], [1,2], [2,2]]
edges = dd(dict)
for y in range(2, H+2):
    for x in range(2, W+2):
        f = M[y][x]
        if f != '
            for dy, dx in ds:
                t = M[y+dy][x+dx]
                if t != '
                    edges[f][t] = edges[t][f] = 1

start = M[Cy+2-1][Cx+2-1]
goal = M[Dy+2-1][Dx+2-1]
q = set([start])
visited = [False] * num_groups
visited[start] = True
ans = 0
while q:
    nq = set()
    for p in q:
        if p == goal:
            print(ans)
            exit()
        for t in edges[p].keys():
            if not visited[t]:
                nq.add(t)
                visited[t] = True
    q = nq
    ans += 1

print(-1)

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20

MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    h, w = ns()
    ch, cw = ns()
    ch, cw = ch - 1, cw - 1
    dh, dw = ns()
    dh, dw = dh - 1, dw - 1

    map = [list(input()) for _ in range(h)]

    table = [[-1 for _ in range(w)] for __ in range(h)]
    group = {}

    pos = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    cnt = -1
    for i in range(h):
        for j in range(w):
            if map[i][j] == "." and table[i][j] == -1:
                cnt += 1
                group[cnt] = [[i, j]]
                que = collections.deque()
                que.append([i, j])
                table[i][j] = cnt

                while que:
                    y, x = que.popleft()
                    for py, px in pos:
                        ty = y + py
                        tx = x + px
                        if 0 <= ty < h and 0 <= tx < w:
                            if map[ty][tx] == "." and table[ty][tx] == -1:
                                table[ty][tx] = cnt
                                que.append([ty, tx])
                                group[cnt].append([ty, tx])

    ini_group = table[ch][cw]
    req_group = table[dh][dw]
    done_group = set()
    done_group.add(ini_group)

    nxt = {ini_group}
    ans = 0

    while len(nxt):
        if req_group in done_group:
            break

        tmp = []
        for nxti in nxt:
            tmp.extend(group[nxti])
        que = collections.deque(tmp)

        nxt = set()
        for _ in range(len(que)):
            y, x = que.popleft()
            for py in range(-2, 3):
                for px in range(-2, 3):
                    if i == 0 and j == 0:
                        continue
                    ty = y + py
                    tx = x + px
                    if 0 <= ty < h and 0 <= tx < w:
                        if table[ty][tx] != -1 and table[ty][tx] not in done_group:
                            nxt.add(table[ty][tx])
                            done_group.add(table[ty][tx])

        ans += 1

    print(ans if req_group in done_group else -1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

def bfs(sx, sy, gx, gy):
    dist = [[-1] * w for _ in range(h)]
    dist[sx][sy] = 0
    q = deque()
    r = deque()
    q.append([sx, sy])
    while True:
        if not q:
            while r:
                x, y = r.popleft()
                for i in range(-2, 3):
                    for j in range(-2, 3):
                        xx, yy = x + i, y + j
                        if 0 <= xx < h and 0 <= yy < w:
                            if s[xx][yy] == "." and dist[xx][yy] == -1:
                                dist[xx][yy] = dist[x][y] + 1
                                q.append([xx, yy])
        if not q:
            return dist[gx][gy]
        x, y = q.popleft()
        r.append([x, y])
        for u in v:
            xx, yy = x + u[0], y + u[1]
            if 0 <= xx < h and 0 <= yy < w:
                if s[xx][yy] == "." and dist[xx][yy] == -1:
                    dist[xx][yy] = dist[x][y]
                    q.append([xx, yy])
    return dist[gx][gy]

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)]
v = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = bfs(ch - 1, cw - 1, dh - 1, dw - 1)
print(ans)

Solution (Python):
from collections import *
H,W=map(int,input().split())
CH,CW=map(int,input().split())
CH,CW=CH-1,CW-1
DH,DW=map(int,input().split())
DH,DW=DH-1,DW-1
S=[input() for i in range(H)]
Q=deque()
INF=10**9
D=[[INF]*W for i in range(H)]
D[CH][CW]=0
Q.append((CH,CW))
w4x=[[0,1,0,-1],[]]
w4y=[[1,0,-1,0],[]]
for i in range(5):
  for j in range(5):
    if abs(i-2)+abs(j-2)<=1:
      continue
    w4x[1].append(i-2)
    w4y[1].append(j-2)
v=0
w=0
d=0
while len(Q):
  v=Q.popleft()
  for j in range(2):
    for i in range(len(w4x[j])):
      w=(v[0]+w4y[j][i],v[1]+w4x[j][i])
      if min(w)<0 or w[0]>=H or w[1]>=W:
        continue
      if S[w[0]][w[1]]=='
        continue
      d=D[v[0]][v[1]]+j
      if D[w[0]][w[1]]>d:
        D[w[0]][w[1]]=d
        if j:
          Q.append(w)
        else:
          Q.appendleft(w)
if D[DH][DW]==INF:
  print(-1)
else:
  print(D[DH][DW])

Solution (Python):
INF = 10**18

def main():

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

    M = [str(input()) for _ in range(h)]
    
    

    from collections import deque
    q = deque()
    q.append((ch, cw))

    visit = [[-1]*w for _ in range(h)]
    visit[ch][cw] = 0
    C = [[INF]*w for _ in range(h)]
    C[ch][cw] = 0

    import itertools
    cnt = 0
    while q:
        y, x = q.popleft()
        
            
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                
                if C[ny][nx] != C[y][x] and M[ny][nx] != '
                    visit[ny][nx] = visit[y][x]
                    C[ny][nx] = min(C[y][x], C[ny][nx])
                    q.appendleft((ny, nx))
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0:
                    continue
                ny, nx = y+dy, x+dx
                if 0 <= ny < h and 0 <= nx < w:
                    
                    if visit[ny][nx] == -1 and M[ny][nx] != '
                        visit[ny][nx] = visit[y][x]
                        C[ny][nx] = min(C[y][x]+1, C[ny][nx])
                        q.append((ny, nx))
    
    
    if visit[dh][dw] == -1:
        print(-1)
    else:
        print(C[dh][dw])

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H,W = map(int,input().split())
CH,CW = map(int,input().split())
CH-=1
CW-=1
DH,DW = map(int,input().split())
DH-=1
DW-=1
S = [0]*H
hoge = 0
for i in range(H):
    S[i] = [-1]*W
    hoge = input()
    for j in range(W):
        if hoge[j] == ".":
            S[i][j] = 10000000

DDD = [0]*25
dddd = 0
for dx in (-2,-1,0,1,2):
    for dy in (-2,-1,0,1,2):
        DDD[dddd] = (dx,dy,dx * dx + dy * dy)
        dddd += 1

D = deque()
D.append((CH,CW,0))
S[CH][CW] = 0
while len(D):
    X,Y,DD = D.pop()
    for dx,dy,a in DDD:
        XX = X + dx
        YY = Y + dy
        if a == 0 or not(0<=XX<H) or not(0<=YY<W) or S[XX][YY] == -1:
            continue
        elif a == 1 and S[XX][YY] > DD:
            D.append((XX,YY,DD))
            S[XX][YY] = DD
        elif S[XX][YY] > DD + 1:
            D.appendleft((XX,YY,DD+1))
            S[XX][YY] = DD + 1

print(-1 if S[DH][DW] == 10000000 else S[DH][DW])

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

S = ['
for h in range(2, H+2):
    S[h] = '

T = [[-1]*(W+4) for _ in range(H+4)]

f = 0
for h in range(2,H+2):
    for w in range(2,W+2):
        if S[h][w]=='
        
        queue = [(h,w)]
        iq = 0
        while iq<len(queue):
            ph, pw = queue[iq]
            iq += 1

            if S[ph][pw]=='
            
            T[ph][pw] = f
            queue.append((ph+1,pw  ))
            queue.append((ph-1,pw  ))
            queue.append((ph  ,pw+1))
            queue.append((ph  ,pw-1))

        f += 1

P = [set() for _ in range(f)]
    
for h in range(2,H+2):
    for w in range(2,W+2):
        f = T[h][w]
        if f==-1: continue
        for h2 in range(h-2, h+3):
            for w2 in range(w-2, w+3):
                f2 = T[h2][w2]
                if f2==-1: continue
                if f!=f2: P[f].add(f2)

N = [-1]*len(P)
queue = [(T[Ch+1][Cw+1], 0)]
iq = 0
while iq<len(queue):
    f, n = queue[iq]
    iq += 1

    if N[f]!=-1: continue

    N[f] = n
    for f2 in P[f]: queue.append((f2, n+1))

print(N[T[Dh+1][Dw+1]])

Solution (Python):


import os,sys
from io import BytesIO, IOBase
from collections import deque,defaultdict

def main():
    h,w = map(int,input().split())
    x1,y1 = map(int,input().split())
    a1,b1 = map(int,input().split())
    arr = [list(input().strip()) for _ in range(h)]
    dp = [[0]*w for _ in range(h)]
    se = set()
    for i in range(h):
        for j in range(w):
            if arr[i][j] != '
                se.add((i,j))
    reg = 1
    while len(se):
        x = se.pop()
        curr = deque([x])
        while len(curr):
            y = curr.popleft()
            z = (y[0]+1,y[1])
            dp[y[0]][y[1]] = reg
            if z[0]<h and z[1]<w and z in se and arr[z[0]][z[1]] != '
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
            z = (y[0],y[1]+1)
            if z[0] < h and z[1] < w and z in se and arr[z[0]][z[1]] != '
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
            z = (y[0]-1, y[1])
            if z[0] >= 0 and z[1] >= 0 and z in se and arr[z[0]][z[1]] != '
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
            z = (y[0],y[1] - 1)
            if z[0] >= 0 and z[1] >= 0 and z in se and arr[z[0]][z[1]] != '
                curr.append(z)
                se.remove(z)
                dp[z[0]][z[1]] = reg
        reg += 1
    path = defaultdict(set)
    for i in range(h):
        for j in range(w):
            if arr[i][j] == '
                continue
            for r in range(-2,3):
                for q in range(-2,3):
                    if 0<=i+r<h and 0<=j+q<w and dp[i][j] != dp[i+r][j+q] and dp[i+r][j+q]:
                        path[dp[i][j]].add(dp[i+r][j+q])
    st = dp[x1-1][y1-1]
    en = dp[a1-1][b1-1]
    curr = deque([st])
    visi = {st}
    ans=fl=0
    val = 1
    tar = 0
    val1 = 0
    while len(curr):
        x = curr.popleft()
        tar += 1
        if x == en:
            fl = 1
            break
        for i in path[x]:
            if i not in visi:
                visi.add(i)
                curr.append(i)
                val1 += 1
        if tar == val:
            tar = 0
            val = val1
            val1 = 0
            ans += 1
    if fl:
        print(ans)
    else:
        print(-1)



BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque
h,w = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())
maze =["
temp = [[-1]*(w+4) for i in range(h+4)]


q = deque([(sy+1,sx+1)])
temp[sy+1][sx+1] = 0

opt = [(0,1),(0,-1),(1,0),(-1,0)]
while q:
    y,x = q.popleft()
    
    for i in opt:
        ty,tx = y+i[0],x+i[1]
        if maze[ty][tx] == "
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x]
            q.appendleft((ty,tx))
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i,x+j
            if maze[ty][tx] == "
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] = temp[y][x]+1
                q.append((ty,tx))

    


print(temp[gy+1][gx+1])

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)









INF = 1 << 50

def bfs(MAZE, start, goal):
    MAP = [[INF] * len(MAZE[0]) for _ in range(len(MAZE))]
    walks = [(0,1), (1,0), (-1,0), (0, -1)]
    warps = []
    for i in range(-2, 3):
        for j in range(-2, 3):
            if i == 0 and j == 0: continue
            if not (i,j) in walks:
                warps.append((i, j))
    queue = []
    k = (0,) + start
    heappush(queue, k)

    
    



    while queue:
        count, ci, cj = heappop(queue)
        if (ci, cj) == goal:
            return count
        for ii, jj in walks:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count:
                heappush(queue, (count, ni, nj))
                MAP[ni][nj] = count
        for ii, jj in warps:
            ni, nj = ci + ii, cj + jj
            if MAZE[ni][nj] == '.' and MAP[ni][nj] > count + 1:
                heappush(queue, (count+1, ni, nj))
                MAP[ni][nj] = count + 1

    return -1


def run():
    H, W = map(int, sysread().split())
    Ci, Cj = map(int, sysread().split())
    Ci += 1
    Cj += 1
    Di, Dj = map(int, sysread().split())
    Di += 1
    Dj += 1
    MAZE = []
    MAZE.append('
    MAZE.append('
    for i in range(H):
        s = input()
        s = '
        MAZE.append(s)
    MAZE.append('
    MAZE.append('
    print(bfs(MAZE, (Ci, Cj), (Di, Dj)))





if __name__ == "__main__":
    run()

Solution (Python):

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())
X = [input() for _ in range(H)]

inf = 10 ** 9
dist = [[inf] * W for _ in range(H)]
dist[C_h - 1][C_w - 1] = 0
q1 = deque()
q1.append((C_h - 1, C_w - 1))
q2 = deque()


def bfs_1():
    while q1:
        u, v = q1.popleft()
        q2.append((u, v))
        for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            if (0 <= u + i < H and 0 <= v + j < W
                    and X[u + i][v + j] == "."
                    and dist[u + i][v + j] > dist[u][v]):
                dist[u + i][v + j] = dist[u][v]
                q1.append((u + i, v + j))
                q2.append((u + i, v + j))


def bfs_2():
    while q2:
        u, v = q2.popleft()
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (0 <= u + i < H and 0 <= v + j < W
                        and X[u + i][v + j] == "."
                        and dist[u + i][v + j] > dist[u][v] + 1):
                    dist[u + i][v + j] = dist[u][v] + 1
                    q1.append((u + i, v + j))


while q1 or q2:
    bfs_1()
    bfs_2()

if dist[D_h - 1][D_w - 1] < inf:
    print(dist[D_h - 1][D_w - 1])
else:
    print(-1)

Solution (Python):
import queue
h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
s=[input() for _ in range(h)]
q=queue.deque([[sy-1,sx-1]])
q2=[[sy-1,sx-1]]
q3=[]
inf=10**7
dist=[[inf for _ in range(w)] for _ in range(h)]
d=[[1,0],[0,1],[-1,0],[0,-1]]
dist[sy-1][sx-1]=0

while q:
    y,x=q.pop()
    for dy,dx in d:
        ny,nx=y+dy,x+dx
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='
            dist[ny][nx]=min(dist[y][x],dist[ny][nx])
            q.append([ny,nx])
            q2.append([ny,nx])
    if not q:
        for y,x in q2:
            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 and s[ny][nx]!='
                        dist[ny][nx]=min(dist[y][x]+1,dist[ny][nx])
                        q.append([ny,nx])
                        q3.append([ny,nx])
        q2=q3
        q3=[]
print(dist[gy-1][gx-1] if dist[gy-1][gx-1]!=inf else -1)

Solution (Python):
from collections import deque

h, w = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
Dh, Dw = map(int, input().split())
Dh -= 1
Dw -= 1
s = []
for _ in range(h):
    s.append(list(input()))

def is_valid_point(ph, pw):
    if 0 <= ph < h and 0 <= pw < w and s[ph][pw] == '.':
        return True
    else:
        return False

dh = (1, 0, -1, 0)
dw = (0, 1, 0, -1)

inf = 10 ** 18
dist = [[inf] * w for _ in range(h)]
dist[ch][cw] = 0

q = deque([(ch, cw)])
while q:
    ph, pw = q.popleft()
    for k in range(4):
        nh, nw = ph + dh[k], pw + dw[k]
        if is_valid_point(nh, nw):
            if dist[ph][pw] < dist[nh][nw]:
                dist[nh][nw] = dist[ph][pw]
                q.appendleft((nh, nw))
    for nh in range(ph - 2, ph + 3):
        for nw in range(pw - 2, pw + 3):
            if is_valid_point(nh, nw):
                if dist[ph][pw] + 1 < dist[nh][nw]:
                    dist[nh][nw] = dist[ph][pw] + 1
                    q.append((nh, nw))

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

Solution (Python):
from collections import deque

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

l = [list(input()) for i in range(h)]

dp = [[float("INF")]*w for i in range(h)]

dp[sx][sy] = 0

q = deque([])
q.append([sx,sy])
dx = [0,0,1,-1]
dy = [1,-1,0,0]
count = 0
while True:
    cq = []
    while q:
        x,y = q.popleft()
        cq.append((x,y))
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < h and 0 <= ny < w and l[nx][ny] == "." and dp[nx][ny] > count:
                dp[nx][ny] = count
                q.append([nx,ny])
    if dp[gx][gy] < float("INF"):
        print(dp[gx][gy])
        exit()
    count += 1
    if len(cq) == 0:
        break
    for x,y in cq:
        for i in range(-2,3):
            for j in range(-2,3):
                nx = x+i
                ny = y+j
                if 0 <= nx < h and 0 <= ny < w and l[nx][ny] == "." and dp[nx][ny] > count:
                    dp[nx][ny] = count
                    q.append([nx,ny])

if dp[gx][gy] == float("INF"):
    print(-1)

Solution (Python):
DESTINATION = [(1, 0), (0, 1), (-1, 0), (0, -1)]


class UnionFindTree():
    def __init__(self, N):
        self.N = N
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(self.N):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


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)]
    distance = [[float("inf")] * W for _ in range(H)]
    stack = [[Ch, Cw]]
    cost = 0
    while len(stack):
        visited = set()
        while len(stack):
            h, w = stack.pop()
            visited.add((h, w))
            for dh, dw in DESTINATION:
                nh, nw = h + dh, w + dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and distance[nh][nw] == float("inf"):
                    stack.append([nh, nw])
                    distance[nh][nw] = cost
        for h, w in visited:
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and distance[nh][nw] == float("inf"):
                        stack.append([nh, nw])
                        distance[nh][nw] = cost + 1
        cost += 1
    if distance[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(distance[Dh][Dw])


if __name__ == "__main__":
    main()

Solution (Python):
from heapq import heappush, heappop

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

grid = []
for _ in range(H):
	grid.append(list(c == "." for c in input().strip()))

m = H * W + 1
smallests = [[m] * W for _ in range(H)]

queue_move = [(0, Cw, Ch)]
queue_warp = [(0, Cw, Ch)]
smallests[Ch][Cw] = 0

def calc():
	while queue_move or queue_warp:
		if queue_move:
			d, x, y = heappop(queue_move)
			if d == smallests[y][x]:
				for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
					tx = x + dx
					ty = y + dy
					if tx >= 0 and tx < W and ty >= 0 and ty < H:
						if grid[ty][tx] and d < smallests[ty][tx]:
							smallests[ty][tx] = d
							heappush(queue_move, (d, tx, ty))
							heappush(queue_warp, (d, tx, ty))
		else:
			d, x, y = heappop(queue_warp)
			if d == smallests[y][x]:
				d += 1
				for tx in range(max(0, x - 2), min(W, x + 3)):
					for ty in range(max(0, y - 2), min(H, y + 3)):
						if grid[ty][tx] and d < smallests[ty][tx]:
							smallests[ty][tx] = d
							heappush(queue_move, (d, tx, ty))
							heappush(queue_warp, (d, tx, ty))
	return smallests[Dh][Dw]

result = calc()
if result == m:
	print(-1)
else:
	print(result)

Solution (Python):
h,w = map(int,input().split())
s = list(map(int,input().split()))
g = list(map(int,input().split()))
s[0] -= 1
s[1] -= 1
g[0] -= 1
g[1] -= 1
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)

now = [s]
ans = 0
def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])
seen[s[0]][s[1]] = 1
from collections import deque
now = deque([s])
while now:
  for i in range(10**6):
    try:
      a,b = now[i]
      check(a-1,b)
      check(a+1,b)
      check(a,b-1)
      check(a,b+1)
    except:
      break
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  
  ans += 1
  last = now
  now = deque()
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
  
else:
  print(-1)

Solution (Python):
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    qn = deque([[sy,sx]])

    while q:
        
        while q:
            y, x = q.popleft()
            qn.append([y,x])
            if [y, x] == [gy, gx]:
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                    visited[ny][nx] = visited[y][x]
                    q.append([ny,nx])
                    qn.append([ny,nx])
        
        
        
            
        
        next_qnl = []
        while qn:
            y, x = qn.popleft()
            
            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        
                        q.append([ny,nx])
            
            
            

    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
print(ans)

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


dist = []
for _ in range(H):
  dist.append(list(map(lambda x:-1 if x=='.' else 10**30, input())))



C = set([(Ch, Cw)])
N = set()
ans = 0
while C or N:
  if C:
    
    xh, xw = C.pop()
    if dist[xh][xw] >=0:
      continue
    else:
      dist[xh][xw] = ans

    if (xh, xw) == (Dh, Dw):
      print(ans)
      exit()
    
    if xh > 0 and dist[xh-1][xw] < 0:
      C.add((xh-1,xw))
    if xh < H-1 and dist[xh+1][xw] < 0:
      C.add((xh+1,xw))
    if xw > 0 and dist[xh][xw-1] < 0:
      C.add((xh,xw-1))
    if xw < W-1 and dist[xh][xw+1] < 0:
      C.add((xh,xw+1))
    for dh in [-2, -1, 0, 1, 2]:
      for dw in [-2, -1, 0, 1, 2]:
        if 0 <= xh + dh < H and 0 <= xw + dw < W and dist[xh+dh][xw+dw] < 0:
          N.add((xh+dh, xw+dw))
  else:
    C = N
    N = set()
    ans += 1
      
      
print(-1)