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

INF = 10 ** 9

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(map(lambda x: INF if x == "." else -1, [c for c in input()])) for _ in range(H)]


"""h = []
heapq.heappush(h, (0, Ch, Cw))"""

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

while len(q) != 0:
    d, nh, nw = q.popleft()
    if nh == Dh and nw == Dw:
        print(d)
        exit()

    for dh in [-2, -1, 0, 1, 2]:
        for dw in [-2, -1, 0, 1, 2]:
            flag = False
            if dh == 0 and dw == 0:
                continue
            newd = d + 1
            if abs(dh) + abs(dw) == 1:
                newd = d
                flag = True
            newh = nh + dh
            neww = nw + dw
            if 0 <= newh < H and 0 <= neww < W:
                if S[newh][neww] > newd:
                        S[newh][neww] = newd
                        if flag:
                            q.appendleft((newd, newh, neww))
                        else:
                            q.append((newd, newh, neww))   
print(-1)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





H, W = getNM()
Ch, Cw = getNM()
Dh, Dw = getNM()
maze = [input() for i in range(H)]
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1





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

pos = deque([[Ch, Cw]])
dp = [[-1] * W for i in range(H)]
dp[Ch][Cw] = 0

while len(pos) > 0:
    y, x = pos.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if 0 <= nx < W and 0 <= ny < H and maze[ny][nx] == "." and (dp[ny][nx] == -1 or dp[y][x] < dp[ny][nx]):
            
            
            pos.appendleft([ny, nx])
            dp[ny][nx] = dp[y][x]
    
    for i in range(-2, 3):
        for j in range(-2, 3):
            wy = y + i
            wx = x + j
            
            if 0 <= wx < W and 0 <= wy < H and maze[wy][wx] == "." and dp[wy][wx] == -1:
                pos.append([wy, wx])
                dp[wy][wx] = dp[y][x] + 1

print(dp[Dh][Dw])

Solution (Python):
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())

cy -= 1
cx -= 1
gy -= 1
gx -= 1

grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())

q = deque()

q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
                if nx == gx and ny == gy:
                    ans = min(ans, e+1)
                    continue
                
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e+1))

print(-1 if ans == float("inf") else ans)

Solution (Python):
H,W = map(int,input().split())
Ch, Cw = map(lambda x: int(x)-1,input().split())
Dh, Dw = map(lambda x: int(x)-1,input().split())
S = []
for i in range(H):
  S.append(input())


from collections import deque

def bfs(sh,sw):
  queue = deque([(sh,sw)])
  d = [[None]*W for _ in range(H)]
  now = set()
  d[sh][sw]=0
  
  while queue:
    h,w = queue.popleft()
    now.add((h,w))
    for nh,nw in [(h-1,w),(h+1,w),(h,w-1),(h,w+1)]:
      if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
      queue.append((nh,nw))
      now.add((nh,nw))
      d[nh][nw]=d[h][w]

    if queue: continue
    for h,w in now:
      for i in range(-2,3):
        for j in range(-2,3):
          if i==0 and abs(j)<=1: continue
          if j == 0 and abs(i)<=1: continue
          nh,nw = h-i,w-j
          if (0<=nh<=H-1 and 0<=nw<=W-1 and S[nh][nw] == '.' and d[nh][nw] is None) == False: continue
          d[nh][nw] = d[h][w]+1
          queue.append((nh,nw))
    now = set()
    
  return d

d = bfs(Ch,Cw)
if d[Dh][Dw] == None: 
  print(-1)
  exit()
print(d[Dh][Dw])

Solution (Python):
import collections

R, C = map(int, input().split())
sy, sx = map(lambda n: int(n) - 1, input().split())
gy, gx = map(lambda n: int(n) - 1, input().split())
c = [input() for _ in range(R)]

dist = [[-1 for _ in range(C)] for _ in range(R)]

q = collections.deque([(sy, sx, -1)])


G =     [(-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)] 

while q:
    y, x, d = q.popleft()

    if y < 0 or R <= y or x < 0 or C <= x:  
        continue

    if c[y][x] == '
        continue

    if dist[y][x] != -1:  
        continue

    dist[y][x] = d + 1
    
    for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
        q.appendleft((y + i, x + j, d ))
    for i,j in G:
        q.append((y+i,x+j,d+1))
print(dist[gy][gx])

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

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

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

    return -1


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

Solution (Python):
h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch -= 1
cw -= 1
dh,dw = map(int,input().split())
dh -= 1
dw -= 1
s = [input() for i in range(h)]

cost = [[-1]*w for i in range(h)]

from collections import deque
q = [[0,ch,cw]]
q = deque(q)

ans = -1
while q:
    cnt,cx,cy = q.popleft()
    if cost[cx][cy]<0:
        cost[cx][cy]=cnt
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=cx+dx<h and 0<=cy+dy<w and s[cx+dx][cy+dy]=='.':
                    if cost[cx+dx][cy+dy]<0:
                        if [dx,dy] in [[1,0],[-1,0],[0,1],[0,-1]]:
                            q.appendleft([cnt,cx+dx,cy+dy])
                        else:
                            q.append([cnt+1,cx+dx,cy+dy])

print(cost[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())
S = [list(input()) for _ in range(h)]



def clear_maze(h, w, ch, cw, dh, dw, S):
    visited = [[-1] * w for _ in range(h)]
    visited[ch - 1][cw - 1] = 0
    queue = deque([[ch - 1 , cw - 1]])
    m_queue = deque([])
    while queue or m_queue:
        if queue:
            y, x = queue.popleft()
        else:
            n_y, n_x, y, x = m_queue.popleft()
            if visited[n_y][n_x] != -1:
                continue
            visited[n_y][n_x] = visited[y][x] + 1
            y, x = n_y, n_x
        if [y, x] == [dh - 1, dw - 1]:
            return visited[y][x]
        num = 0
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            n_y = y + i
            n_x = x + j
            if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                visited[n_y][n_x] = visited[y][x]
                queue.append([n_y, n_x])
        for i in range(-2, 2 + 1):
            for j in range(-2, 2 + 1):
                if not [i, j] in ([1, 0], [-1, 0], [0, 0], [0, 1], [0, -1]):
                    n_y = y + i
                    n_x = x + j
                    if n_y >= 0 and n_y < h and n_x >= 0 and n_x < w and S[n_y][n_x] == '.' and visited[n_y][n_x] == -1:
                        m_queue.append([n_y, n_x, y, x])
    return -1

print(clear_maze(h, w, ch, cw, dh, dw, S))

Solution (Python):
from collections import deque
h,w=map(int,input().split())
cx,cy=map(int,input().split())
cx+=1
cy+=1
dx,dy=map(int,input().split())
dx+=1
dy+=1
l=[]
l.append("
l.append("
for i in range(h):
    l.append("
l.append("
l.append("


"""
for i in l:
    print(*i)
"""

q=deque([[cx,cy]])
qq=deque([[cx,cy]])
s=[[-1 for i in j]for j in l]
s[cx][cy]=0

while len(qq)>0:
    while len(q)>0:
        x,y=q.popleft()
        for px,py in ((0,1),(0,-1),(1,0),(-1,0)):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]
                q.appendleft([x+px,y+py])
                qq.append([x+px,y+py])
    x,y=qq.popleft()
    for px in range(-2,3):
        for py in range(-2,3):
            if l[x+px][py+y]=="." and s[x+px][y+py]==-1:
                s[x+px][y+py]=s[x][y]+1
                q.append([x+px,y+py])
                qq.append([x+px,y+py])
"""
for i in s:
    print(*i)
"""

print(s[dx][dy])

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

visited = [[0 for j in range(W)] for i in range(H)]
seen = [[0 for j in range(W)] for i in range(H)]
done = set()

def bfs(u, done):
    stack = deque([u])
    seen[u[0]][u[1]] = 1

    while len(stack) > 0:
        v = stack.popleft()
        done.add(v)
        visited[v[0]][v[1]] = 1
        
        w1 = (v[0] + 1, v[1])
        w2 = (v[0] , v[1] + 1)
        w3 = (v[0] - 1, v[1])
        w4 = (v[0] , v[1] -1)
        

        ws = [w1,w2,w3,w4]

        for w in ws:
            if w[0] >= 0 and w[0] < H and w[1] >= 0 and w[1] < W:
                if S[w[0]][w[1]] == ".":
                    if seen[w[0]][w[1]] == 0:
                        stack.append(w)
                        seen[w[0]][w[1]] = 1

bfs((Ch-1,Cw-1), done)

count = 0




while True:
    if visited[Dh-1][Dw-1] == 1:
        print(count)
        sys.exit()
    else:
        count += 1
        pp = deque([])
        for d in list(done):
            i = d[0]
            j = d[1]
            for k in range(-2,3):
                for l in range(-2,3):
                    if i+k >= 0 and i+k < H and j+l >= 0 and j+l < W:
                        if S[i+k][j+l] == ".":
                            if visited[i+k][j+l] == 0:
                                pp.append((i+k,j+l))

        if len(pp) == 0:
            print(-1)
            break

        done = set()
        for ppp in pp:
            bfs(ppp, done)

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

group=[[-1 for j in range(W)] for i in range(H)]

g=0

def bfs(x,y):
    global g
    group[x][y]=g
    deq=deque([(x,y)])
    while deq:
        h,w=deq.popleft()
        for i in range(-1,2):
            for j in range(-1,2):
                if i*j==0 and (i,j)!=(0,0) and 0<=h+i<H and 0<=w+j<W and S[h+i][w+j]=="." and group[h+i][w+j]==-1:
                    group[h+i][w+j]=g
                    deq.append((h+i,w+j))
    g+=1

for i in range(H):
    for j in range(W):
        if group[i][j]==-1 and S[i][j]==".":
            bfs(i,j)

edge=[[] for i in range(g)]

for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            for k in range(-2,3):
                for l in range(-2,3):
                    if 0<=i+k<H and 0<=j+l<W and group[i+k][j+l]!=-1:
                        edge[group[i][j]].append(group[i+k][j+l])

dist=[10**18 for i in range(g)]
dist[group[Ch][Cw]]=0
deq=deque([group[Ch][Cw]])
while deq:
    v=deq.popleft()
    for nv in edge[v]:
        if dist[nv]>dist[v]+1 and nv!=-1:
            dist[nv]=dist[v]+1
            deq.append(nv)

if dist[group[Dh][Dw]]!=10**18:
    print(dist[group[Dh][Dw]])
else:
    print(-1)