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, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() 
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))

visited = [[float('inf')] * W for _ in range(H)]
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() 
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = narr((H, W), lambda: float('inf'))
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Solution (Python):
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Solution (Python):

from collections import deque

def inc(y, x):
	return 0 <= y < H and 0 <= x < W

H, W = map(int, input().split())
Sy, Sx = map(int, input().split())
Gy, Gx = map(int, input().split())
"""
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()
"""
a = [input() for i in range(H)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]


visit = [[-1 for i in range(W)] for j in range(H)]
visit[Sy-1][Sx-1]=0 
deq = deque([(Sy-1, Sx-1)])

while deq:
    h, w = deq.pop()
    for dh, dw in zip(DH, DW):
        x = w+dw; y=h+dh
        if inc(y, x)==False or a[y][x]=='
            continue
        if visit[y][x]==-1 or visit[y][x]>visit[h][w]:
            visit[y][x] = visit[h][w]
            deq.append((y,x))
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if inc(h+dh, w+dw)==False or a[h+dh][w+dw]=='
                continue
            if visit[h+dh][w+dw]==-1: 
                visit[h+dh][w+dw] = visit[h][w]+1
                deq.appendleft((h+dh, w+dw))
if visit[Gy-1][Gx-1] == 1e8:
    print(-1)
else:
    print(visit[Gy-1][Gx-1])

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))

mat = lambda x, y, v: [[v]*y for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))


visited = mat(H, W, float('inf'))
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
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())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-1])

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

mp = [input() for _ in range(H)]
ds1 = [[0,-1],[0,1],[-1,0],[1,0]]
ds2 = [[i,j] for i in range(-2,3) for j in range(-2,3)]

memo = [[0]*W for _ in range(H)]
memo[CH][CW] = 1

h1 = deque([(CH,CW)])
h2 = deque([])
ans = 0

while 1:
  while h1:
    t = h1.popleft()
    h2.append(t)
    for d in ds1:
      if t[0]+d[0] >= 0 and t[0]+d[0] < H \
         and t[1]+d[1] >= 0 and t[1]+d[1] < W:
        if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 0:
          memo[t[0]+d[0]][t[1]+d[1]] = 1
          h1.append((t[0]+d[0], t[1]+d[1]))
  if memo[DH][DW] == 1:
    print(ans)
    exit()
  ans += 1

  while h2:
    t = h2.popleft()
    for d in ds2:
      if t[0]+d[0] >= 0 and t[0]+d[0] < H \
         and t[1]+d[1] >= 0 and t[1]+d[1] < W:
        if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 0:
          memo[t[0]+d[0]][t[1]+d[1]] = 1
          h1.append((t[0]+d[0], t[1]+d[1]))
          
  if not h1:
    print(-1)
    exit()

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() 
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))

visited = [[float('inf')] * W for _ in range(H)]
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() 
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
visited = narr((H, W), lambda: float('inf'))
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

H, W = MAP()
sy, sx = MAP()
gy, gx = MAP()
sx += 1
sy += 1
gx += 1
gy += 1
S = ["
dist = [[10**6]*(W+4) for _ in range(H+4)]
dist[sy][sx] = 0
q = deque()
q.append((sy, sx, 0))

while q:
    y, x, cnt = q.popleft()
    if dist[y][x] != cnt:
        continue
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            ny = y+dy
            nx = x+dx
            if abs(dx)+abs(dy) > 1:
                if S[ny][nx] == "." and dist[ny][nx] >  dist[y][x]+1:
                    dist[ny][nx] = cnt + 1
                    q.append((ny, nx, cnt+1))
            else:
                if S[ny][nx] == "." and dist[ny][nx] > dist[y][x]:
                    dist[ny][nx] = cnt
                    q.appendleft((ny, nx, cnt))

print(dist[gy][gx] if dist[gy][gx] != 10**6 else -1)

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())
S=[input() for _ in range(H)]

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1=[(Ch,Cw)]
stack2=[]

answer=0

while 1:
    while stack1:
        sh,sw=stack1.pop()
        stack2.append((sh,sw))
        for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
            nh,nw = sh+i, sw+j
            if 0<=nh<H and 0<=nw<W and S[nh][nw]!="
                if nh==Dh and nw==Dw:
                    print(answer)
                    exit()
                grid[nh][nw]=1
                stack1.append((nh,nw))
    answer+=1

    while stack2:
        sh,sw=stack2.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                nh,nw = sh+i,sw+j
                if 0<=nh<H and 0<=nw<W and S[nh][nw]!="
                    if nh==Dh and nw==Dw:
                        print(answer)
                        exit()
                    grid[nh][nw]=1
                    stack1.append((nh,nw))

    if not stack1:
        print(-1)
        exit()

Solution (Python):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
                que.append((count + 1, py, px))

print(grid[dh][dw])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

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
rows,cols = h,w

OK = "."
NG = "

ss = np.array([[c=="
@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] 
    
    












    while q:

        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1

    
    
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
print(main(ss,ch,cw,dh,dw))

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())
S = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]

move = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        move.append((i, j))
q = deque()
q.append((0, ch, cw))
while q:
    c, h, w = q.popleft()
    if dist[h][w] >= 0:
        continue
    dist[h][w] = c
    for hh, ww in move:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] < 0:
            if (hh, ww) in ((0,1), (1,0), (-1,0), (0,-1)):
                q.appendleft((c, h+hh, w+ww)) 
            else:
                q.append((c+1, h+hh, w+ww)) 

print(dist[dh][dw])

Solution (Python):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
                que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])

Solution (Python):
from collections import deque

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

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(2)]
memo[0][Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

while d:
    h, w, c = d.popleft()

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[0][h+i][w+j] and not searched[h+i][w+j]:
                    memo[0][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[0][h+i][w+j] and not memo[1][h+i][w+j] and not searched[h+i][w+j]:
                        memo[1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)

Solution (Python):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
s = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
                que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])

Solution (Python):
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 = [list(input()) for _ in range(H)]
dist = [[float("inf")] * W for _ in range(H)]








y = {(0, 1), (1, 0), (-1, 0), (0, -1)}


from collections import deque
q = deque()
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]:
            dist[h+hh][w+ww] = dist[h][w]
            q.appendleft((h+hh, w+ww))
    for hh in range(-2, 3):
        for ww in range(-2, 3):
            if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w] + 1:
                dist[h+hh][w+ww] = dist[h][w] + 1
                q.append((h+hh, w+ww))

if dist[dh][dw] == float("inf"):
    print(-1)
else:
    print(dist[dh][dw])

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

h,w = readInts()
ch,cw = readInts()
dh,dw = readInts()
s = ["
visited = [[-2]*(w+2) for i in range(h+2)]
for i in range(h+2):
	for j in range(w+2):
		if s[i][j]==".":
			visited[i][j] = -1

delta1 = [[0,1],[1,0],[-1,0],[0,-1]]

q = {(ch,cw)}
set_list = set()
cost = 0
while 1:
	if len(q)==0:
		break
	while len(q) !=0:
		x,y = q.pop()
		set_list.add((x,y))
		visited[x][y] = cost
		for dx,dy in delta1:
			x2 = x+dx
			y2 = y+dy
			if visited[x2][y2]==-1:
				q.add((x2,y2))
	cost+=1
	while len(set_list) != 0:
		x,y = set_list.pop()
		for dx in range(-2,3):
			for dy in range(-2,3):
				x2 = x+dx
				y2 = y+dy
				if visited[min(x2,h+1)][min(y2,w+1)]!=-1: continue
				q.add((x2,y2))

print(visited[dh][dw])

Solution (Python):
from collections import deque

def inc(y, x):
	return 0 <= y < H and 0 <= x < W

H, W = map(int, input().split())
Sy, Sx = map(int, input().split())
Gy, Gx = map(int, input().split())
"""
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()
"""
a = [input() for i in range(H)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]


visit = [[1e8 for i in range(W)] for j in range(H)]
visit[Sy-1][Sx-1]=0 
deq = deque([(Sy-1, Sx-1)])

while deq:
    h, w = deq.pop()
    for dh, dw in zip(DH, DW):
        x = w+dw; y=h+dh
        if inc(y, x)==False or a[y][x]=='
            continue
        if visit[y][x] > visit[h][w]:
            visit[y][x] = visit[h][w]
            deq.append((y,x))
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if inc(h+dh, w+dw)==False or a[h+dh][w+dw]=='
                continue
            if visit[h+dh][w+dw] > visit[h][w]+1: 
                visit[h+dh][w+dw] = visit[h][w]+1
                deq.appendleft((h+dh, w+dw))
if visit[Gy-1][Gx-1] == 1e8:
    print(-1)
else:
    print(visit[Gy-1][Gx-1])

Solution (Python):
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
from itertools import count
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


MOVES = [
    ((1, 0), [(2,-1),(2,0),(2,1),(2,2),(1,1)]),
    ((-1, 0),[(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]),
    ((0, 1), [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]),
    ((0, -1), [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]),
    ]

CONVERTED_MOVES = None

def solve(dist, start, goal):
    q = [start]
    cnt = 0
    while q:
        nq = []
        while q:
            x = q.pop()
            if x == goal:
                return cnt
            if dist[x] < cnt:
                continue
            for d,l in CONVERTED_MOVES:
                nx = x+d
                if dist[nx] > cnt:
                    dist[nx] = cnt
                    q.append(nx)
                if dist[nx] < 0:
                    for t in l:
                        p = x+t
                        if dist[p] > cnt+1:
                            dist[p] = cnt+1
                            nq.append(p)
        q = nq
        cnt += 1

    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)+1,readline().split()))
    goal = tuple(map(lambda i:int(i)+1,readline().split()))

    H += 4
    W += 4

    dist = [-1]*(W*H)

    start = start[0]*W+start[1]
    goal = goal[0]*W+goal[1]

    for t,s in zip(count(2*W,W),read().split()):
        for i,c in zip(count(t+2),s.decode()):
            if c == '.':
                dist[i] = 10**7

    convert = lambda x,y: x*W+y
    CONVERTED_MOVES = []
    for d,l in MOVES:
        d = convert(*d)
        l = [convert(*d) for d in l]
        CONVERTED_MOVES.append((d,l))

    

    print(solve(dist,start,goal))

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()
ch, cw = LI()
dh, dw = LI()
s = [input() for _ in range(h)]

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
que = deque([(cw-1, ch-1)])
d = [[10**10] * w for _ in range(h)]
d[ch-1][cw-1] = 0
while que:
    x, y = que.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < w and 0 <= ny < h:
            if s[ny][nx] == '.' and d[ny][nx] > d[y][x]:
                d[ny][nx] = d[y][x]
                que.appendleft((nx, ny))
    for i in range(-2, 3):
        for j in range(-2, 3):
            nx, ny = x + i, y + j
            if 0 <= nx < w and 0 <= ny < h:
                if s[ny][nx] == '.' and d[ny][nx] > d[y][x] + 1:
                    d[ny][nx] = d[y][x] + 1
                    que.append((nx, ny))
if d[dh-1][dw-1] == 10**10:
    print(-1)
else:
    print(d[dh-1][dw-1])

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

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
rows,cols = h,w

OK = "."
NG = "

ss = np.array([[c=="
@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] 
    
    
    dx = []
    dy = []
    vvs = []
    for i in range(-2,3):
        for j in range(-2,3):
            if not (i==j==0):
                dx.append(i)
                dy.append(j)
                if abs(i)+abs(j)>1:
                    vvs.append(1)
                else:
                    vvs.append(0)
    while q:

        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        
        if pu==goal:
            break
        for xx,yy,vv in zip(dx,dy,vvs):
    
    
            x,y = ux+xx, uy+yy
            u = x*w + y
            num = pnum+vv
            if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                continue
    
            if seen[u]>num:
                seen[u] = num
                hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
print(main(ss,ch,cw,dh,dw))

Solution (Python):
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
s = [list(input()) for _ in range(h)]
d = [[-1] * w for _ in range(h)]
d[ch][cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
warp = [[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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if d[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count:
                d[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '
            if d[y + NY][x + NX] == -1 or d[y + NY][x + NX] > count + 1:
                d[y + NY][x + NX] = count + 1
                que.append((count + 1, y + NY, x + NX))

print(d[dh][dw])