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

Solution (Python):
from collections import deque

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

squares = []
for i in range(H):
    squares.append([None]*(W))

for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '
            squares[i][j] = -1  

squares[Ch][Cw]=0

d1 = deque()
d2 = deque()
d1.append([Ch, Cw])

warps = 0

def visit(i1, j1, i2, j2, with_warp = False):  
    if i2 < 0 or i2 >= H or j2 < 0 or j2 >= W:
        return
    sq2 = squares[i2][j2]
    if sq2 == None:
        if with_warp:
            squares[i2][j2] = warps + 1  
        else:
            squares[i2][j2] = warps  
        d1.append([i2, j2])
        if i2 == Dh and j2 == Dw:
            print(squares[i2][j2])
            exit()

while (len(d1)>0):
    while (len(d1)>0):
        src = d1.popleft()
        visit(src[0], src[1], src[0] - 1, src[1])
        visit(src[0], src[1], src[0] + 1, src[1])
        visit(src[0], src[1], src[0], src[1] - 1)
        visit(src[0], src[1], src[0], src[1] + 1)
        d2.append(src)

    while (len(d2)>0):
        src = d2.popleft()
        for i in range(-2,3):
            for j in range(-2,3):
                visit(src[0], src[1], src[0]+i, src[1]+j, True)

    warps += 1

print(-1)

Solution (Python):
from collections import deque
from itertools import product

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 = [list(input()) for _ in range(H)] 
walkFrom = deque([(Ch, Cw)]) 
warpFrom = deque() 
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: not x in WalkRange + [(0, 0)], product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h_dist, w_dist in moveRange:
    h_to, w_to = h_from + h_dist, w_from + w_dist
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))


maze[Ch][Cw] = warpCount
while walkFrom:
  
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print('-1') if goal in ['.', '

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

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

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]

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
from itertools import product

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 = [list(input()) for _ in range(H)] 
walkFrom = deque([(Ch, Cw)]) 
warpFrom = deque() 
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h_dist, w_dist in moveRange:
    h_to, w_to = h_from + h_dist, w_from + w_dist
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))


maze[Ch][Cw] = warpCount
while walkFrom:
  
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print('-1') if goal in ['.', '

Solution (Python):
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    h, w = rl()
    starth, startw = rl()
    endh, endw = rl()
    maze = []
    for i in range(h):
        maze.append(list(input()))

    def nbrs(x, y):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < h and 0 <= ny and ny < w:
                yield (nx, ny)

    def magic(x, y):
        for nx in range(x - 2, x + 3):
            for ny in range(y - 2, y + 3):
                if nx == x and ny == y: continue
                if 0 <= nx and nx < h and 0 <= ny and ny < w:
                    yield (nx, ny)


    bridges = dd(set)
    def dfs(x, y, num):
        if maze[x][y] != '.':
            return
        else:
            maze[x][y] = num
            for nx, ny in magic(x, y):
                if maze[nx][ny] not in ['.', '
                    bridges[num].add(maze[nx][ny])
                    bridges[maze[nx][ny]].add(num)
            for nx, ny in nbrs(x, y):
                dfs(nx, ny, num)

    num = 0
    for x in range(h):
        for y in range(w):
            if maze[x][y] == ".":
                dfs(x, y, num)
                num += 1
   
    curr = [maze[starth-1][startw-1]]
    goal = maze[endh-1][endw-1]
    if curr[0] == goal:
        print (0)
        return

    seen = set(curr)
    depth = 0
    while curr:
        ring = []
        depth += 1
        for node in curr:
            for nxt in bridges[node]:
                if nxt not in seen:
                    if nxt == goal:
                        print (depth)
                        return
                    seen.add(nxt)
                    ring.append(nxt)
        curr = ring

    print (-1)



mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Solution (Python):
from collections import deque
from itertools import product

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 = [list(input()) for _ in range(H)]
walkFrom = deque([(Ch, Cw)]) 
warpFrom = deque() 
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h, w in moveRange:
    h_to, w_to = h_from + h, w_from + w
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))


while walkFrom:
  
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print('-1') if goal in ['.', '

Solution (Python):
from collections import deque
from itertools import product

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 = [list(input()) for _ in range(H)]
walkFrom = deque([(Ch, Cw)]) 
warpFrom = deque() 
WalkRange = [(1, 0), (-1, 0), (0, 1), (0, -1)]
WarpRange = list(filter(lambda x: x != (0, 0), product(range(-2, 3), repeat=2)))
warpCount = 0

def move(h_from, w_from, moveRange):
  for h, w in moveRange:
    h_to, w_to = h_from + h, w_from + w
    if 0 <= h_to < H and 0 <= w_to < W and maze[h_to][w_to] == '.':
      maze[h_to][w_to] = warpCount
      walkFrom.append((h_to, w_to))


while walkFrom:
  
  while walkFrom:
    h, w = walkFrom.popleft()
    warpFrom.append((h, w))
    move(h, w, WalkRange)
  
  warpCount += 1
  while warpFrom:
    h, w = warpFrom.popleft()
    move(h, w, WarpRange)

goal = maze[Dh][Dw]
print(goal) if not goal in ['.', '

Solution (Python):

import sys,math,collections,itertools
input = sys.stdin.readline
 
H,W=list(map(int,input().split()))
Ch,Cw=list(map(int,input().split()))
Dh,Dw=list(map(int,input().split()))
s=[ input().rstrip() for _ in range(H)]
 

dp = [ [float('inf') ]*W  for _ in range(H)]
 
q = collections.deque([])
q.append((Ch-1,Cw-1))
dp[Ch-1][Cw-1]=0
while q:
    visit = [] 
    while q:
        nh,nw = q.popleft()
        visit.append((nh,nw))
        
        move = [(-1,0),(1,0),(0,-1),(0,1)]
        for ih,iw in move:
            if  (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                    q.append((nh+ih,nw+iw))
                    dp[nh+ih][nw+iw] = dp[nh][nw]
    while visit:
    
        nh,nw = visit.pop()
        for ih in range(-2,3,1):
            for iw in range(-2,3,1):
                if (0<= nh+ih<=H-1) and (0<=nw+iw<=W-1):
                    if s[nh+ih][nw+iw] =='.' and dp[nh+ih][nw+iw]>dp[nh][nw]:
                        q.append((nh+ih,nw+iw))
                        dp[nh+ih][nw+iw] = dp[nh][nw]+1
     
 
ans = dp[Dh-1][Dw-1]
print(-1 if ans==float('inf') else ans)

Solution (Python):
import copy

from collections import deque
 
H, W = [int(x) for x in 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

cell = [list(input()) for i in range(H)]

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

copy_stack = []
copy_stack.append([Ch,Cw])

nstack = []

dp[Ch][Cw] = 0

def search(stack):
    while len(stack) > 0:
        h,w = stack.pop()
        for dy, dx in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
            nh = h + dy
            nw = w + dx
            if 0 <= nh < H and 0 <= nw < W and (dp[nh][nw] == -1 or dp[nh][nw] > dp[h][w]):
                if cell[nh][nw] == '.':
                    dp[nh][nw] = dp[h][w]
                    stack.append([nh,nw])
                    copy_stack.append([nh,nw])
                   
while True:
    if len(copy_stack):
        nstack = copy.copy(copy_stack)
    else:
        copy_stack = copy.copy(nstack)
    search(nstack)
    
    if dp[Dh][Dw] == -1:
        while len(copy_stack)>0:
            h,w = copy_stack.pop()
            for ddy in range(-2,3):
                for ddx in range(-2,3):
                    if ddy==ddx==0:
                        continue
                    nnh = h + ddy
                    nnw = w + ddx
                    if 0 <= nnh < H and 0 <= nnw < W:
                        if cell[nnh][nnw] == '.' and dp[nnh][nnw] == -1:
                            dp[nnh][nnw] = dp[h][w] + 1
                            nstack.append([nnh,nnw])
        if len(nstack) == 0:
            break
    else:
        break
                        
if dp[Dh][Dw] != -1:
    print(dp[Dh][Dw])
else:
    print(-1)

Solution (Python):
import heapq
class Dijkstra:
    INF = 10**13
    threshold = 10**6+1

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

def main():
    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    eh, ew = map(int, input().split())

    sh -= 1
    sw -= 1
    eh -= 1
    ew -= 1

    S = [input() for _ in range(h)]

    di = Dijkstra(h*w)
    for x in range(h):
        for y in range(w):
            if S[x][y] == '
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + i
                    Y = y + j
                    if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '
                    D = abs(i) + abs(j)

                    if D == 1: di.insert(x * w + y, X * w + Y, 0)
                    if D >= 2: di.insert(x * w + y, X * w + Y, 1)

    di.dijkstra(sh * w + sw)
    ans = di.dist[eh * w + ew]
    if ans == 10**13: print(-1)
    else: print(ans)

main()

Solution (Python):
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

def main():
    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    eh, ew = map(int, input().split())

    sh -= 1
    sw -= 1
    eh -= 1
    ew -= 1

    S = [input() for _ in range(h)]

    di = Dijkstra(h*w)
    for x in range(h):
        for y in range(w):
            if S[x][y] == '
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + i
                    Y = y + j
                    if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '
                    D = abs(i) + abs(j)

                    if D == 1: di.insert(x * w + y, X * w + Y, 0)
                    if D >= 2: di.insert(x * w + y, X * w + Y, 1)

    di.dijkstra(sh * w + sw)
    ans = di.dist[eh * w + ew]
    if ans == 10**18: print(-1)
    else: print(ans)

main()

Solution (Python):
from collections import deque


def bfs():
    
    d = [[float("inf")] * m for i in range(n)]
    
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    sx = c[0]
    sy = c[1]
    gx = g[0]
    gy = g[1]

    
    dd = []
    for i in range(-2,3):
        for j in range(-2,3):
            dd.append([i,j])

    
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    
    while que:
        
        p = que.popleft()
        
        if p[0] == gx and p[1] == gy:
            break
        
        for i in range(4):
            
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            
            
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] > d[p[0]][p[1]]:
                
                que.appendleft((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]
        for i in range(25):
            
            nx = p[0] + dd[i][0]
            ny = p[1] + dd[i][1]
            
            
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]+1

    return d[gx][gy]

n, m = map(int, input().split())
c = list(map(lambda x:int(x)-1,input().split()))
g = list(map(lambda x:int(x)-1,input().split()))
maze = [list(input()) for i in range(n)]

ans = bfs()
if ans == float("inf"):
    print(-1)
else:
    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=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h=deque([(ch-1,cw-1)])
c=0
while 1:
  done=[]
  while h:
    cx,cy=h.popleft()
    done.append((cx,cy))
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h or visited[dh-1][dw-1]!=-1:
    break
  c+=1
print(visited[dh-1][dw-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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
visited = [[0 for i in range(w)] for j in range(h)] 
t = [list(input()) for _ in range(h)]
d = deque([(Ch, Cw)])
d2 = deque()
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = range(-2, 3)

while True:
  
  while len(d) != 0:
    Th, Tw = d.popleft()
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b :
      for j in b :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[_h][_w] = 1
  if len(d) == 0:
    print('-1')
    exit()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] 
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[_h][_w] = 1
  if len(d) == 0:
    print('-1')
    exit()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
visited = [[0 for i in range(w)] for j in range(h)] 
t = [list(input()) for _ in range(h)]
d = deque([(Ch, Cw)])
d2 = deque()
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = range(-2, 3)

while True:
  
  while len(d) != 0:
    Th, Tw = d.popleft()
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b :
      for j in b :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[_h][_w] = 1
  if len(d) == 0:
    print('-1')
    exit()

Solution (Python):
from collections import deque

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

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

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

def p_dist():
    print('---')
    for row in dist:
        print(row)

while q:
    jump_list = []
    while q:
        v = q.popleft()
        jump_list.append(v)
        
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))

    cost += 1
    for v in jump_list:
        
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == v[1]:
                    pass
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == v[0]:
                    pass
                elif i == v[0] and j == v[1]:
                    pass
                elif i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                    
                    dist[i][j] = cost
                    q.append((i, j))


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

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

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

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) != (0, 0) and (i, j) not in walk:
            warp.append((i, j))

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())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] 
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[Th][Tw] = 1
  if len(d) == 0:
    print('-1')
    exit()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] 
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[Th][Tw] = 1
  if len(d) == 0:
    print('-1')
    exit()

Solution (Python):
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] 
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

Solution (Python):
from collections import deque

H,W=map(int,input().split())
C=tuple(map(int,input().split()))
D=tuple(map(int,input().split()))

S=["*"*(W+4)]*(H+4)

for x in range(H):
    S[x+2]="**"+input()+"**"

V=[]
for a in range(-2,3):
    for b in range(-2,3):
        if not(a==b==0):
            if abs(a)+abs(b)<=1:
                V.append(((a,b),0))
            else:
                V.append(((a,b),1))

inf=float("inf")
Dist=[[inf]*(W+1) for _ in range(H+1)]

Q=deque([C])
Dist[C[0]][C[1]]=0

while Q:
    (x,y)=Q.popleft()
    for ((a,b),c) in V:
        try:
            if S[x+a+1][y+b+1]=="." and Dist[x][y]+c<Dist[x+a][y+b]:
                Dist[x+a][y+b]=Dist[x][y]+c
                if c==0:
                    Q.appendleft((x+a,y+b))
                else:
                    Q.append((x+a,y+b))
        except:
            pass

if Dist[D[0]][D[1]]<inf:
    print(Dist[D[0]][D[1]])
else:
    print(-1)

Solution (Python):


from collections import deque

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())

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

q = deque([(CH - 1, CW - 1, 0)])

while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= h + i < H and 0 <= w + j < W and S[h + i][w + j] == '.':

                    
                    if abs(i) + abs(j) == 0:
                        continue

                    
                    elif abs(i) + abs(j) == 1:
                        q.appendleft((h + i, w + j, c))

                    
                    elif abs(i) + abs(j) >= 2:
                        q.append((h + i, w + j, c + 1))


if S[DH - 1][DW - 1] == '.':
    print(-1)

else:
    print(S[DH - 1][DW - 1])

Solution (Python):
import heapq

h, w = map(int, input().split())
i0, j0 = map(lambda x: int(x) - 1, input().split())
i1, j1 = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(h)]
inf = 10**10
D = [[inf] * w for i in range(h)]
D[i0][j0] = 0
Q = [(0, (i0, j0))]
heapq.heapify(Q)
while Q:
    _, (i, j) = heapq.heappop(Q)
    for di in range(-2, 3):
        for dj in range(-2, 3):
            ii, jj = i + di, j + dj
            if 0 <= ii < h and 0 <= jj < w and S[ii][jj] == ".":
                nex = int(abs(di) + abs(dj) != 1)
                if D[i][j] + nex < D[ii][jj]:
                    D[ii][jj] = D[i][j] + nex
                    heapq.heappush(Q, (D[ii][jj], (ii, jj)))
if D[i1][j1] >= inf:
    print(-1)
else:
    print(D[i1][j1])