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
def main():
    H,W = map(int, input().split())
    start = list(map(int, input().split()))
    goal = list(map(int, input().split()))
    field = [input() for _ in range(H)]

    wmap = [[-1] * W for _ in range(H)]
    wmap[start[0]-1][start[1]-1] = 0

    d = deque()
    d.appendleft((start[1]-1,start[0]-1))

    warpd = d.copy()

    def flood():
        while len(d) > 0:
            pos = d.pop()
            warpd.append(pos)
            posx, posy = pos
            w = wmap[posy][posx]
            for x,y in [(posx-1, posy), (posx+1, posy), (posx, posy-1), (posx, posy+1)]:
                if 0 <= x < W and 0 <= y < H and field[y][x] == "." and wmap[y][x] == -1:
                    wmap[y][x] = w
                    d.appendleft((x,y))
                    warpd.append((x,y))

    
    def warp():
        movable = set()
        while len(warpd) > 0:
            x,y = warpd.pop()
            w = wmap[y][x]
            
            for my in range(-2, 3):
                for mx in range(-2, 3):
                    px = x + mx
                    py = y + my
                    if 0 <= px < W and 0 <= py < H and field[py][px] == "." and wmap[py][px] == -1:
                        wmap[py][px] = w+1
                        movable.add((px,py))

        for item in movable:
            d.append(item)

    while len(d) != 0 and wmap[goal[0]-1][goal[1]-1] == -1:
        flood()
        warp()

    print(wmap[goal[0]-1][goal[1]-1])

if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappop, heappush
H,W = map(int,input().split()); base = 1000
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)

reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
visit = [[False]*W for _ in range(H)]
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = []
Q.append((0,C[0]+C[1]*base))
while Q:
  score,z = heappop(Q)
  x = z%base;y=z//base
  if visit[x][y]:
    continue
  visit[x][y] = True
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = nx+ny*base
      heappush(Q,(score,u))
  
 
  for i in range(5): 
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "
        continue
      if reach[mx][my] <= score+1: 
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = mx+my*base
      
      heappush(Q,(score+1,p))



if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])

Solution (Python):
from collections import deque

h, w = map(int, input().split())
cx, cy = map(lambda x: int(x) - 1, input().split())
dx, dy = map(lambda x: int(x) - 1, input().split())
s = [input() for _ in range(h)]
c = [[10**6] * w for _ in range(h)]


def bfs():
    d = ((1, 0), (-1, 0), (0, 1), (0, -1))
    q = deque([(cx, cy)])

    c[cx][cy] = 0

    while q:
        x, y = q.pop()
        cp = c[x][y]
        if (x, y) == (dx, dy):
            c[x][y] = cp
            break
        for i, j in d:
            nx = x + i
            ny = y + j
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                    ny] > cp:
                q.append((nx, ny))
                c[nx][ny] = cp
        cp += 1
        for i in range(-2, 3):
            for j in range(-2, 3):
                nx = x + i
                ny = y + j
                if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "
                        ny] > cp:
                    c[nx][ny] = cp
                    q.appendleft((nx, ny))

    return -1 * (c[dx][dy] == 10**6) or c[dx][dy]


print(bfs())

Solution (Python):
from collections import deque

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)]
D = [[-1] * w for i in range(h)]
Q = deque([(i0, j0, 0)])
while Q:
    i, j, cnt = Q.popleft()
    if D[i][j] != -1:
        continue
    D[i][j] = cnt
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if 0 <= i + di < h and 0 <= j + \
                    dj < w and S[i + di][j + dj] == "." and D[i + di][j + dj] == -1:
                if abs(di) + abs(dj) == 1:
                    Q.appendleft((i + di, j + dj, cnt))
                else:
                    Q.append((i + di, j + dj, cnt + 1))
print(D[i1][j1])

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)]
visited = [[False]*w for _ in range(h)]
ch -= 1
cw -= 1
dh -= 1
dw -= 1

coordinates = [(1,0),(0,1),(-1,0),(0,-1)]

que = deque([(0,ch,cw)])
while que:
    d,i,j = que.popleft()
    if (i,j) == (dh,dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for cdi,cdj in coordinates:
        ni,nj = i + cdi, j + cdj
        if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.':
            que.appendleft((d,ni,nj))
    for di in range(-2,3):
        for dj in range(-2,3):
            if di == dj == 0:
                continue
            ni,nj = i+di,j+dj
            if 0 <= ni < h and 0 <= nj < w and s[ni][nj] == '.' and not visited[ni][nj]:
                que.append((d+1,ni,nj))
print(-1)

Solution (Python):
h, w = map(int, input().split()) 
sy, sx = map(int, input().split()) 
gy, gx = map(int, input().split()) 
sy-=1
sx-=1
gy-=1
gx-=1
s = [input() for i in range(h)]

from collections import deque

q = deque([])
q.append([sy, sx, 0])

mx=[0,0,1,-1]
my=[1,-1,0,0]

vis = [[-1]*w for i in range(h)]
vis[sy][sx]=0

while len(q)>0:
  y, x, c = q.popleft()

  for i in range(4):
    nx=x+mx[i]
    ny=y+my[i]
    if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and (vis[ny][nx]>c or vis[ny][nx]==-1):
      vis[ny][nx]=c
      q.appendleft([ny,nx,c])
  
  for xi in range(5):
    for yi in range(5):
      nx=x+xi-2
      ny=y+yi-2    
      if 0<=nx<w and 0<=ny<h and s[ny][nx]=="." and vis[ny][nx]==-1:
        vis[ny][nx]=c+1
        q.append([ny,nx,c+1])
print(vis[gy][gx])

Solution (Python):
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [list(input()) for i in range(H)]
 
res_S = [[-1]*W for i in range(H)]
dx = [1,-1,0,0]
ddx = [-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2]
dy = [0,0,1,-1]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
count = 0
 
que = [(Ch,Cw)]
que_warp =[(Ch,Cw)]
res_S[Ch-1][Cw-1] = 0
 
while (que or que_warp):
    l = len(que)
    while (que):
        if l > 0:
            que_warp.append(que[0])
            l -= 1
        for i in range(4):
            nx = int(que[0][0]+dx[i])
            ny = int(que[0][1]+dy[i])
            if (1<=nx<=H) and (1<=ny<=W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1]=count
                    que.append((nx,ny))
                    que_warp.append((nx,ny))
        que.pop(0)
 
    count += 1
 
    while(que_warp):
        for i in range(len(ddx)):
            nx = int(que_warp[0][0] + ddx[i])
            ny = int(que_warp[0][1] + ddy[i])
            if (1 <= nx <= H) and (1 <= ny <= W):
                if res_S[nx-1][ny-1]<0 and S[nx-1][ny-1]=='.':
                    res_S[nx-1][ny-1] = count
                    que.append((nx, ny))
        que_warp.pop(0)
 
print (res_S[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())
maze = [list(input()) for _ in range(H)]
 
def BFS(maze,s,g):
  q1 = deque([s])
  checked = []
  cost = [[-1]*W for _ in range(H)]
  m = 0
  while q1:
    h,w,n = q1.popleft()
    if cost[h][w]<0:
      cost[h][w] = n
      if (h,w)==g: return n
      dp = [(x-2,y-2) for x in range(5) for y in range(5) if (x-2)!=0 or (y-2)!=0]
      for dh,dw in dp:
        if 0<=h+dh<H and 0<=w+dw<W and maze[h+dh][w+dw]==".":
          if (dh,dw) in [(-1,0),(1,0),(0,-1),(0,1)]:
            q1.appendleft((h+dh,w+dw,n))
          else:
            q1.append((h+dh,w+dw,n+1))
  return cost[g[0]][g[1]]
print(BFS(maze,(CH-1,CW-1,0),(DH-1,DW-1)))

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
 
 
def main():
    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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, noww+j])
                elif s2[nowh+i][noww+j] != '
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.appendleft([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])
    if s2[Dh][Dw] == '.':
        print(-1)
    else:
        print(s2[Dh][Dw])
 
 
if __name__ == '__main__':
    main()

Solution (Python):
import sys;input=sys.stdin.readline
H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
cx-=1;cy-=1;dx-=1;dy-=1
B = []
for _ in range(H):
    B.append(input().strip())

D = [0]*(H*W)
bb = -1
t = 0
t2c = dict()
for i in range(H):
    for j in range(W):
        if B[i][j] == "
            D[i*W+j] = bb
            continue
        if D[i*W+j]>0:
            continue
        t += 1
        t2c[t] = set()
        stack = [(i, j)]
        while stack:
            u, v = stack.pop()
            D[W*u+v] = t
            t2c[t].add((u, v))
            for x, y in [(u+1, v), (u-1, v), (u, v-1), (u, v+1)]:
                if x >= H or x<0:
                    continue
                if y >= W or y<0:
                    continue
                if B[x][y] == "
                    D[x*W+y] = bb
                    continue
                if D[x*W+y]:
                    continue
                stack.append((x, y))
depth = 0
cs = [D[cx*W+cy]]
tt = D[dx*W+dy]
vs = set([cs[0], -1])
if tt in vs:
    print(0)
    sys.exit()
while True:
    depth += 1
    nexts = []
    for c in cs:
        for i, j in t2c[c]:
            for ii in range(max(0, i-2), min(i+3, H)):
                for jj in range(max(0, j-2), min(j+3, W)):
                    if D[ii*W+jj] in vs:
                        continue
                    vs.add(D[ii*W+jj])
                    nexts.append(D[ii*W+jj])
                    if D[ii*W+jj] == tt:
                        print(depth)
                        sys.exit()
    cs = nexts
    if not cs:
        break
print(-1)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()
 
 
def main():
    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
    s2 = [list(input()) for i in range(h)]
    s2[Ch][Cw] = 0
    d = deque()
    d.append([Ch, Cw])
    while d:
        nowh, noww = d.popleft()
        if [nowh,noww]==[Dh,Dw]:
            print(s2[nowh][noww])
            exit()
        for i, j in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
            if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                if s2[nowh+i][noww+j] == '.':
                    s2[nowh+i][noww+j] = s2[nowh][noww]
                    d.appendleft([nowh+i, noww+j])
                elif s2[nowh+i][noww+j] != '
                    if s2[nowh+i][noww+j] > s2[nowh][noww]:
                        s2[nowh+i][noww+j] = s2[nowh][noww]
                        d.appendleft([nowh+i, noww+j])
        for i in [-2,-1,0,1,2]:
            for j in [-2,-1,0,1,2]:
                if ((0 <= nowh+i < h) and (0 <= noww+j < w)):
                    if s2[nowh+i][noww+j] == '.':
                        s2[nowh+i][noww+j] = s2[nowh][noww]+1
                        d.append([nowh+i, noww+j])
                    elif s2[nowh+i][noww+j] != '
                        if s2[nowh+i][noww+j] > s2[nowh][noww]+1:
                            s2[nowh+i][noww+j] = s2[nowh][noww]+1
                            d.append([nowh+i, noww+j])
    print(-1)
 
 
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())


mp = [[0]*w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        mp[i][j] = tmp[j]






q = deque()
dx1 = (-1, 0, 1, 0)
dy1 = (0,-1,0,1)
dx2 = (-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2)
dy2 = (-2,-1,0,1,2,-2,-1,1,2,-2,2,-2,-1,1,2,-2,-1,0,1,2)
q.append((ch-1,cw-1))

q2 = deque()

mpc = [[0]*w for _ in range(h)]

mpc[ch-1][cw-1] = 1
while q:
    x, y = q.popleft()
    for i in range(4): 
        nx = x+dx1[i]
        ny = y+dy1[i]
        if nx < 0 or nx >= h:
            continue
        if ny < 0 or ny >= w:
            continue
        if mp[nx][ny] == '.' and mpc[nx][ny] != mpc[x][y]:           
            mpc[nx][ny] = mpc[x][y]
            q.appendleft((nx,ny))

    for i in range(len(dx2)):
        nx = x+dx2[i]
        ny = y+dy2[i]
        if nx < 0 or nx >= h:
            continue
        if ny < 0 or ny >= w:
            continue
        if mp[nx][ny] == '.' and mpc[nx][ny] == 0:       
            mpc[nx][ny] = mpc[x][y] + 1
            q.append((nx,ny))
    



print(mpc[dh-1][dw-1]-1)

Solution (Python):
import sys
import os
from collections import deque

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")

INF = float("inf")

H,W = LI()
C = LI()
D = LI()
maze = [list(_S()) for i in range(H)]

def bfs():
    
    d = [[INF] * W for i in range(H)]
    
    sx = C[0]-1
    sy = C[1]-1
    gx = D[0]-1
    gy = D[1]-1

    
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    
    que2 = deque([])

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

    
    dx2 = [-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0, 1, 1,  1,  1, 2, 2, 2,  2, 2]
    dy2 = [-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, 2, 1, -1, -2, 2, 1, 0, -1, -2]

    while que: 
        while que:
            p = que.popleft()       
            
            if p[0] == gx and p[1] == gy:
                ans = d[p[0]][p[1]]
                print(ans)
                exit()
            que2.append((p[0], p[1]))
            
            for i in range(4):
                
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "
                    
                    que.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]
                    
        while que2:
            
            p = que2.popleft()
            for i in range(20):
            
            
                nx = p[0] + dx2[i]
                ny = p[1] + dy2[i]
                if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] != "
                    
                    que.append((nx, ny))
                    d[nx][ny] = d[p[0]][p[1]]+1  
        
    return

bfs()
print(-1)

Solution (Python):
import sys
readline=sys.stdin.readline

H,W=map(int,readline().split())

sy,sx = map(int,readline().split())
gy,gx = map(int,readline().split())

sy -= 1
sx -= 1
gy -= 1
gx -= 1

G = [None] * H
for i in range(H):
  G[i] = readline().rstrip()


INF = 10 ** 10
costs = [[INF] * W for i in range(H)]

from collections import deque
q = deque([])

q.append((sy,sx,0))

cases = {(0,1),(0,-1),(1,0),(-1,0)}
while q:
  y,x,co = q.popleft()
  if costs[y][x] <= co:
    continue
  if G[y][x] == "
    continue
  costs[y][x] = co
  for c in cases:
    if 0 <= y + c[0] < H and 0 <= x + c[1] < W:
      if G[y + c[0]][x + c[1]] == "
        continue
      if costs[y + c[0]][x + c[1]] <= co:
        continue
      q.appendleft((y + c[0], x + c[1], co))
  for i in range(-2,3):
    for j in range(-2,3):
      if (i,j) in cases or (i,j) == (0,0):
        continue
      if 0 <= y + i < H and 0 <= x + j < W:
        if G[y + i][x + j] == "
          continue
        if costs[y + i][x + j] <= co + 1:
          continue
        q.append((y + i, x + j, co + 1))

if costs[gy][gx] == INF:
  print(-1)
else:
  print(costs[gy][gx])

Solution (Python):

from collections import deque

H, W = [int(i) for i in input().split()]
ch, cw = [int(i)-1 for i in input().split()]
dh, dw = [int(i)-1 for i in input().split()]

S = [input() for i in range(H)]
cost = [[-1]*W for i in range(H)]

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

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


s=[input() for i in range(h)]

seen=[[0 for _ in range(w)] for _ in range(h)]
distance=[[10**7 for _ in range(w)] for _ in range(h)]

q=queue.Queue()

distance[ch][cw]=0
seen[ch][cw]=1
q.put([ch,cw])


while (not q.empty()) and distance[dh][dw]==10**7:
  sth,stw=q.get()
  qi=queue.Queue()
  qi.put([sth,stw])
  wlis=[]
  while not qi.empty():
    ph,pw=qi.get()
    cntp=0
    for nearh,nearw in [[ph-1,pw],[ph+1,pw],[ph,pw-1],[ph,pw+1]]:
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="." and seen[nearh][nearw]!=1:
        qi.put([nearh,nearw])
        seen[nearh][nearw]=1
        distance[nearh][nearw]=distance[ph][pw]
      if 0<=nearh<=h-1 and 0<=nearw<=w-1 and s[nearh][nearw]=="
        cntp+=1
    if cntp!=0:
      wlis.append([ph,pw])
  for i,j in wlis:
    for warph,warpw in [[i-2,j-2],[i-2,j-1],[i-2,j],[i-2,j+1],[i-2,j+2],
                        [i-1,j-2],[i-1,j-1],[i-1,j],[i-1,j+1],[i-1,j+2],
                        [i,j-2],[i,j-1],[i,j+1],[i,j+2],
                        [i+1,j-2],[i+1,j-1],[i+1,j],[i+1,j+1],[i+1,j+2],
                        [i+2,j-2],[i+2,j-1],[i+2,j],[i+2,j+1],[i+2,j+2]]:
      if 0<=warph<=h-1 and 0<=warpw<=w-1 and s[warph][warpw]=="." and seen[warph][warpw]==0:
        q.put([warph,warpw])
        seen[warph][warpw]=2
        distance[warph][warpw]=distance[i][j]+1



if distance[dh][dw]==10**7:
  print(-1)
else:
  print(distance[dh][dw])

Solution (Python):
from collections import deque

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
input = sys.stdin.readline

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
S = [input().rstrip() for _ in [0]*H]

INF = 10**10
D = [[INF]*W for _ in [0]*H]
used = set()

q = deque()
q.append((0, Ch*W+Cw))

while q:
    d, ij = q.popleft()
    i, j = divmod(ij, W)

    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di
            J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    q.appendleft((d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    q.append((d+1, I*W+J))
ans = D[Dh][Dw]
print(ans if ans < INF 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 = [list(input()) for _ in range(h)]

from collections import deque

q = deque([[ch, cw, 0]])
wall = deque()
visited = [[-1] * w for _ in range(h)]
visited[ch][cw] = 0
ans = -2
while True:
    
    while q:
        i, j, wc = q.popleft()
        if i == dh and j == dw:
            ans = wc
            break
        next_to_wall = False
        for mi, mj in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            ni, nj = i + mi, j + mj

            if 0 <= nj < w and 0 <= ni < h:
                if S[ni][nj] == '.' and visited[ni][nj] != wc:
                    visited[ni][nj] = wc
                    q.append([ni, nj, wc])
                elif S[ni][nj] == '
                    next_to_wall = True
        if next_to_wall:
            wall.append([i, j, wc])
    else:
        
        if not wall:
            ans = -1
    if ans > -2:
        break

    while wall:
        i, j, wc = wall.popleft()
        for wi, wj in ((-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)):
            ni, nj = i+wi, j+wj
            if (0 <= nj < w and 0 <= ni < h and S[ni][nj] == '.' and
                (visited[ni][nj] == -1 or visited[ni][nj] > wc+1)):
                visited[ni][nj] = wc+1
                q.append([ni, nj, wc+1])
print(ans)

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




def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))


from collections import deque

def main():
	h,w=MI()
	ch,cw=MI()
	dh,dw=MI()
	ch+=1
	cw+=1
	dh+=1
	dw+=1

	S=[["
	S.append(["
	for _ in range(h):
		S.append(["
	S.append(["
	S.append(["

	

	S[ch][cw]=0
	Q=deque()
	Q.append([0,ch,cw])


	d1=[(0,1),(0,-1),(-1,0),(1,0)]
	d2=[(i,j) for i in range(-2,3) for j in range(-2,3)]

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

		for xx,yy in d1:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d
				Q.appendleft([d,x+xx,y+yy])
			elif S[x+xx][y+yy]=="
				continue
			elif S[x+xx][y+yy]>d:
				S[x+xx][y+yy]=d
				Q.appendleft([d,x+xx,y+yy])

		for xx,yy in d2:
			if S[x+xx][y+yy]==".":
				S[x+xx][y+yy]=d+1
				Q.append([d+1,x+xx,y+yy])
			elif S[x+xx][y+yy]=="
				continue
			elif S[x+xx][y+yy]>d+1:
				S[x+xx][y+yy]=d+1
				Q.appendleft([d+1,x+xx,y+yy])



	

	print(-1 if S[dh][dw]=="." else S[dh][dw])


if __name__ == "__main__":
	main()

Solution (Python):
from collections import deque
import itertools


def bfs():
    H, W = map(int, input().split())
    C = list(map(int, input().split()))
    D = list(map(int, input().split()))
    S = [list(input()) for _ in range(H)]

    tests = (0, 1), (1, 0), (-1, 0), (0, -1)
    

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

    queue = deque()
    
    queue.append(start)

    while queue:
        w_n, x, y = queue.popleft()

        
        for dx, dy in tests:
            nx = x + dx
            ny = y + dy

            if not (0 <= nx < H):
                continue

            if not (0 <= ny < W):
                continue

            if S[nx][ny] != "
                if S[nx][ny] != "." and w_n >= S[nx][ny]:
                    continue
                else:
                    S[nx][ny] = w_n
                    queue.appendleft((w_n, nx, ny))

        
        for dx, dy in itertools.product(range(-2, 3), range(-2, 3)):
            nx = x + dx
            ny = y + dy

            if not (0 <= nx < H):
                continue

            if not (0 <= ny < W):
                continue

            if S[nx][ny] != "
                if S[nx][ny] != "." and w_n + 1 >= S[nx][ny]:
                    continue
                else:
                    S[nx][ny] = w_n + 1
                    queue.append((w_n + 1, nx, ny))

    if S[goal[0]][goal[1]] == ".":
        print(-1)
    else:
        print(S[goal[0]][goal[1]])


bfs()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))


def main():
    H, W = map(int, readline().split())
    Ch, Cw = map(int, readline().split())
    Dh, Dw = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    dist = [[-1] * W for _ in range(H)]
    dist[Ch][Cw] = 0
    queue = deque([(Ch, Cw)])
    while queue:
        x, y = queue.popleft()
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if (
                0 <= nx < H
                and 0 <= ny < W
                and (dist[nx][ny] == -1 or dist[nx][ny] > dist[x][y])
                and S[nx][ny] == '.'
            ):
                dist[nx][ny] = dist[x][y]
                queue.appendleft((nx, ny))
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] == -1 and S[nx][ny] == '.':
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))

    print(dist[Dh][Dw])
    return


if __name__ == '__main__':
    main()

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 functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

import heapq
def dijkstra(start, end):
	
	dist = [[float('inf')]*W for _ in range(H)]
	dist[start[0]][start[1]] = 0
	heap = []
	heapq.heappush(heap, (0, start))
	while heap:
		d, n = heapq.heappop(heap)
		if n == end:
			return d
		if dist[n[0]][n[1]] != d:
			continue
		edges = get_edges(n)
		for nn, ed in edges:
			nd = d + ed
			ni, nj = nn
			if dist[ni][nj] > nd:
				dist[ni][nj] = nd
				heapq.heappush(heap, (nd, nn))
	return -1

def get_edges(n):
	i, j = n
	edges = []
	if M[i][j] == '
	for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '
		edges.append(((ni, nj), 0))
	for di in range(-2, +3):
		for dj in range(-2, +3):
			ni, nj = i+di, j+dj
			if di == 0 and dj == 0: continue
			if (di, dj) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
				continue
			if not(0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '
			edges.append(((ni, nj), 1))
	return edges

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])
d = dijkstra(start, end)
print(d)

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