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

    H, W = map(int, input().split())
    sy, sx = (int(x) - 1 for x in input().split())
    gy, gx = (int(x) - 1 for x in input().split())
    G = [input().rstrip() for _ in range(H)]

    dq = deque()
    dq.append((sy, sx, 0))

    INF = H * W + 10

    ctr = [[INF] * W for _ in range(H)]
    ctr[sy][sx] = 0

    while dq:
        y, x, cnt = dq.popleft()
        if cnt > ctr[y][x]:
            continue

        if y > 0 and G[y - 1][x] == '.' and ctr[y - 1][x] > cnt:
            dq.appendleft((y - 1, x, cnt))
            ctr[y - 1][x] = cnt
            if y - 1 == gy and x == gx:
                print(cnt)
                return

        if x > 0 and G[y][x - 1] == '.' and ctr[y][x - 1] > cnt:
            dq.appendleft((y, x - 1, cnt))
            ctr[y][x - 1] = cnt
            if y == gy and x - 1 == gx:
                print(cnt)
                return

        if y < H - 1 and G[y + 1][x] == '.' and ctr[y + 1][x] > cnt:
            dq.appendleft((y + 1, x, cnt))
            ctr[y + 1][x] = cnt
            if y + 1 == gy and x == gx:
                print(cnt)
                return

        if x < W - 1 and G[y][x + 1] == '.' and ctr[y][x + 1] > cnt:
            dq.appendleft((y, x + 1, cnt))
            ctr[y][x + 1] = cnt
            if y == gy and x + 1 == gx:
                print(cnt)
                return

        ncnt = cnt + 1
        for dr in range(-2, 3):
            ny = y + dr
            if ny < 0 or ny >= H:
                continue
            for dc in range(-2, 3):
                nx = x + dc
                if nx < 0 or nx >= W:
                    continue
                if G[ny][nx] == '.' and ctr[ny][nx] > ncnt:
                    dq.append((ny, nx, ncnt))
                    ctr[ny][nx] = ncnt

        if ctr[gy][gx] <= cnt:
            print(cnt)
            return

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
import copy
import sys
sys.setrecursionlimit(10**7)

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

meiro = [ ['
meiro += [ ['
meiro += [['
meiro += [ ['
meiro += [ ['

moved = [[-1, 0], [1, 0], [0, 1], [0, -1]]

def label(row, column):
    meiro[row][column] = num
    for i,j in moved:
        if meiro[row+i][column+j] == '.':
            check.append([row+i, column+j])
            label(row+i, column+j)

row = ch + 1
column = cw + 1

num = 0
check = [[row, column]]
label(row, column)

while True:
    num += 1
    check_copy = copy.deepcopy(check)
    check = []
    for i,j in check_copy:
        for s in range(-2, 3):
            for t in range(-2, 3):
                if meiro[i+s][j+t] == '.':
                    check.append([i+s, j+t])
                    label (i+s,j+t)

    if len(check) == 0:
        break

if meiro[dh+1][dw+1] == '.':
    print(-1)
else:
    print(meiro[dh+1][dw+1])

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]

class TwoDimGrid:
    
    def __init__(self, h, w, wall="
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        self.init_cost()

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self, start, goal):
        grid = self.grid
        cy, cx = start
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        warp = []
        for i in range(-2, 3):
            for j in range(-2, 3):
                if (i, j) not in move and (i != 0 or j != 0):
                    warp.append((i, j))
        
        d = deque()
        wd = deque()
        self.set(start[1], start[0], 0)
        d.append((0, cx, cy))
        while (d or wd):
            
            if d:
                cc, cx, cy = d.popleft()
            else:
                cc, cx, cy = wd.popleft()
            
            if self.get(cx, cy) < cc:
                continue
            for dx, dy in move:

                nx, ny = dx + cx, dy + cy
                if self.getgrid(nx, ny) == "
                    continue
                if self.get(nx, ny) > cc:
                    self.set(nx, ny, cc)
                    d.append((cc, nx, ny))

            for dx, dy in warp:
                nx, ny = dx + cx, dy + cy
                if nx < 0 or nx > self.w + 1 or ny < 0 or ny > self.h + 1:
                    continue
                if self.getgrid(nx, ny) == "
                    continue
                if self.get(nx, ny) > cc + 1:
                    self.set(nx, ny, cc + 1)
                    wd.append((cc + 1, nx, ny))
        
        
        
        ans = self.get(goal[1], goal[0])
        if ans == INF:
            print(-1)
            return
        else:
            print(ans)
            return





def solve():
    h, w = getList()
    start = getList()
    goal = getList()
    G = TwoDimGrid(h, w)
    G.search(start, goal)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import sys
from collections import deque
h, w = (int(x) for x in input().split())
ch, cw = (int(x) for x in input().split())
dh, dw = (int(x) for x in input().split())
ch-=1
cw-=1
dh-=1
dw-=1
directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
directions_warp = [[-2, -2], [-2, -1], [-2, 0], [-2, 1], [-2, 2], [-1, -2], [-1, 2], [0, -2], [0, 2], [1, -2], [1, 2], [2, -2], [2, -1], [2, 0], [2, 1], [2, 2], [-1, -1], [1, 1], [-1, 1], [1, -1]]
s = []
for i in range(h):
    sh = input()
    s.append(sh)
gone = [[-1]*w for i in range(h)]
que = deque([[ch, cw]])
gone[ch][cw]=0
boo = True
count = 0
while boo ==True:
    now = []
    while que:
        nh, nw = que.pop()
        now.append((nh, nw))
        for gh, gw in directions:
            if nh+gh<0 or nh+gh>=h or nw+gw<0 or nw+gw>=w:
                pass
            elif gone[nh+gh][nw+gw]==0:
                pass
            else:
                if s[nh+gh][nw+gw]=="
                    pass
                else:
                    now.append((nh+gh, nw+gw))
                    gone[nh+gh][nw+gw]=0
                    que.appendleft([nh+gh, nw+gw])
    if gone[dh][dw]==0:
        print(count)
        break
    boo2 = False
    for nh, nw in now:
        for gh, gw in directions_warp:
            if nh+gh<0 or nh+gh>=h or nw+gw<0 or nw+gw>=w:
                pass
            else:
                if s[nh+gh][nw+gw]=="
                    pass
                elif gone[nh+gh][nw+gw]==0:
                    pass
                else:
                    boo2 = True
                    gone[nh+gh][nw+gw]=0
                    que.appendleft([nh+gh, nw+gw])
    if boo2 == False:
        print(-1)
        break
    count+=1

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R,C = NMI()
    sy, sx = NMI()
    gy, gx = NMI()
    board = [list(input()) for _ in range(R)]

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

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

    
    INF = 10**7
    distance = [[INF for _ in range(C)] for _ in range(R)]

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

    
    distance[sy][sx] = 0
    
    
    tx = [-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]
    ty = [-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]
    
    
    teleque = deque([])
    

    while len(que) != 0 or len(teleque) != 0:
        

        
        while len(que) != 0:

            
            pop = que.popleft()
            if pop[0]==gy and pop[1]==gx:
                print(distance[gy][gx])
                sys.exit()

            
            for i in range(len(dx)):
                
                ny = pop[0]+dy[i]
                nx = pop[1]+dx[i]


                
                if 0<= ny < R and 0 <= nx < C and distance[ny][nx] == INF:

                    if board[ny][nx]!='
                        
                        que.appendleft((ny,nx))
                        distance[ny][nx] = distance[pop[0]][pop[1]]


                    else:
                        teleque.append((pop[0],pop[1]))
                        

        while len(teleque) != 0:
            telepop = teleque.popleft()
            if telepop[0]==gy and telepop[1]==gx:
                print(distance[gy][gx]+1)
                sys.exit()


                
            for j in range(len(tx)):
                teley = telepop[0]+ty[j]
                telex = telepop[1]+tx[j]
                
                
                if 0<= teley < R and 0 <= telex < C and distance[teley][telex] == INF:
                    if board[teley][telex]!='
                        que.append((teley,telex))
                        distance[teley][telex] = distance[pop[0]][pop[1]]+1 

    print(-1)


if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

H,W=map(int,input().split())
Sx,Sy=map(int,input().split())
Gx,Gy=map(int,input().split())
Sx-=1
Sy-=1
Gx-=1
Gy-=1
tmp=False
check=deque()

M=[[0 if j=='.' else 1 for j in input()]for i in range(H)]



ans=0
check.append([Sx,Sy])
while True:
    hit=set()
    while check:
        x,y = check.pop()
        
        if x==Gx and y==Gy:
            tmp=True
            break
        M[x][y]=2
        
        for dx,dy in [ [x+1,y],[x-1,y],[x,y-1],[x,y+1] ]:
            if not(0<=dx and dx<H and 0<=dy and dy<W):
                continue
            if M[dx][dy]==1:
                hit.add((x,y))
            if M[dx][dy]==0:
                check.append([dx,dy])
    if tmp:
        print(ans)
        break
    if len(hit)==0:
        print(-1)
        break
    for e in hit:
        x,y=e
        for i in range(-2,3):
            for j in range(-2,3):
                if 0<=x+i and x+i<H and 0<=y+j and y+j<W and M[x+i][y+j]==0:
                    check.append([x+i,y+j])
    if len(check)==0:
        print(-1)
        break

    ans+=1

Solution (Python):
from __future__ import  print_function
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    num = 0
    visited = set()
    stack = []
    for i in range(h):
        for j in range(w):
            if (not s[i][j] == "
                visited.add(i*h + j)
                who[i][j] = num
                stack.append((i,j))
                while stack:
                    cur = stack.pop()
                    who[cur[0]][cur[1]] = num
                    for nb in getnb(cur[0], cur[1]):
                        ii = nb[0]
                        jj = nb[1]
                        if (not s[ii][jj] == "
                            stack.append(nb)
                            visited.add(ii*h + jj)
                num += 1
    
    
    
    edges = [set() for _ in range(num)]
    for i in range(h):
        for j in range(w):
            cg = who[i][j]
            if not cg == -1:
                for a in range(0, 3):
                    for b in range(-2, 3):
                        if 0 <= i+a < h and 0<= j+b < w:
                            ng = who[i+a][j+b]
                            if ng not in (-1, cg) and (ng not in edges[cg]):
                                edges[cg].add(ng)
                                edges[ng].add(cg)
    
    start = who[ch-1][cw-1]
    goal = who[dh-1][dw-1]
    count = 0
    stack = [start]
    visited = set()
    while stack:
        new_stack = []
        for el in stack:
            if not el in visited:
                visited.add(el)
                if el == goal:
                    print(count)
                    exit()
                new_stack.extend(list(edges[el]))
        stack = new_stack
        count += 1
    print(-1)
    exit()

    return


def getnb(i, j):
    nb = []
    if i > 0:
        nb.append((i-1, j))
    if i < h-1:
        nb.append((i+1, j))
    if j > 0:
        nb.append((i, j -1))
    if j < w-1:
        nb.append((i, j +1))
    return nb








h, w = RA()
ch, cw = RA()
dh, dw = RA()
s = [list(raw_input()) for _ in range(h)]
who = [[-1 for _ in range(w)] for _ in range(h)]
solve()

Solution (Python):

import collections as cl
import sys
MAX_INT = -100


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


def LI():
    return list(map(int, sys.stdin.readline().split()))


class Maze():
    def __init__(self, maze, start, goal, h, w):
        self.maze = maze
        self.h = h
        self.w = w
        self.start = start
        self.goal = goal

    def clastering(self):
        group = 0
        for i in range(self.h):
            for j in range(self.w):
                if self.maze[i][j] != -1:
                    continue
                self.fill([i, j], group)
                group += 1
        self.num_group = group

    def fill(self, point, group):
        self.maze[point[0]][point[1]] = group
        deque = cl.deque([point])
        ways = [[-1, 0], [0, -1], [0, 1], [1, 0]]

        while len(deque) > 0:
            cur = deque.popleft()

            for way in ways:
                next_i = cur[0] + way[0]
                next_j = cur[1] + way[1]
                if self.isReachable(next_i, next_j) and self.maze[next_i][next_j] != group:
                    self.maze[next_i][next_j] = group
                    deque.append([next_i, next_j])

    def isReachable(self, i, j):
        return 0 <= i < self.h and 0 <= j < self.w and self.maze[i][j] != MAX_INT

    def solve(self):
        self.clastering()

        connected = [[]for i in range(self.num_group)]

        for i in range(self.h):
            for j in range(self.w):
                if not self.isReachable(i, j):
                    continue

                for i_plus in [-2, -1, 0, 1, 2]:
                    for j_plus in [-2, -1, 0, 1, 2]:
                        next_i = i + i_plus
                        next_j = j + j_plus
                        if self.isReachable(next_i, next_j):
                            next_group = self.maze[next_i][next_j]
                            cur_group = self.maze[i][j]
                            if next_group != cur_group:
                                connected[cur_group
                                          ].append(next_group)

        for g in range(len(connected)):
            connected[g] = list(set(connected[g]))

        start_group = self.maze[self.start[0] - 1][self.start[1]-1]
        goal_group = self.maze[self.goal[0]-1][self.goal[1] - 1]

        if start_group == goal_group:
            print(0)
            return

        if len(connected[start_group]) == 0 or len(connected[goal_group]) == 0:
            print(-1)
            return

        costs = [10**19] * len(connected)

        costs[start_group] = 0
        deque = cl.deque([connected[start_group]])
        cost = 1
        while len(deque) > 0:
            cur = deque.popleft()
            if len(cur) == 0:
                break
            next_g = []
            for group in cur:
                if costs[group] > cost:
                    costs[group] = cost
                    next_g.extend(connected[group])

            cost += 1
            deque.append(next_g)

        print(costs[goal_group])


def main():
    h, w = MI()
    start = LI()
    goal = LI()
    maze = [[MAX_INT for i in range(w)] for j in range(h)]

    for i in range(h):
        row = input()
        for j in range(len(row)):
            if row[j] == "
                continue
            maze[i][j] = -1

    solver = Maze(maze, start, goal, h, w)
    solver.solve()


main()

Solution (Python):
h,w = map(int,input().split())
c_h,c_w = map(int,input().split())
d_h,d_w = map(int,input().split())
s_list = [[c for c in input()] for _ in range(h)]

move_pattern = [[-1,0],[1,0],[0,-1],[0,1]]
around_area = [[i-2,j-2] for i in range(5) for j in range(5)]
kakutei_set = set([(c_h-1,c_w-1)])
temp_dic = {}
temp_dic[0] = set([(c_h-1,c_w-1)])
temp_num = 0
while True:
    cur_list = list(temp_dic[temp_num])
    for i,j in cur_list:
        for x,y in move_pattern:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                cur_list.append((i+y,j+x))
                temp_dic[temp_num].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_dic[temp_num+1] = set()
    for i,j in temp_dic[temp_num]:
        for x,y in around_area:
            if i+y<0 or i+y>=h or j+x<0 or j+x>=w:
                continue
            elif s_list[i+y][j+x]=="
                continue
            elif (i+y,j+x) in kakutei_set:
                continue
            else:
                temp_dic[temp_num+1].add((i+y,j+x))
                kakutei_set.add((i+y,j+x))
    temp_num += 1
    if len(temp_dic[temp_num])==0:
        break
if (d_h-1,d_w-1) not in kakutei_set:
    print(-1)
else:
    for key,value in temp_dic.items():
        if (d_h-1,d_w-1) in value:
            print(key)

Solution (Python):
import sys
import heapq as hq
import functools, collections
import math, random
from collections import Counter, defaultdict
import threading










from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc


def dijkstra(G, s):
    n = len(G)
    visited = [False]*n
    weights = [math.inf]*n
    path = [None]*n
    queue = []
    weights[s] = 0
    hq.heappush(queue, (0, s))
    while len(queue) > 0:
        g, u = hq.heappop(queue)
        visited[u] = True
        for v, w in G[u]:
            if not visited[v]:
                f = g + w
                if f < weights[v]:
                    weights[v] = f
                    path[v] = u
                    hq.heappush(queue, (f, v))
    return path, weights


def solve(grid, sx, sy, ex, ey):  
    console("----- solving ------")

    grid = [[0 if cell == "
    grid = [[0] * len(grid[0])]*2 + grid + [[0] * len(grid[0])]*2
    grid = [[0,0] + row + [0,0] for row in grid]
    sx, sy, ex, ey = sx+1, sy+1, ex+1, ey+1

    labels = [[False for _ in row] for row in grid]
    diffs = [(-1,0), (1,0), (0,-1), (0,1)]

    
    def dfs(var):
        x,y,cur_label = var
        for dx,dy in diffs:
            xx, yy = x+dx, y+dy
            if labels[xx][yy]:
                continue
            if grid[xx][yy] == 0:
                continue
            labels[xx][yy] = cur_label
            var2 = xx,yy,cur_label
            dfs(var2)

    cur_label = 0
    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if labels[i][j]:
                continue
            if grid[i][j] == 0:
                continue
            cur_label += 1
            labels[i][j] = cur_label
            var = i,j,cur_label
            dfs(var)
            
    console("label")
    console(labels)


    start = labels[sx][sy]
    end = labels[ex][ey]
    console("start and end", start, end)

    connections = defaultdict(set)

    for i,row in enumerate(grid):
        for j,cell in enumerate(row):
            if cell == 0:
                continue
            for dx in [-2,-1,0,1,2]:
                for dy in [-2,-1,0,1,2]:
                    if labels[i][j] != False and labels[i+dx][j+dy] != False:
                        if labels[i][j] != labels[i+dx][j+dy]:
                            connections[labels[i][j]].add(labels[i+dx][j+dy])
                            connections[labels[i+dx][j+dy]].add(labels[i][j])

    console("connections", connections)

    G = [[] for _ in range(cur_label+1)]

    for k,lst in connections.items():
        G[k].extend([(x,1) for x in lst])

    console("G", G)

    _, result = dijkstra(G, start)
    
    console("result", result)

    if result[end] > 10**6:
        return -1
    return result[end]



def console(*args):  
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return




def main():
    
    

    
    
    
    
    

    
    nrows, w = list(map(int,input().split()))
    sx, sy = list(map(int,input().split()))
    ex, ey = list(map(int,input().split()))

    
    
    
    grid = []
    for _ in range(nrows):
        grid.append(list(input()))

    res = solve(grid, sx, sy, ex, ey)  
    
    
    

    
    print(res)

main()

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False


BLOCK = '
ROAD = '.'

warps = []

for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) not in [(-1, 0), (0, 1), (1, 0), (0, -1), (0, 0)]:
            warps.append((i, j))

def bfs(graph, initial, goal, H, W):
    options = [(-1, 0), (0, 1), (1, 0), (0, -1)]
    q = deque([(initial, 0)])
    visited = [[False for i in range(W)] for i in range(H)]
    dist = [[-1 for i in range(W)] for i in range(H)]
    visited[initial[0]][initial[1]] = True
    block_li = set([])

    while len(q) != 0:
        p, cnt = q.popleft()

        for d in options:
            i = p[0] + d[0]
            j = p[1] + d[1]

            if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j]:
                if graph[i][j] != BLOCK:
                    visited[i][j] = True
                    q.append(((i, j), cnt))

                    if goal[0] == i and goal[1] == j:
                        return cnt
                else:
                    block_li.add((p[0], p[1]))

        if len(q) == 0 and len(block_li) != 0:
            
            for bp in block_li:
                for d in warps:
                    i = bp[0] + d[0]
                    j = bp[1] + d[1]

                    if i >= 0 and i < H and j >= 0 and j < W and not visited[i][j] and graph[i][j] != BLOCK:
                        tmp = cnt + 1
                        visited[i][j] = True
                        q.append(((i, j), tmp))

                        if goal[0] == i and goal[1] == j:
                            return tmp
            block_li = set()
    return -1


def main():
    H, W = MI()
    CH, CW = MI()
    DH, DW = MI()
    graph = [None] * H
    CH -= 1
    CW -= 1
    DH -= 1
    DW -= 1

    for i in range(H):
        graph[i] = list(S())

        for j in range(W):
            if graph[i][j] == 'S':
                pass

    ret = bfs(graph, (CH, CW), (DH, DW), H, W)
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
H, W = list(map(int, input().split()))
Ch, Cw = list(map(int, input().split()))
Dh, Dw = list(map(int, input().split()))
S = [[o for o in input()] for i in range(H) ]

def dfs(y, x, c):
    S[y][x] = c
    for dy, dx in [(-1,0), (1,0), (0,1), (0,-1)]:
            ny = y+dy
            nx = x+dx
            if nx>=0 and nx<W and ny>=0 and ny<H and S[ny][nx]=='.':
                dfs(ny, nx, c)

c = 0
for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            dfs(i, j, c)
            c+=1

arr = {i:[] for i in range(c)}

for i in range(H):
    for j in range(W):
        cla = S[i][j]
        if cla!='
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx = j+dx
                    ny = i+dy
                    if nx>=0 and nx<W and ny>=0 and ny<H and S[ny][nx]!='
                        if S[ny][nx]!=cla and S[ny][nx] not in arr[cla]:
                            arr[cla].append(S[ny][nx])

current = S[Ch-1][Cw-1]
goal = S[Dh-1][Dw-1]
dis = {current:0}
queue = [current]
cnt = 1
while queue:
    now = queue.pop(0)
    if arr[now]!=[]:
        for one in arr[now]:
            if one not in dis:
                dis[one] = dis[now]+1
                queue.append(one)

if goal in dis:
    print(dis[goal])
else:
    print(-1)

Solution (Python):
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
raw = []
seen = []
for _ in range(h):
  tmp = input()
  raw.append(tmp)
  t = []
  for j in range(w):
    if tmp[j] == '.':
      t.append(0)
    else:
      t.append(1)
  seen.append(t)

now = [s]
ans = 0
def check(ii,jj):
  if 0 <= ii < h and 0 <= jj < w:
    if seen[ii][jj] == 0:
      seen[ii][jj] = 1
      now.append([ii,jj])
while now:
  for x in now:
    a,b = x
    check(a-1,b)
    check(a+1,b)
    check(a,b-1)
    check(a,b+1)
  if seen[g[0]][g[1]] == 1:
    print(ans)
    break
  ans += 1
  last = now
  now = []
  for x in last:
    a,b = x
    for di in range(-2,3):
      for dj in range(-2,3):
        check(a+di,b+dj)
else:
  print(-1)