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

Solution (Python):
from collections import deque

H, W = 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)]
maze = [[-1]*W for _ in range(H)]

def walk(h, w, warp_n):
    ans = []
    if maze[h][w] != -1:
        return []
    else:
        maze[h][w] = warp_n
        ans += [(h, w)]
        
    return ans

queue = deque([(Ch, Cw, 0)])
while queue:
    h, w, warp_n = queue.popleft()
    if maze[h][w] != -1:
        continue
    maze[h][w] = warp_n
    
    for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if h+dh < 0 or w+dw < 0 or h+dh >= H or w+dw >= W:
                continue
            if S[h+dh][w+dw] == '
                continue
            queue.appendleft((h+dh, w+dw, warp_n))
    
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if h+dh < 0 or w+dw < 0 or h+dh >= H or w+dw >= W:
                continue
            if S[h+dh][w+dw] == '
                continue
            if dh == 0 and dw == 0:
                continue
            queue.append((h+dh, w+dw, warp_n+1))

print(maze[Dh][Dw])

Solution (Python):
from collections import deque
def main():
    h,w=map(int,input().split())
    sx,sy=map(int,input().split())
    sx-=1
    sy-=1
    gx,gy=map(int,input().split())
    gx-=1
    gy-=1
    g=[tuple(input()) for _ in range(h)]
    v=[[0 for j in range(w)] for i in range(h)]
    q=deque([[sx,sy]])
    v[sx][sy]=1
    ans=0
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    while True:
        l=[]
        while q:
            x,y=q.popleft()
            l.append([x,y])
            if x==gx and y==gy:
                print(ans)
                exit()
            for a,b in k:
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                    q.append([nx,ny])
                    v[nx][ny]=1
        if len(l)==0:
            break
        for x,y in l:              
            for a in range(-2,3):
                for b in range(-2,3):
                    if a*b==0 and abs(a+b)<=1:
                        continue
                    nx=x+a
                    ny=y+b
                    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                        q.append([nx,ny])
                        v[nx][ny]=1
        ans+=1 
    print(-1)
if __name__=='__main__':
    main()

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


from collections import deque
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
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Solution (Python):
import sys
def input(): return sys.stdin.readline()


from collections import deque
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
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Solution (Python):

import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) 

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if (fro_h, fro_w)==(DH,DW):
        print d[(fro_h, fro_w)]
        quit()
    if d[(fro_h, fro_w)]<kyori: continue
    
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

print -1

Solution (Python):




from collections import deque
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
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()


from collections import deque
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
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Solution (Python):

import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) 

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Solution (Python):

import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) 

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    if (fro_h, fro_w)==(DH,DW):
        print d[(fro_h, fro_w)]
        quit()
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

print -1

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

h, w = map(int, input().split())
ch, cw = map(int, input().split())
gh, gw = map(int, input().split())

s = []
for i in range(h):
   s.append(input().rstrip('\n'))

INF = 10 ** 10
d = [INF] * (h*w)

stack = deque([(ch-1, cw-1, 0)])

nex = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) in [(-1,0),(1,0),(0,-1),(0,1),(0,0)]:
            continue
        else:
            nex.append((i,j))

while stack:
    curh, curw, cnt = stack.popleft()
    if d[curh * w + curw] <= cnt:
        continue
    else:
        d[curh * w + curw] = cnt
    for dh, dw in ((-1,0), (1,0), (0,1), (0,-1)):
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and d[nh * w + nw] > cnt:
            stack.appendleft((nh, nw, cnt))
    for dh, dw in nex:
        nh = curh + dh
        nw = curw + dw
        if nh >= 0 and nh < h and nw >= 0 and nw < w and s[nh][nw] == '.' and  d[nh * w + nw] > cnt:
            stack.append((nh, nw, cnt+1))



gh -= 1
gw -= 1

if d[gh*w + gw] == INF:
    print(-1)
else:
    print(d[gh*w + gw])

Solution (Python):
from _collections import deque
h,w=map(int,input().split())
c_h,c_w=map(int,input().split())
d_h,d_w=map(int,input().split())
M=[input() for i in range(h)]
V=[[10**9]*w for i in range(h)]

q=deque([[0,c_h-1,c_w-1]])

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

    if V[x][y]!=10**9:
        continue
    V[x][y]=warp

    if x==d_h-1 and y==d_w-1:
        break

    for px in range(-2,3):
        for py in range(-2,3):
            if 0<=x+px<h and 0<=y+py<w:
                if px == 0 and py == 0:
                    continue
                if M[x + px][y + py] == '
                    continue
                if abs(px)+abs(py)<=1:
                    q.appendleft([warp,x+px,y+py])
                else:
                    q.append([warp+1,x+px,y+py])


if V[d_h-1][d_w-1]==10**9:
    print(-1)
else:
    print(V[d_h-1][d_w-1])

Solution (Python):
import sys
from io import StringIO
import unittest
import os
from collections import deque


sys.setrecursionlimit(999999999)





class youk_maze:
    __maze = []
    __wall_str = ""
    __road_str = ""
    __road_s = []  
    __wall_s = []  
    __arrived_s = []  
    __not_arrived_val = -1  

    def __init__(self, maze: [], can_move_out: bool = False, wall_str: str = "
        """
        コンストラクタ
        :maze 迷路の情報を保持する2次元配列
        :can_move_out 迷路の外側に出れるか(True:出れる、False:出れない)
        """

        if len(maze) == 0:
            raise ValueError("迷路の情報が設定されていない = len()が0")

        
        
        
        self.__wall_str = wall_str
        self.__road_str = road_str

        
        
        
        
        
        frame = road_str if can_move_out else wall_str
        
        self.__maze = [[frame] + [frame for _ in range(len(list(maze[0])))] + [frame]]
        
        for line in maze:
            self.__maze.append([frame] + line + [frame])
        
        self.__maze.append([frame] + [frame for _ in range(len(maze[0]))] + [frame])

        
        
        
        self.__road_s = []
        self.__wall_s = []
        for i in range(len(self.__maze)):
            for j in range(len(self.__maze[0])):
                
                if self.__maze[i][j] == self.__wall_str:
                    self.__wall_s.append([i, j])
                elif self.__maze[i][j] == self.__road_str:
                    self.__road_s.append([i, j])

        
        
        
        self.reset_arrived()

    def get_road_list(self):
        """
        座標の一覧を取得(道)
        """
        return self.__road_s

    def get_wall_list(self):
        """
        座標の一覧を取得(壁)
        """
        return self.__wall_s

    def get_maze(self):
        """
        迷路情報を返す
        """
        return self.__maze

    def get_arrived_val(self, cell: []):
        return self.__arrived_s[cell[0]][cell[1]]

    def is_arrived(self, cell: []) -> bool:
        """
        指定された座標が到達済みかを返す。(-1：未到達)
        """
        if self.__arrived_s[cell[0]][cell[1]] == self.__not_arrived_val:
            return False
        else:
            return True

    def can_moved(self, cell: [], do_arrive_check: bool = True) -> bool:
        """
        指定された経路に移動できるかを返す。(True:移動可能、False:移動不可)
        """
        
        if not 0 <= cell[0] < len(self.__maze) or not 0 <= cell[1] < len(self.__maze[0]):
            return False

        
        if self.__maze[cell[0]][cell[1]] == self.__wall_str:
            return False

        if not do_arrive_check:
            return True

        
        if self.__arrived_s[cell[0]][cell[1]] != self.__not_arrived_val:
            return False

        return True

    def set_arrived_val(self, cell: [], val):
        """
        指定された経路に到達情報を設定する。
        """
        self.__arrived_s[cell[0]][cell[1]] = val

    def reset_arrived(self):
        """
        経路の到達情報を初期化する。(おそらく、コンストラクタ以外で使うことは無い・・)
        """
        self.__arrived_s = [[self.__not_arrived_val for i in range(len(self.__maze[0]))] for j in
                            range(len(self.__maze))]

    def get1dpoint(self, cell) -> int:
        """
        座標情報を1次元に変換したものを返す。対象を1次元で管理する処理との連携に使用する。(例：UnionFind)
        """
        
        return cell[0] * len(self.__maze[0]) + cell[1]

    def getcellcount(self) -> int:
        """
        座標数を返す(囲み枠を考慮した座標数を返す)
        """
        
        return len(self.__maze) * len(self.__maze[0])

    def debugmazemap(self, custom_list: [] = []) -> str:
        """
        ※デバック用変数※
        迷路の情報と到達リストをテキスト形式で返す(タブ区切り)
        custom_list:
         任意の一次元配列。渡した場合、座標ごとに情報を紐づけしたものを返す。
         ※到達リスト以外のリストを作って何かを管理している場合、渡すと良い。
        """
        ans = ""
        
        for i in range(len(self.__maze)):
            ans += "\t".join(self.__maze[i]) + "\n"

        ans += "\n"
        
        for i in range(len(self.__maze)):
            ans += "\t".join(map(str, self.__arrived_s[i])) + "\n"
        return ans

        
        if len(custom_list) == 0:
            return

        
        ans += "\n"
        for i in range(len(self.__maze)):
            line = ""
            for j in range(len(self.__maze[0])):
                point = self.get1dpoint([i, j])
                line += str(custom_list[point]) + "\t"
            ans += line + "\n"
        return ans



def resolve(test_def_name=""):
    h, w = map(int, input().split())

    start = list(map(int, input().split()))
    gorl = list(map(int, input().split()))

    maze = youk_maze([list(input()) for i in range(h)])

    
    start_list = maze.get_road_list()
    que = deque()
    que.extend(start_list)

    
    
    group_num = 0
    while len(que) is not 0:
        now = que.popleft()

        
        if not maze.is_arrived(now):
            group_num += 1
            maze.set_arrived_val(now, group_num)

        
        for move_h, move_w in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
            target = [now[0] + move_h, now[1] + move_w]
            if not maze.can_moved(target):
                continue

            
            maze.set_arrived_val(target, group_num)
            
            que.appendleft(target)

    move_target_list = [set() for a in range(group_num + 1)]
    
    que.extend(start_list)
    while len(que) is not 0:
        now = que.popleft()

        
        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), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]:
            
            target = [now[0] + i, now[1] + j]
            if not maze.can_moved(target, do_arrive_check=False):
                continue

            
            if maze.get_arrived_val(now) != maze.get_arrived_val(target):
                move_target_list[maze.get_arrived_val(now)].add(maze.get_arrived_val(target))

    
    start_erea = maze.get_arrived_val(start)

    
    area_list = [-1 for a in range(group_num + 1)]
    area_list[start_erea] = 0

    que.appendleft(start_erea)
    while len(que) is not 0:
        now = que.popleft()

        
        for move_target in move_target_list[now]:

            
            if not area_list[move_target] == -1:
                continue

            
            que.append(move_target)

            
            area_list[move_target] = area_list[now] + 1

    gorl_area = maze.get_arrived_val(gorl)
    print(area_list[gorl_area])

    


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 1
4 4
..
..
.
.
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4 4
1 4
4 1
.


.
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """4 5
1 2
2 5




        output = """2"""
        self.assertIO(test_input, output)

    
    def test_original(self):
        test_input = """4 4
2 2
3 3
....
..
.
...."""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_origina2(self):
        test_input = """4 4
2 2
3 3
....
..
.
...."""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_origina3(self):
        test_input = """4 4
2 2
3 3
....
..

...."""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina4(self):
        test_input = """4 4
1 1
3 3
.
..

...."""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina5(self):
        test_input = """4 4
1 1
4 4
.


...."""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina6(self):
        test_input = """4 4
1 1
4 4
.


...."""
        output = """2"""
        self.assertIO(test_input, output)

    
    def test_origina7(self):
        test_input = """1 4
1 1
1 4
...."""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_origina8(self):
        test_input = """1 4
1 1
1 4
.
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina9(self):
        test_input = """1 4
1 4
1 1
..
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina10(self):
        test_input = """4 1
4 1
1 1
.
.

.
"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_origina11(self):
        test_input = """4 1
1 1
4 1
.
.

.
"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original12(self):
        test_input = """6 6
1 1
6 6
......
......
......
......
......
......"""
        output = """0"""
        self.assertIO(test_input, output)

    
    def test_original13(self):
        test_input = """6 6
1 1
6 6
......

......
......
......
......"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original14(self):
        test_input = """6 6
1 1
6 6
......


......
......
......"""
        output = """-1"""
        self.assertIO(test_input, output)

    
    def test_original15(self):
        test_input = """6 6
1 1
6 6
......

.
.

......"""
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original16(self):
        test_input = """6 6
1 1
6 1
......

.
.

....
        output = """2"""
        self.assertIO(test_input, output)

    
    def test_original17(self):
        test_input = """6 6
3 3
6 1
......

.
.

....
        output = """1"""
        self.assertIO(test_input, output)

    
    def test_original17(self):
        test_input = """6 6
1 1
4 4
.
.
.
.
.
.
        output = """1"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial,sqrt
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7

    h,w=MI()
    sx,sy=MI()
    gx,gy=MI()
    sy-=1
    sx-=1
    gy-=1
    gx-=1
    mp=[[0]*h for i in range(w)]
    Q=deque([[sy,sx]])
    for i in range(h):
        s=SI()
        for j in range(w):
            if s[j]=="
                mp[j][i]=1
    
    turn=[[inf]*h for i in range(w)]
    turn[sy][sx]=0
    
    step=[[-1,0],[1,0],[0,1],[0,-1]]
    
    while Q:
        y,x=Q.popleft()
        z=turn[y][x]
        if y==gy and x==gx:
            print(turn[y][x])
            sys.exit()
        for j,i in step:
            if not (0<=y+j<w and 0<=x+i<h):
                continue
            elif mp[y+j][x+i]==1:
                continue
            else:
                if z<turn[y+j][x+i]:
                    turn[y+j][x+i]=z
                    Q.appendleft([y+j,x+i])
        
        for i in range(-2,3):
            for j in range(-2,3):
                if not (0<=y+j<w and 0<=x+i<h):
                    continue
                elif mp[y+j][x+i]==1:
                    continue
                else:
                    if z+1<turn[y+j][x+i]:
                        turn[y+j][x+i]=z+1
                        Q.append([y+j,x+i])
        
    
    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())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

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

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    cy,cx = LI()
    gy,gx = LI()
    s = [input() for _ in range(h)]
    cy -= 1
    cx -= 1
    gy -= 1
    gx -= 1
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    bfs = [[float("inf")]*w for i in range(h)]
    bfs[cy][cx] = 0
    q = deque([(cy,cx)])
    while q:
        y,x = q.popleft()
        b = bfs[y][x]
        if (y,x) == (gy,gx):
            print(b)
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "
                bfs[ny][nx] = b
                q.appendleft((ny,nx))
        nb = b+1
        for dy in range(-2,3):
            for dx in range(-2,3):
                ny,nx = y+dy,x+dx
                if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "
                    bfs[ny][nx] = nb
                    q.append((ny,nx))
    print(-1)
    return


if __name__ == "__main__":
    solve()