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


def inValidRegion(i,j,H,W):
    return i >= 0 and i < H and j >= 0 and j < W



def main():
    
    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()))
    
    R = []
    for i in range(H):
        R.append([])
        for j in range(W):
            R[i].append(-1 if S[i][j]=="
    currentId = 1
    for ii in range(H):
        for ij in range(W):
            if R[ii][ij] != 0:
                continue
            init = (ii,ij)
            c = set()
            c.add(init)
            while len(c) > 0:
                i,j = c.pop()
                R[i][j] = currentId
                if inValidRegion(i+1,j,H,W) and R[i+1][j] == 0:
                    c.add((i+1,j))
                if inValidRegion(i,j+1,H,W) and  R[i][j+1] == 0:
                    c.add((i,j+1))
                if inValidRegion(i-1,j,H,W) and R[i-1][j] == 0:
                    c.add((i-1,j))
                if inValidRegion(i,j-1,H,W) and  R[i][j-1] == 0:
                    c.add((i,j-1))
            currentId+=1
    
    Connections = [set() for i in range(currentId)]
    Ca = R[Ch-1][Cw-1]
    Da = R[Dh-1][Dw-1]
    
    
    if Ca == Da:
        print(0)
    else:
        for i in range(H):
            for j in range(W):
                a = R[i][j]
                if a == -1:
                    continue
                for k in range(-2,3):
                    for l in range(-2,3):
                        if inValidRegion(i+k,j+l,H,W):
                            a2 = R[i+k][j+l]
                            if a2 != a and a2 > 0:
                                Connections[a].add(a2)
                                Connections[a2].add(a)
        
        reached = set([Ca])
        nextSet = set([Ca])
        warp = 0
        while len(nextSet) > 0:
            currentSet = nextSet
            nextSet = set()
            warp += 1
            while len(currentSet) > 0:
                current = currentSet.pop()
                for c in Connections[current]:
                    if c not in reached:
                        reached.add(c)
                        nextSet.add(c)
                    if c == Da:
                        print(warp)
                        return
        print(-1)

    pass

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

def walk(i, j):
    ans = []
    for h, w in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
        
        if h >= 0 and w >= 0 and h < H and w < W:
            
            if S[h][w] == '.':
                if maze[h][w] == -1:
                    ans.append((h, w))
    return ans

def warp(i, j):
    tmp = []
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if not (dh == 0 and dw == 0):
                tmp.append([i + dh, j + dw])
    ans = []
    for h, w in tmp:
        if h >= 0 and w >= 0 and h < H and w < W:
            if S[h][w] == '.':
                if maze[h][w] == -1:
                    ans.append((h, w))
    return ans

maze = [[-1]*W for _ in range(H)]
warp_n = 0
maze[Ch][Cw] = 0
walk_stack= deque(walk(Ch, Cw))
warp_set = set(warp(Ch, Cw))



while walk_stack or warp_set:
    while walk_stack:
        h, w = walk_stack.pop()
        if maze[h][w] == -1:
            maze[h][w] = warp_n
            walk_stack.extend(walk(h, w))
            warp_set |= set(warp(h, w))
    warp_n += 1
    
    
    next_warp = set()
    for h, w in warp_set:
        if maze[h][w] == -1:
            maze[h][w] = warp_n
            walk_stack.extend(walk(h, w))
            next_warp |= set(warp(h, w))
    warp_set = next_warp
print(maze[Dh][Dw])

Solution (Python):
import sys
from collections import deque
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 = []
for _ in range(H):
    S.append(input())
P = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            P[i][j] = -1
P[Ch][Cw] = 1
P[Dh][Dw] = 100
yudlr = [0, 0, 1, -1]
xudlr = [1, -1, 0, 0]
D = deque()
Q = deque()
Q.append([Ch, Cw])
c = 0
while len(Q) > 0 or len(D) > 0:
    while len(Q) > 0:
        q = Q.popleft()
        y, x = q[0], q[1]
        for i in range(4):
            y1 = y + yudlr[i]
            x1 = x + xudlr[i]
            if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                continue
            if P[y1][x1] == 100:
                print(c)
                sys.exit()
            if P[y1][x1] == -1 and P[y][x] == 1:
                D.append([y, x])
                P[y][x] = 2
                continue
            if P[y1][x1] != 0:
                continue
            Q.append([y1, x1])
            P[y1][x1] = 1
    c += 1
    while len(D) > 0:
        d = D.popleft()
        y, x = d[0], d[1]
        for i in range(-2, 3):
            for j in range(-2, 3):
                y1 = y + i
                x1 = x + j
                if y1 < 0 or y1 >= H or x1 < 0 or x1 >= W:
                    continue
                if P[y1][x1] == 100:
                    print(c)
                    sys.exit()
                if P[y1][x1] != 0:
                    continue
                Q.append([y1, x1])
                P[y1][x1] = 1
print(-1)

Solution (Python):
h,w = map(int,input().split())
a,b = map(int,input().split())
c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1

g = []
for _ in range(h):
    s = list(input())
    tmp = []
    for i in s:
        tmp.append(i)
    g.append(tmp)
if g[c][d] =='
from collections import deque
q = deque([])
p  =deque([])
dp = [[float('inf')]*w for _ in range(h)]

q.append((a,b,0))
dist = [(1,0),(0,1),(0,-1),(-1,0)]
seen = [[False]*w for _ in range(h)]

dp[a][b] = 0
seen[a][b] = True

while p or q:
    while q:
        x,y,cnt = q.popleft()
        p.append((x,y,cnt+1))
        for dx,dy in dist:
            X = x+dx
            Y = y + dy
            if 0<=X<h and 0<=Y<w and not seen[X][Y] and g[X][Y]=='.':
                if dp[X][Y]>cnt:
                    dp[X][Y] = min(dp[X][Y],cnt)
                    seen[X][Y] = True
                    q.append((X,Y,cnt))
                    p.append((X,Y,cnt+1))
    while p:
        x,y,cnt = p.popleft()
        for dx in range(-2,3,1):
            for dy in range(-2,3,1):
                X = x+dx
                Y = y + dy
                if 0<=X<h and 0<=Y<w and not seen[X][Y] and g[X][Y]=='.':
                    if dp[X][Y]>cnt:
                        dp[X][Y] = min(dp[X][Y],cnt)
                        seen[X][Y] = True
                        q.append((X,Y,cnt))
    
print(dp[c][d] if dp[c][d]!=float('inf') else -1)

Solution (Python):
from sys import stdin
from collections import deque
input = stdin.readline

H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = [list(input().rstrip()) for _ in range(H)]

dir_h = [0, 0, 1, -1]
dir_w = [1, -1, 0, 0]

seen = [[-1 for _ in range(W)] for _ in range(H)]
edge = []
nex = [[ch - 1, cw - 1]]
num = 0
group = [[-1 for _ in range(W)] for _ in range(H)]


def bfs():
    q = deque([])

    for h, w in nex:
        if seen[h][w] != -1:
            continue
        q.append([h, w])
        seen[h][w] = num
        while q:
            h, w = q.popleft()

            for dh, dw in zip(dir_h, dir_w):
                nh, nw = h + dh, w + dw

                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                elif S[nh][nw] == "
                    edge.append([h, w])
                    continue
                elif seen[nh][nw] != -1:
                    continue
                else:
                    seen[nh][nw] = num
                    q.append([nh, nw])


def dfs():
    d = deque([])
    for h, w in edge:
        d.append([h, w])

        while d:
            h, w = d.pop()
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw

                    if nh < 0 or nh >= H or nw < 0 or nw >= W:
                        continue
                    elif S[nh][nw] == "
                        continue
                    elif seen[nh][nw] != -1:
                        continue
                    else:
                        nex.append([nh, nw])


while True:
    bfs()
    if not edge:
        break
    nex = []
    num += 1
    dfs()
    if not nex:
        break
    edge = []




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

Solution (Python):
H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
S = []
for i in range(H):
  S.append(str(input()))
  
def main(h, w, cnt):
  global H
  global W
  global S
  tmp = []
  if (h<H-1) and (S[h+1][w]=='.') and (ans[h+1][w]<0):
    ans[h+1][w] = cnt
    tmp.append([h+1, w])
  if (w<W-1) and (S[h][w+1]=='.') and (ans[h][w+1]<0):
    ans[h][w+1] = cnt
    tmp.append([h, w+1])
  if (0<h) and (S[h-1][w]=='.') and (ans[h-1][w]<0):
    ans[h-1][w] = cnt
    tmp.append([h-1, w])
  if (0<w) and (S[h][w-1]=='.') and (ans[h][w-1]<0):
    ans[h][w-1] = cnt
    tmp.append([h, w-1])
  return tmp

def sub(h, w, cnt):
  global H
  global W
  global S
  tmp = []
  for x in range(max(h-2, 0), min(h+3, H)):
    for y in range(max(w-2, 0), min(w+3, W)):
      if (S[x][y]=='.') and (ans[x][y]<0):
        ans[x][y] = cnt
        tmp.append([x, y])
  return tmp

ans = [[-1]*W for i in range(H)]
ans[ch-1][cw-1] = 0
lis = [[ch-1, cw-1]]
li = [[ch-1, cw-1]]
flag = False
for i in range(1000000):
  for j in range(1000000):
    l = []
    for n in li:
      l += main(n[0], n[1], i)
    if l == []:
      break
    elif [dh-1, dw-1] in l:
      flag = True
      break
    else:
      lis += l
      li = l
  if flag:
    break
  else:
    z = []
    for m in lis:
      z += sub(m[0], m[1], i+1)
    if z == []:
      break
    else:
      lis = z
      li = z
print(ans[dh-1][dw-1])

Solution (Python):
[H, W] = map(int, input().split())
[Ch, Cw] = map(int, input().split())
[Dh, Dw] = map(int, input().split())

mp = []
for i in range(H):
    mp.append(list(input()))

[Ch, Cw, Dh, Dw] = [Ch-1, Cw-1, Dh-1, Dw-1] 

cur = [[Ch, Cw]] 
walked = [[Ch, Cw]]
steps = 0
step = [[1, 0], [0, 1], [-1, 0], [0, -1]]
warp = [[i, j] for i in range(-2, 3) for j in range(-2, 3) if not i==j==0]

while True:
    current = cur.pop()

    for i in range(len(step)):
        nxt = [ current[0]+step[i][0], current[1]+step[i][1] ]
        if nxt[0] == Dh and nxt[1] == Dw:
            print (steps)
            quit()
        if 0<=nxt[0] <H and 0<=nxt[1]<W:
            if mp[nxt[0]][nxt[1]] == '
                pass
            elif mp[nxt[0]][nxt[1]] == '.': 
                mp[nxt[0]][nxt[1]] = 'X'
                cur.append([nxt[0], nxt[1]])
                walked.append([nxt[0], nxt[1]])
    if len(cur) > 0: continue

    
    steps += 1
    for j in range(len(walked)):
        current = walked.pop()
        for i in range(len(warp)):
            nxt = [ current[0]+warp[i][0], current[1]+warp[i][1] ]
            if nxt[0] == Dh and nxt[1] == Dw:
                print (steps)
                quit()
            if 0<=nxt[0]<H and 0<=nxt[1]<W:
                if mp[nxt[0]][nxt[1]] == '
                    pass
                elif mp[nxt[0]][nxt[1]] == '.': 
                    mp[nxt[0]][nxt[1]] = 'X'
                    cur.append([nxt[0], nxt[1]])
    if len(cur) == 0:
        print('-1')
        quit()
    walked = cur.copy()

Solution (Python):
import collections

h, w = map(int, input().split())
src_y, src_x = map(int, input().split())
dst_y, dst_x = map(int, input().split())
src_y -= 1
dst_y -= 1
src_x -= 1
dst_x -= 1
grid = [input() for _ in range(h)]

UNDEF = -1
colors = [[UNDEF] * w for _ in range(h)]


ncolors = 0
def paint(grid, colors):
    global ncolors
    for y in range(h):
        for x in range(w):
            if grid[y][x] == '.' and colors[y][x] == UNDEF:
                q = collections.deque()
                colors[y][x] = ncolors
                q.append((y, x))
                while q:
                    i, j = q.popleft()

                    for ii, jj in (
                        (i - 1, j),
                        (i, j - 1),
                        (i, j + 1),
                        (i + 1, j)
                    ):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] == UNDEF and grid[ii][jj] == '.':
                            colors[ii][jj] = ncolors
                            q.append((ii, jj))
                ncolors += 1

paint(grid, colors)


def build(grid, colors, ncolors):
    g = [set() for _ in range(ncolors)]
    for i in range(h):
        for j in range(w):
            if colors[i][j] != UNDEF:
                for ii in range(i - 2, i + 3):
                    for jj in range(j - 2, j + 3):
                        if 0 <= ii < h and 0 <= jj < w and colors[ii][jj] != colors[i][j] and colors[ii][jj] != UNDEF:
                            c1 = colors[ii][jj]
                            c2 = colors[i][j]
                            assert c1 != UNDEF and c2 != UNDEF
                            g[c1].add(c2)
                            g[c2].add(c1)
    return g

g = build(grid, colors, ncolors)

q = collections.deque()
src_color = colors[src_y][src_x]
dst_color = colors[dst_y][dst_x]
q.append((src_color, 0))
vis = [0] * ncolors
vis[src_color] = 1
ans = -1
while q:
    color, dist = q.popleft()
    if color == dst_color:
        ans = dist
        break
    for other in g[color]:
        if not vis[other]:
            q.append((other, dist + 1))
            vis[other] = 1

print(ans)

Solution (Python):
def resolve():
    H, W = list(map(int, input().split()))
    Ch, Cw = list(map(lambda x: int(x)-1, input().split()))
    Dh, Dw = list(map(lambda x: int(x)-1, input().split()))
    S = [list(input()) for _ in range(H)]
    warps = [[-1 for _ in range(W)] for __ in range(H)]
    warpcnt = 0
    import collections
    warp_to = set()
    q = collections.deque([(Ch, Cw)])
    while q:
        while q:
            h, w = q.pop()
            if warps[h][w] != -1:
                continue
            warps[h][w] = warpcnt
            for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                nh = h+dh
                nw = w+dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and warps[nh][nw] == -1:
                    q.appendleft((nh, nw))
            for dh, dw 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)]:
                nh = h+dh
                nw = w+dw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == "." and warps[nh][nw] == -1:
                    warp_to.add((nh, nw))
        q = collections.deque(list(warp_to))
        warp_to = set()
        warpcnt += 1
    print(warps[Dh][Dw])

if '__main__' == __name__:
    resolve()

Solution (Python):
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): 
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    D = [[S[0], S[1]]]
    while True:
      while not q.empty():
        h, w = q.get()
        k = T[h][w]
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
          hh = h + i
          ww = w + j
          if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
            q.put([hh, ww])
            D.append([hh, ww])
            T[hh][ww] = k
      if len(D) == 0: break
      ND = []
      for h, w in D:
        for i in range(-2, 3):
          for j in range(-2, 3):
            hh = h + i
            ww = w + j
            if hh < 0: continue
            if hh > H: continue
            if ww < 0: continue
            if ww > W:continue
            if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k + 1):
              q.put([hh, ww])
              ND.append([hh, ww])
              T[hh][ww] = k + 1
      D = ND

    return T, k


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

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1

G = gridMan(S)
G.makeWall()

T, k = G.dist([C[0] - 1, C[1] - 1])

print(T[D[0] - 1][D[1] - 1])

Solution (Python):
from heapq import heappush, heappop
inf = float('inf')
def dijkstra(graph:list, node:int, start:int) -> list:
    
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

class UnionFind:
    def __init__(self, num):
        self.table = [-1 for _ in range(num)]

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

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

        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]

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

u = UnionFind(H*W)
for sh in range(H):
    for sw in range(W):
        if S[sh][sw]=='
            continue
        for dx,dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            if 0<=sh+dx<=H-1 and 0<=sw+dy<=W-1 and S[sh+dx][sw+dy]=='.':
                    u.union(sh*W+sw,(sh+dx)*W+sw+dy)
d = {}
n = 0
for sh in range(H):
    for sw in range(W):
        f = u.find(sh*W+sw)
        if f not in d:
            d[f] = n
            n += 1

graph = [[] for _ in range(len(d))]
for sh in range(H):
    for sw in range(W):
        if S[sh][sw]=='
            continue
        f1 = u.find(sh*W+sw)
        for dx in range(-2,3):
            for dy in range(-2,3):
                if 0<=sh+dx<=H-1 and 0<=sw+dy<=W-1 and S[sh+dx][sw+dy]=='.':
                        f2 = u.find((sh+dx)*W+sw+dy)
                        graph[d[f1]].append((1,d[f2]))

dist = dijkstra(graph, len(d), d[u.find(Ch*W+Cw)])
ans = dist[d[u.find(Dh*W+Dw)]]
if ans == inf:
    ans = -1
print(ans)

Solution (Python):
H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
grid = ""
for i in range(H):
    grid += input()
grid = list(grid)

def convert_1d_to_2d(l, cols):
    return [l[i:i + cols] for i in range(0, len(l), cols)]

grid = convert_1d_to_2d(grid, W)

ans = [[1000000]*W for i in range(H)]
ans[Ch-1][Cw-1]=0

from collections import deque
ans = [[1000000]*W for i in range(H)]
ans[Ch-1][Cw-1]=0

from collections import deque

que = deque([[Ch-1,Cw-1]])
que2 = deque([[Ch-1,Cw-1]])

while que or que2:
    if que:
        x,y=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que.append([nextx,nexty])

        for i,j in [(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,2),(-1,1),(-1,-1),(-1,-2)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]+1

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que2.append([nextx,nexty])
            
    else:
        x,y=que2.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que.append([nextx,nexty])

        for i,j in [(2,2),(2,1),(2,0),(2,-1),(2,-2),(1,2),(1,1),(1,-1),(1,-2),(0,2),(0,-2),(-2,2),(-2,1),(-2,0),(-2,-1),(-2,-2),(-1,2),(-1,1),(-1,-1),(-1,-2)]:
            nextx,nexty=x+i,y+j
            check = ans[x][y]+1

            if nextx>=0 and nexty>=0 and nextx<=H-1 and nexty<=W-1:
                dist=grid[nextx][nexty]
                if dist!='
                    if check<ans[nextx][nexty]:
                        ans[nextx][nexty]=check
                        que2.append([nextx,nexty])
        
                    
if ans[Dh-1][Dw-1]==1000000:
    print("-1")
else:
    print(ans[Dh-1][Dw-1])

Solution (Python):

from collections import deque
import sys
INF = 10000000

H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for _ in range(H)]
C = [[INF]*W for _ in range(H)]
C[Ch-1][Cw-1] = 0
que = deque([(Ch,Cw)])
now = set()
tmp = 0

while True:
    while len(que)>0:
        i,j = que.popleft()
        now.add((i,j))
        for (h,w) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
            if 1<=h<=H and 1<=w<=W and S[h-1][w-1]=='.' and C[h-1][w-1]>tmp:
                C[h-1][w-1] = tmp
                que.append((h,w))
    for i,j in now:
        for h in range(i-2,i+3):
            for w in range(j-2,j+3):
                if 1<=h<=H and 1<=w<=W and S[h-1][w-1]=='.' and C[h-1][w-1]>tmp+1:
                    C[h-1][w-1] = tmp+1
                    que.append((h,w))
    now = set()
    tmp += 1
    if C[Dh-1][Dw-1]!=INF:
        print(C[Dh-1][Dw-1])
        break
    if len(que)==0:
        print(-1)
        break

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

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)
    deq = np.empty(2 * H * W + 100, np.int64)
    dist[S] = 0
    deq[H * W], l, r = S, H * W, H * W + 1
    while l < r:
        v, l = deq[l], l + 1
        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] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        
        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] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    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 sys import stdin
def input():
    return stdin.readline().strip()

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
g = ['
for _ in range(h):
    g.append('
g.append('
g.append('

d1 = [(-1, 0), (0, -1), (0, 1), (1, 0)]
d2 = [(-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)]

from collections import deque

seen = [[-1] * (w+2) for _ in range(h+2)]
todo = deque([(0, ch, cw)])
while len(todo) > 0:
    history = []
    while len(todo) > 0:
        cost, x, y = todo.popleft()
        if seen[x][y] == -1:
            if x == dh and y == dw:
                print(cost)
                exit()
            seen[x][y] = cost
            history.append((cost, x, y))
        else:
            continue

        for i in range(4):
            dx, dy = d1[i]
            if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
                todo.append((cost, x+dx, y+dy))

    for j in history:
        cost, x, y = j
        for i in range(20):
            dx, dy = d2[i]
            if g[x+dx][y+dy] == '.' and seen[x+dx][y+dy] == -1:
                todo.append((cost+1, x+dx, y+dy))

print(-1)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.buffer.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

c = cx*w + cy
d = dx*w + dy


s = []
for i in range(h):
    s.append(list(input()))

a = [10**6]*(h*w)
a[c] = 0

tank = deque([c])
used = [False]*(h*w)

while tank:
    now = tank.popleft()
    if used[now]:
        continue
    used[now] = True

    x,y = divmod(now,w)

    cost = a[now]

    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                continue
            if (0 <= x+i < h) and (0 <= y+j < w) and (not used[(x+i)*w + y+j]) and s[x+i][y+j] == 46:
                if (i == 0 and (j == 1 or j == -1)) or (j == 0 and (i == 1 or i == -1)):
                    tank.appendleft((x+i)*w + y+j)
                    a[(x+i)*w + y+j] = min(a[(x+i)*w + y+j],cost)
                else:
                    tank.append((x+i)*w + y+j)
                    a[(x+i)*w + y+j] = min(a[(x+i)*w + y+j],cost + 1)

if a[d] == 10**6:
    print(-1)
else:
    print(a[d])

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd



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)]
seen=[[0]*w for _ in range(h)]
d=deque()
ch-=1
cw-=1
dh-=1
dw-=1
res=[]
p=[[0,1],[0,-1],[1,0],[-1,0]]

seen[ch][cw]=1
d.append(ch*w+cw)
ans=0
while True:
    z=d.pop()
    x=z//w 
    y=z%w
    res.append([x,y])
    for v in p:
        i,j=v
        if 0<=x+i<h and 0<=y+j<w and seen[x+i][y+j]==0:
            if s[x+i][y+j]==".":
                d.append((x+i)*w+(y+j))
                seen[x+i][y+j]=1
    if seen[dh][dw]==1:
        break
    if not d:
        ans+=1
        for z in res:
            x,y=z
            for i in range(3):
                for j in range(3):
                    if 0<=x+i<h and 0<=y+j<w and seen[x+i][y+j]==0 and s[x+i][y+j]==".":
                        z=(x+i)*w+(y+j)
                        d.append(z)
                        seen[x+i][y+j]=1
                    if 0<=x-i<h and 0<=y-j<w and seen[x-i][y-j]==0 and s[x-i][y-j]==".":
                        z=(x-i)*w+(y-j)
                        d.append(z)
                        seen[x-i][y-j]=1
                    if 0<=x+i<h and 0<=y-j<w and seen[x+i][y-j]==0 and s[x+i][y-j]==".":
                        z=(x+i)*w+(y-j)
                        d.append(z)
                        seen[x+i][y-j]=1
                    if 0<=x-i<h and 0<=y+j<w and seen[x-i][y+j]==0 and s[x-i][y+j]==".":
                        z=(x-i)*w+(y+j)
                        d.append(z)
                        seen[x-i][y+j]=1
        res=[]
    if not d:
        print(-1)
        exit()
print(ans)