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

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
from sys import stdin
s=[stdin.readline() for i in range(h)]





from collections import deque
q=deque([(ch-1,cw-1)])
used=[[float("INF")]*w for i in range(h)]
used[ch-1][cw-1]=0
X=((-1,0),(1,0),(0,1),(0,-1))
Y=((-2,-2),(-2,-1),(-2,0),(-2,1),(-2,2),(-1,-2),(-1,-1),(-1,1),(-1,2),(0,-2),(0,1),(0,2),(1,-2),(1,-1),(1,1),(1,2),(2,-2),(2,-1),(2,0),(2,1),(2,2))
while len(q)>0:
  y,x=q.popleft()
  for dy,dx in X:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]
        q.appendleft((ny,nx))
  for dy,dx in Y:
    nx=x+dx
    ny=y+dy
    if nx>=0 and nx<w and ny>=0 and ny<h and s[ny][nx]==".":
      if used[ny][nx]>used[y][x]:
        used[ny][nx]=used[y][x]+1
        q.append((ny,nx))

if used[dh-1][dw-1]==float("INF"):
  print(-1)
else:
  print(used[dh-1][dw-1])

Solution (Python):
import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    import os, zlib, base64
    open('solve.pyx', 'wb').write(zlib.decompress(base64.b85decode("c$}@2ZI7Zb5Xay1Ddw^{7GecmbIHXl_eBUX*cPeBL!m|CKK)G
    os.system('cythonize -i -3 -b solve.pyx')
import solve

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

S = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

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

Solution (Python):
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si ,sj = map(int, input().split())
ti, tj = map(int, input().split())

si -= 1
sj -= 1
ti -= 1
tj -= 1
inf = 10**9
s = list()
for i in range(H):
  s.append(input())

dist = [[inf] * W for i in range(H)]
q = deque()
dist[si][sj] = 0
q.append([si,sj])

while len(q) > 0:
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == '
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
    
  for ei in range(-2, 3, 1):
    for ej in range(-2, 3, 1):
      ni = i + ei
      nj = j + ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == '
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d+1
      q.append([ni,nj])
    
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Solution (Python):
from collections import deque
H, W = map(int, input().split())
c = tuple(int(x)+1 for x in input().split())
d = [int(x)+1 for x in input().split()]
maze = [[-1] * (W+4), [-1] * (W+4)]

for i in range(H):
    temp = []
    s0 = input()
    s0 = '11' + s0.replace('.', '0').replace('
    for j, s in enumerate(s0):
        temp.append(-int(s))
    maze.append(temp)
maze.append([-1] * (W+4))
maze.append([-1] * (W+4))

def check55(i, j):
    cset = {(ii, jj) for ii in range(i-2, i+3) for jj in range(j-2, j+3) if maze[ii][jj]==0}
    cset = cset - {(i-1, j), (i, j), (i+1, j), (i, j-1), (i, j+1)}
    return cset

def check(i, j, delta):
    if delta[0] != 0:
        ii = i + 3 * delta[0]
        for jj in range(j-2, j+3):
            if maze[ii][jj]==0:
                dset.add((ii, jj))

    else:
        jj = j + 3 * delta[1]
        for ii in range(i-2, i+3):
            if maze[ii][jj]==0:
                dset.add((ii, jj))

    return



k = 1
tempbfs = deque([[c[0], c[1], k]])
flag = 0
while tempbfs:
    if flag == 1:break
    p = tempbfs.popleft()

    
    if maze[p[0]][p[1]] != 0:continue
    maze[p[0]][p[1]] = p[2]
    if p[0] == d[0] and p[1] == d[1]:
        flag = 1
        k = p[2]
        break
    temp = [(p[0], p[1])]
    dset = set()
    while temp:
        p0 = temp.pop()
        for delta in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            y = p0[0] + delta[0]
            x = p0[1] + delta[1]
            if maze[y][x] != 0: continue
            maze[y][x] = p[2]
            if y == d[0] and x == d[1]:
                flag = 1
                k = p[2]
                break
            temp.append((y, x))
            check(p0[0], p0[1], delta)

    if flag == 1: break
    for l in dset:
        if maze[l[0]][l[1]] == 0:
            tempbfs.append([l[0], l[1], p[2]+1])
    dset = check55(p[0], p[1])
    for l in dset:
        tempbfs.append([l[0], l[1], p[2]+1])

print(k - 1 if flag else -1)

Solution (Python):
import sys
import re
import queue
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    H, W = i_map()
    Ch, Cw = i_map()
    Dh, Dw = i_map()
    Ch,Cw = Ch-1,Cw-1
    Dh,Dw = Dh-1,Dw-1
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]  

    
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while(q):
        ux,uy,s = q.popleft()
        for dx,dy in walk:
            nx = ux + dx
            ny = uy + dy
            if(0<=nx<H and 0<=ny<W and maze[nx][ny]=='.' and path[nx][ny] > s):
                path[nx][ny] = s
                q.appendleft((nx,ny,s))
        for dx,dy in warp:
            nx = ux + dx
            ny = uy + dy
            if(0<=nx<H and 0<=ny<W and maze[nx][ny]=='.' and path[nx][ny] > s+1):
                path[nx][ny] = s+1
                q.append((nx,ny,s+1))

    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


if __name__ == '__main__':
	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())

C0 -= 1
C1 -= 1
D0 -= 1
D1 -= 1

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

inf = 1000000000

q = deque([[C0, C1]])
dist = [[inf for a in range(1100)]for b in range(1100)]
dist[C0][C1] = 0

walk0 = [1, 0, -1, 0]
walk1 = [0, 1, 0, -1]


while q:
    now = q.popleft()
    d = dist[now[0]][now[1]]

    for v in range(4):
        wnxt0 = now[0] + walk0[v]
        wnxt1 = now[1] + walk1[v]

        if wnxt0 < 0 or wnxt0 > H - 1: continue
        elif wnxt1 < 0 or wnxt1 > W - 1: continue
        elif map[wnxt0][wnxt1] == "
        elif dist[wnxt0][wnxt1] <= d: continue
        
        dist[wnxt0][wnxt1] = d
        q.appendleft([wnxt0, wnxt1])

    for x in [-2, -1, 0, 1, 2]:
        for y in [-2, -1, 0, 1, 2]:
            mnxt0 = now[0] + y
            mnxt1 = now[1] + x

            if mnxt0 < 0 or mnxt0 > H - 1: continue
            elif mnxt1 < 0 or mnxt1 > W - 1: continue
            elif map[mnxt0][mnxt1] == "
            elif dist[mnxt0][mnxt1] <= d + 1: continue

            dist[mnxt0][mnxt1] = d + 1
            q.append([mnxt0, mnxt1])

ans = dist[D0][D1]

if ans == inf:
    ans = -1

print(ans)

Solution (Python):
import sys
import re
import queue
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext

def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    H, W = i_map()
    Ch, Cw = i_map()
    Dh, Dw = i_map()
    Ch,Cw = Ch-1,Cw-1
    Dh,Dw = Dh-1,Dw-1
    maze = [input() for _ in range(H)]

    INF = 10 ** 12
    path = [[INF] * W for _ in range(H)]  

    
    walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

    q = deque()
    path[Ch][Cw] = 0
    q.append((Ch, Cw, 0))

    while q:
        x, y, s = q.popleft()
        for dx, dy in walk:  
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
                path[nx][ny] = s
                q.appendleft((nx, ny, s))  
        for dx, dy in warp:  
            nx = x + dx
            ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, s + 1))  
    
    ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
    print(ans)


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

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  


walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

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

from heapq import *

H, W = map(int, input().split())
m1 = lambda s: int(s)-1
sy, sx = map(m1, input().split())
fy, fx = map(m1, input().split())
G = [list(input()) for _ in range(H)]
D = [[10 ** 18] * W for _ in range(H)]

D[sy][sx] = 0
Q = [(0, sx, sy)]
while Q:
	d, x, y = heappop(Q)
	if D[y][x] < d: continue

	if (x, y) == (fx, fy):
		print(d)
		break

	for dx in range(-2, 3):
		for dy in range(-2, 3):
			nx = x + dx
			ny = y + dy
			if nx < 0 or ny < 0 or nx >= W or ny >= H or G[ny][nx] == '
			nd = d + (0 if abs(dx) + abs(dy) == 1 else 1)
			if nd >= D[ny][nx]: continue
			D[ny][nx] = nd
			heappush(Q, (nd, nx, ny))
else:
	print(-1)

Solution (Python):
from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())

Solution (Python):
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list('
for i in range(h):
    a = '
    s[i+1] = list(a)
queue = deque([[ch,cw]])
s[ch][cw] = 0
l = [[0,-1],[0,1],[-1,0],[1,0]] 
r = [[] for i in range(20)]
k = 0
for i in range(-2,3):
    for j in range(-2,3):
        if i != 0 or j != 0:
            if not [i,j] in l:
                r[k] = [i,j]
                k += 1
while queue:
    x,y = queue.popleft()
    if [x,y] != [dh,dw]:
        for n,m in l:
            new_h,new_w = x+n,y+m 
            if s[new_h][new_w] == '.':
                s[new_h][new_w] = s[x][y]
                queue.appendleft([new_h,new_w])
            elif s[new_h][new_w] != "
                if s[new_h][new_w] > s[x][y]:
                    s[new_h][new_w] = s[x][y]
                    queue.appendleft([new_h,new_w])
            else:
                pass
        for n,m in r:
            new_h,new_w = x+n,y+m
            if new_h >= 0 and new_h <= h+1 and new_w >= 0 and new_w <= w+1:
                if s[new_h][new_w] == '.':
                    s[new_h][new_w] = s[x][y]+1
                    queue.append([new_h,new_w])
                elif s[new_h][new_w] != "
                    if s[new_h][new_w] > s[x][y]+1:
                        s[new_h][new_w] = s[x][y]+1
                        queue.append([new_h,new_w])
                else:
                    pass
if s[dh][dw] != '.':
    print(s[dh][dw])
else:
    print(-1)

Solution (Python):




import sys
from io import StringIO
import unittest
from collections import deque

def resolve():
    readline=sys.stdin.readline

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

    mp=[[None for i in range(w)] for j in range(h)]

    for i in range(h):
        ss = readline().rstrip()
        for j in range(w):
            if ss[j]=="
                mp[i][j] = -1

    d = deque()
    d2 = deque()

    if mp[ch][cw]==None:
        mp[ch][cw]=0
        d.append((ch,cw))
    while len(d) > 0:
        y,x = d.popleft()
        d2.append((y,x))
        for dy,dx in ((1,0),(-1,0),(0,1),(0,-1)):
            ny=y+dy
            nx=x+dx
            if 0 <= ny < h and 0 <= nx < w and mp[ny][nx]==None:
                mp[ny][nx]=mp[y][x]
                d.append((ny,nx))
        if len(d)==0:
            while len(d2) > 0:
                y2,x2 = d2.popleft()
                for dy in range(-2,3):
                    for dx in range(-2,3):
                        ny=y2+dy
                        nx=x2+dx
                        if 0 <= ny < h and 0 <= nx < w and mp[ny][nx]==None:
                            mp[ny][nx]=mp[y][x]+1
                            d.append((ny,nx))
    if mp[dh][dw] == None:
        print(-1)
    else:
        print(mp[dh][dw])    
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

Solution (Python):
from collections import deque

di = [-1,0,1,0]
dj = [0,-1,0,1]

H,W = map(int, input().split())
si,sj = map(int, input().split())
ti,tj = map(int, input().split())
si -= 1
sj -= 1
ti -= 1
tj -= 1
inf = 10**9
s = list()
for i in range(H):
  s.append(input())

dist = [[inf]*W for i in range(H)]
q = deque()
dist[si][sj] = 0
q.append([si,sj])

while len(q) > 0:
  tmp = q.popleft()
  i = tmp[0]
  j = tmp[1]
  d = dist[i][j]
  if dist[i][j] != d:
    continue
  for v in range(4):
    ni = i + di[v]
    nj = j + dj[v]
    if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
      continue
    if s[ni][nj] == "
      continue
    if dist[ni][nj] <= d:
      continue
    dist[ni][nj] = d
    q.appendleft([ni,nj])
  
  for ei in range(-2,3,1):
    for ej in range(-2,3,1):
      ni = i+ei
      nj = j+ej
      if (ni < 0) or (ni >= H) or (nj < 0) or (nj >= W):
        continue
      if s[ni][nj] == "
        continue
      if dist[ni][nj] <= d+1:
        continue
      dist[ni][nj] = d + 1
      q.append([ni,nj])
      
ans = dist[ti][tj]
if ans == inf:
  ans = -1
print(ans)

Solution (Python):
from collections import deque
def solve():  
    h, w = map(int,input().split())
    ch, cw = map(int,input().split())
    Dh, Dw = map(int,input().split())
    
    M = ['
    for i in range(2):
        M.insert(0,'
        M.append('
    
    INF = float('inf')
    cost = [[INF for _ in range(w+4)] for _ in range(h+4)]
    cost0 = deque()
    ans = -1
    
    cost0.append((ch+1, cw+1, 0))
    cost[ch+1][cw+1] = 0
    
    move = [(1,0),(0,1),(-1,0),(0,-1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)] + move]
    
    cost1 = deque()
    
    while cost0:
        h, w, c = cost0.popleft()
        cost1.append((h, w, c))
        
        for i,j in move:
            dh = h + i
            dw = w + j
            if M[dh][dw] == '.' and c < cost[dh][dw]: 
                cost[dh][dw] = c
                cost0.appendleft((dh, dw, cost[dh][dw]))
        
        if len(cost0) == 0:
            while cost1:
                h, w, c = cost1.popleft()
                for i,j in warp:
                    dh = h + i
                    dw = w + j
                    if M[dh][dw] == '.' and c+1 < cost[dh][dw]:  
                        cost[dh][dw] = c+1
                        cost0.append((dh, dw, cost[dh][dw]))
        if cost[Dh+1][Dw+1] != INF:
            ans = cost[Dh+1][Dw+1]
    
    print(ans)

if __name__ == "__main__":
    solve()

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())
maze = [input() for _ in range(H)]
 
INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  
 
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
 
q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))
 
while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

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

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

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


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

Solution (Python):
from collections import deque

def main():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=["
  for i in range(2):
    M.insert(0,"
    M.append("

  C=[[-1 if M[j][i]=="." else -2 for i in range(w+4)] for j in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if C[dh][dw]==-1:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if C[dh][dw]==-1:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

    if C[-~dy][-~dx]!=-1:
      print(C[-~dy][-~dx])
      exit()

  print(C[-~dy][-~dx])

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque

def main():
  h,w=map(int,input().split())
  cy,cx=map(int,input().split())
  dy,dx=map(int,input().split())

  M=["
  for i in range(2):
    M.insert(0,"
    M.append("

  C=[[-1 if M[j][i]=="." else -2 for i in range(w+4)] for j in range(h+4)]
  C[-~cy][-~cx]=0
  QA,QB=deque(),deque()
  QA.append((-~cy,-~cx,0))
  W=[[i,j] for i in range(-2,3) for j in range(-2,3) if abs(i)+abs(j)>1]

  while QA:
    h,w,c=QA.popleft()
    QB.append((h,w,c))

    for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
      dh,dw=h+i,w+j
      if C[dh][dw]==-1:
        C[dh][dw]=c
        QA.appendleft((dh,dw,c))

    if QA:
      continue

    while QB:
      h,w,c=QB.popleft()
      for i,j in W:
        dh,dw=h+i,w+j
        if C[dh][dw]==-1:
          C[dh][dw]=-~c
          QA.append((dh,dw,-~c))

  print(C[-~dy][-~dx])

if __name__ == "__main__":
  main()

Solution (Python):
from collections import deque

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

S = [[False]*W for _ in range(H)]
for h in range(H):
    s = input()
    for w in range(W):
        if s[w] == ".":
            S[h][w] = True
d = [[10**9]*W for _ in range(H)]
d[Ch-1][Cw-1] = 0

D = deque([(Ch-1, Cw-1, 0)])
while D:
    h, w, c = deque.popleft(D)
    if c > d[h][w]:
        continue
    
    
    if h > 0:
        if S[h-1][w] and c < d[h-1][w]:
            d[h-1][w] = c
            deque.appendleft(D, (h-1, w, c))
    
    if h < H-1:
        if S[h+1][w] and c < d[h+1][w]:
            d[h+1][w] = c
            deque.appendleft(D, (h+1, w, c))
    
    if w > 0:
        if S[h][w-1] and c < d[h][w-1]:
            d[h][w-1] = c
            deque.appendleft(D, (h, w-1, c))
    
    if w < W-1:
        if S[h][w+1] and c < d[h][w+1]:
            d[h][w+1] = c
            deque.appendleft(D, (h, w+1, c))
    
    for hh in range(max(0, h-2), min(H-1, h+2)+1):
        for ww in range(max(0, w-2), min(W-1, w+2)+1):
            if S[hh][ww] and d[hh][ww] > c+1:
                d[hh][ww] = c+1
                deque.append(D, (hh, ww, c+1))
if d[Dh-1][Dw-1] == 10**9:
    print(-1)
else:
    print(d[Dh-1][Dw-1])

Solution (Python):


h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append([c for c in input()])

queue = [[(ch - 1, cw - 1)], []]

dist = 0
while len(queue[0]) > 0:
    while len(queue[0]) > 0:
        y, x = queue[0].pop()
        if s[y][x] != '.':
            continue
        s[y][x] = dist
        for vy in range(-2, 3):
            for vx in range(-2, 3):
                if 0 <= y + vy < h and 0 <= x + vx < w and \
                   s[y + vy][x + vx] == '.':
                    cost = 0 if abs(vx) + abs(vy) <= 1 else 1
                    queue[cost].append((y + vy, x + vx))
    dist += 1
    queue = [queue[1], queue[0]]

dist = s[dh - 1][dw - 1]
print(dist if dist != '.' else -1)

Solution (Python):


import sys
from collections import deque

H,W = map(int, input().split())
S_h,S_w = map(int, input().split()) 
G_h,G_w = map(int, input().split()) 


mp =[["
for i in range(2,H+2):
    mp[i][2:-2] =input().strip() 
    
S_h +=1 
S_w +=1
G_h +=1
G_w +=1
used =[[float('inf')]*(W +4) for i in range(H +4)] 
used[S_h][S_w] =0
wap=[-2,-1,0,1,2] 


dq =deque()
dq.append((0,S_h,S_w)) 
arrive=False 

while dq:
    k,i,j =dq.popleft()
    if k >used[i][j]: 
        continue
    if i ==G_h and j ==G_w: 
        arrive =True
        break
    for di in wap:
        for dj in wap:
            if di ==0 and dj ==0: 
                continue
            ni,nj =i +di ,j +dj 
            if mp[ni][nj] =="
                continue
            if k <used[ni][nj]:
                if abs(di) +abs(dj) ==1: 
                    nk =k
                    used[ni][nj] =nk
                    dq.appendleft((nk,ni,nj))
                else:                   
                    nk =k+1
                    used[ni][nj] =nk
                    dq.append((nk,ni,nj))
if arrive:
    ans =used[G_h][G_w]
else:
    ans =-1
print(ans)

Solution (Python):


from collections import deque

h,  w  = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = []
for i in range(h):
    s.append([c for c in input()])

def dfs(y, x, area_id):
    stack = [(y, x)]
    while len(stack) > 0:
        y, x = stack.pop()
        if s[y][x] == '.':
            s[y][x] = area_id
            for vy, vx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                if (0 <= x + vx < w and 0 <= y + vy < h and
                    s[y + vy][x + vx] == '.'):
                    stack.append((y + vy, x + vx))

n_area = 0
for y in range(h):
    for x in range(w):
        if s[y][x] == '.':
            dfs(y, x, n_area)
            n_area += 1


adj = [set() for i in range(n_area)]
for y in range(h):
    for x in range(w):
        if s[y][x] == '
            continue
        for vy in range(0, 3):
            for vx in range(-2, 3):
                if (0 <= x + vx < w and 0 <= y + vy < h and
                    s[y + vy][x + vx] != '
                    adj[s[y][x]].add(s[y + vy][x + vx])
                    adj[s[y + vy][x + vx]].add(s[y][x])

c = s[ch - 1][cw - 1]
d = s[dh - 1][dw - 1]
dist = [float('inf') for i in range(n_area)]
dist[c] = 0

q = deque()
q.append((c, 0))
while len(q) > 0:
    c, cost = q.popleft()
    for x in adj[c]:
        if dist[x] > cost + 1:
            dist[x] = cost + 1
            q.append((x, cost + 1))

print(dist[d] if dist[d] < float('inf') else -1)