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())
ch -= 1
cw -= 1
dh,dw = map(int, input().split())
dh -= 1
dw -= 1

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if xx == dh and yy == dw:
                return m[xx][yy]
            move(xx, yy, dq, dq_next)
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())

Solution (Python):
from collections import deque


def solve():
    H, W = map(int, input().split())
    C_h, C_w = map(lambda x: int(x) - 1, input().split())
    D_h, D_w = map(lambda x: int(x) - 1, input().split())
    field = [list(input()) for _ in range(H)]
    dp = [[float("inf")] * W for _ in range(H)]
    dp[C_h][C_w] = 0

    q = deque([(C_h, C_w)])
    visited = set()
    while q:
        i, j = q.popleft()
        if (i, j) in visited:
            continue
        visited.add((i, j))
        for di in range(-2, 3):
            for dj in range(-2, 3):
                if (di, dj) == (0, 0):
                    continue
                ni = i + di
                nj = j + dj
                if not (0 <= ni < H and 0 <= nj < W and field[ni][nj] == "."):
                    continue

                if (di, dj) in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j])
                    q.appendleft((ni, nj))
                else:
                    dp[ni][nj] = min(dp[ni][nj], dp[i][j] + 1)
                    q.append((ni, nj))
    ans = dp[D_h][D_w]
    print(-1) if ans == float("inf") else print(ans)


solve()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





H,W = IL()
sy,sx = IL()
gy,gx = IL()
data = SLs(H)
      
dx = [0,0,1,-1]
dy = [1,-1,0,0]

ddx = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]
ddy = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
 
def bfs(start):
  sy,sx = start
  d = [[INF]*W for i in range(H)]
  d[sy][sx] = 0
  q = deque([start])
  while q:
    y,x = q.popleft()
    for i in range(4):
      ny,nx = y+dy[i], x+dx[i]
      if nx<0 or nx>=W or ny<0 or ny>=H: continue
      if data[ny][nx]=="
      if d[ny][nx] <= d[y][x] : continue
      d[ny][nx] = d[y][x]
      q.appendleft((ny,nx))
    for i in range(25):
      ny,nx = y+ddy[i], x+ddx[i]
      if nx<0 or nx>=W or ny<0 or ny>=H: continue
      if data[ny][nx]=="
      if d[ny][nx] <= d[y][x] + 1 : continue
      d[ny][nx] = d[y][x] + 1
      q.append((ny,nx))
  return d
 
d = bfs((sy-1,sx-1))

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

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

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if xx == dh and yy == dw:
                return m[xx][yy]
            move(xx, yy, dq, dq_next)
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())

Solution (Python):
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) for _ in [H, W, ch, cw, dh, dw]]
ch -= 1
cw -= 1
dh -= 1
dw -= 1

stack = [[ch, cw]]
dist = [[None] * W for _ in range(H)]
d = 0
while True:
    stack2 = []
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        if dist[x][y] is not None:
            continue
        dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        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] is None and S[
                        nx][ny] == '.':
                    stack2 += [[nx, ny]]
    if stack2 == []:
        break
    else:
        d += 1
        stack = stack2
print(-1)

Solution (Python):
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = [(p, t)]
        broken_set = []
        while next_set:
            while next_set:
                p, t = next_set.pop()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if self.grid[q[0]][q[1]] == self.wall:         
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    if q == goal:
                        return t
                    
                    
                    
                    parent[q[0]][q[1]] = p
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.pop()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  
                    continue
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))




import sys
input = sys.stdin.readline



road, wall = ".", "

H, W = map(int,input().split())                
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Solution (Python):
from collections import defaultdict,deque

H, W = map(int, input().split())
S = list(map(int, input().split()))
G = list(map(int, input().split()))
S[0] -= 1
S[1] -= 1
G[0] -= 1
G[1] -= 1
c = [input() for i in range(H)]
dist = [[-1]*W for _ in range(H)]

for i in range(H):
    for g in range(W):
        if c[i][g] == "
            dist[i][g] = -2

checkList = set()
que = deque()
que.append(S)

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

cost = 0

while True:
    if len(que) == 0:
        cost += 1
        que = set()
        for h, w in checkList:
            for i in range(-2, 3):
                for g in range(-2, 3):
                    nh = h+i
                    nw = w+g
                    if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                        continue
                    else:
                        if dist[nh][nw] == -1:
                            que.add((nh, nw))
        que = deque(que)
        checkList = set()
        if len(que) == 0:
            print(-1)
            exit()
    else:
        h, w = que.popleft()
        dist[h][w] = cost
        if h == G[0] and w == G[1]:
            print(cost)
            exit()
        for i in range(4):
            nh = h+directions[i][0]
            nw = w+directions[i][1]
            if nw < 0 or nw > W-1 or nh < 0 or nh > H-1:
                continue
            if dist[nh][nw] == -1:
                que.append((nh, nw))
                dist[nh][nw] = cost
            elif dist[nh][nw] == -2:
                checkList.add((h, w))

Solution (Python):
import sys

class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

def solve():
    readline = sys.stdin.readline
    H, W = map(int, readline().split())
    ch, cw = map(int, readline().split())
    dh, dw = map(int, readline().split())
    S = ['
    for _ in range(H):
        S += ['
    S += ['
    H += 2
    W += 2

    uf = UnionFind(H*W)
    for i in range(H*W):
        if S[i] == '
            continue
        for d in [-W, -1, 1, W]:
            if S[i+d] == '.':
                uf.union(i, i+d)

    now = ch*(W) + cw
    goal = dh*(W) + dw
    
    
    if uf.same(now, goal):
        print(0)
        return
    ans = 0
    q = set()
    q.add(now) 
    next_area = set() 
    visited = [False] * (H*W)

    
    
    while True:
        while q:
            x = q.pop()
            if x == goal:
                print(ans)
                return
            visited[x] = True
            for dy in [-2*W, -W, 0, W, 2*W]:
                for dx in [-2, -1, 0, 1, 2]:
                    xx = x + dy + dx
                    if 0 <= xx < W*H and S[xx] == '.' and not visited[xx]:
                        if uf.same(x, xx):
                            q.add(xx)
                        else:
                            next_area.add(xx)
        if next_area:
            q = next_area
            next_area = set()
        else:
            print(-1)
            return 
        ans += 1

if __name__ == '__main__':
    solve()

Solution (Python):


import math
import sys

from collections import deque

h,w = map(int, input().split())

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

maze =["
temp = [[-1]*(w+4) for i in range(h+4)]



q = deque([(ch+1,cw+1)])
temp[ch+1][cw+1]=0

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

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

    
    for i in opt:
        ty,tx = y+i[0], x+i[1]
        if maze[ty][tx]=='
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x] 
            q.appendleft((ty,tx)) 
    
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i, x+j
            if maze[ty][tx] == "
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] =  temp[y][x]+1
                q.append((ty,tx))  



print(temp[dh+1][dw+1])

Solution (Python):
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     
        self.move2 = dict()
        self.move2[(1,0)] = [(2,-1),(2,0),(2,1),(2,2),(1,1)]
        self.move2[(-1,0)] = [(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]
        self.move2[(0,1)] = [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]
        self.move2[(0,-1)] = [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if self.grid[q[0]][q[1]] == self.wall:         
                        for dh2, dw2 in self.move2[(dh,dw)]:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    if q == goal:
                        return t
                    
                    
                    
                    parent[q[0]][q[1]] = p
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  
                    continue
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = 1
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))




from collections import deque
import sys
input = sys.stdin.readline



road, wall = ".", "

H, W = map(int,input().split())                
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

Solution (Python):
from collections import defaultdict
import sys
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
smat=[[x=="." for x in input()] for _ in range(H)]


graph=defaultdict(list)

for i in range(H):
  for j in range(W):
    if not smat[i][j]:
      continue
    
    for k in [-1,1]:
      if 0<=i+k<H and smat[i+k][j]:
        graph[i*W+j].append(((i+k)*W+j,0))
      if 0<=j+k<W and smat[i][j+k]:
        graph[i*W+j].append((i*W+j+k,0))

    for k1 in [-1,1]:
      for k2 in [-1,1]:
        if 0<=i+k1<H and 0<=j+k2<W and smat[i+k1][j+k2]:
          graph[i*W+j].append(((i+k1)*W+j+k2,1))

    for k in range(-2,3):
      if i-2>=0 and 0<=j+k<W and smat[i-2][j+k] :
        graph[i*W+j].append(((i-2)*W+j+k,1))
      if i+2<H and 0<=j+k<W and smat[i+2][j+k] :
        graph[i*W+j].append(((i+2)*W+j+k,1))
        
    for k in range(-1,2):
      if 0<=i+k<H and j-2>=0 and smat[i+k][j-2]:
        graph[i*W+j].append(((i+k)*W+j-2,1))
      if 0<=i+k<H and j+2<W and smat[i+k][j+2]:
        graph[i*W+j].append(((i+k)*W+j+2,1))

dist_mat=[-1]*(H*W)
queue=[(Ch-1)*W+Cw-1]
d=0
while queue:
  new_queue=set()

  while queue:
    u=queue.pop()
    if u==(Dh-1)*W+Dw-1:
      print(d)
      sys.exit(0)
    dist_mat[u]=d
    
    for v,w in graph[u]:
      if dist_mat[v]!=-1:
        continue
      if w==0:
        queue.append(v)
      else:
        new_queue.add(v)

  queue=list(new_queue)
  d+=1


print(-1)

Solution (Python):
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LS2(): return list(sys.stdin.readline().rstrip())  

H,W = MI()
sh,sw = MI()  
gh,gw = MI()  
S = [['
directions1 = [(-1,0),(1,0),(0,-1),(0,1)]
directions2 = [(i,j) for i in range(-2,3) for j in range(-2,3)]

from collections import deque



q = deque([(sh,sw)])
ans = [[-1]*(W+1) for _ in range(H+1)]
ans[sh][sw] = 0
while q:
    nh,nw = q.pop()
    for dh,dw in directions1:
        if 1 <= nh+dh <= H and 1 <= nw+dw <= W and S[nh+dh][nw+dw] == '.':
            if ans[nh+dh][nw+dw] == -1 or ans[nh+dh][nw+dw] > ans[nh][nw]:
                ans[nh+dh][nw+dw] = ans[nh][nw]
                q.append((nh+dh,nw+dw))
    for dh,dw in directions2:
        if 1 <= nh+dh <= H and 1 <= nw+dw <= W and S[nh+dh][nw+dw] == '.':
            if ans[nh+dh][nw+dw] == -1:
                ans[nh+dh][nw+dw] = ans[nh][nw] + 1
                q.appendleft((nh+dh,nw+dw))

print(ans[gh][gw])

Solution (Python):
from heapq import heapify, heappop, heappush
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 = []
heappush(q, (0, Ch*W+Cw))


while q:
    d, ij = heappop(q)
    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
                    heappush(q, (d, I*W+J))
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    heappush(q, (d+1, I*W+J))

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

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8
from heapq import *

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    q = [(0,S)]
    while q:
        dv, v = heappop(q)
        if dv > dist[v]:
            continue
        vx, vy = divmod(v, W)
        
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dv:
                continue
            dist[w] = dv
            heappush(q, (dv, w))
        
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dv + 1:
                    continue
                dist[w] = dv + 1
                heappush(q, (dv+1, w))
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'

print(main(wall, Sx, Sy, Tx, Ty))

Solution (Python):
from queue import deque
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

h,w = map(int,stdin.readline().rstrip().split())
ch,cw = map(int,stdin.readline().rstrip().split())
dh,dw = map(int,stdin.readline().rstrip().split())
inf = 10**10

ch -= 1
cw -= 1
dh -= 1
dw -= 1

def main():
    li = [["" for i in range(w)]for j in range(h)]

    for i in range(h):
        s = stdin.readline().rstrip()
        for j in range(w):
            li[i][j] = s[j]

    que = deque()

    mx = []
    my = []

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            mx.append(i)
            my.append(j)

    lin = [[inf for i in range(w)]for j in range(h)]
    lin[ch][cw] = 0
    que.append((ch,cw))

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

    while que:
        k = que.popleft()
        x = k[0]
        y = k[1]
        no_magic = set()

        for i,j in zip(dx,dy):
            nx = x + i
            ny = y + j

            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "
                continue
            else:
                if lin[nx][ny] > lin[x][y]:
                    que.appendleft((nx,ny))
                    no_magic.add((nx,ny))
                    lin[nx][ny] = lin[x][y]
        
        for i,j in zip(mx,my):
            nx = x + i
            ny = y + j

            if nx < 0 or nx >= h or ny < 0 or ny >= w:
                continue
            elif li[nx][ny] == "
                continue
            else:
                if lin[nx][ny] > lin[x][y]+1:
                    if (nx,ny) not in no_magic:
                        que.append((nx,ny))
                    lin[nx][ny] = lin[x][y]+1

    if lin[dh][dw] == inf:
        print(-1)
    else:
        print(lin[dh][dw])

if __name__ == "__main__":
    main()

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

def trans(s):
    res = []
    for i in s:
        if i == '.':
            res.append(-1)
        else:
            res.append(-2)
    return res

def move(x,y,dq,dq_next):
    for ix,iy in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if (m[ix][iy] == -1) or (m[ix][iy] > m[x][y]):
            m[ix][iy] = m[x][y]
            dq.append((ix, iy))
    for ix, iy in [(x-2, y-2), (x-2, y-1), (x-2, y), (x-2, y+1), (x-2, y+2),
                        (x-1, y-2), (x-1, y-1), (x-1, y+1), (x-1, y+2),
                        (x, y-2), (x, y+2),
                        (x+1, y-2), (x+1, y-1), (x+1, y+1), (x+1, y+2),
                        (x+2, y-2), (x+2, y-1), (x+2, y), (x+2, y+1), (x+2, y+2)]:
        if ix > h-1 or ix < 0 or iy > w-1 or iy < 0:
            continue
        if m[ix][iy] == -1:
            m[ix][iy] = m[x][y] + 1
            dq_next.append((ix, iy))
            
m = [trans(input()) for _ in range(h)]

from collections import deque

m[ch][cw] = 0

def main():
    dq = deque()
    dq_next = deque()
    dq.append((ch,cw))
    while True:
        while len(dq)>0:
            xx, yy = dq.popleft()
            if xx == dh and yy == dw:
                return m[xx][yy]
            move(xx, yy, dq, dq_next)
        if len(dq_next) > 0:
            dq = dq_next.copy()
            dq_next = deque()
        else:
            return -1
          
print(main())