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):
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def RLI(n=8,a=1,b=10):return [random.randint(a,b)for i in range(n)]
def RI(a=1,b=10):return random.randint(a,b)
def Rtest(T):
    case,err=0,0
    for i in range(T):
        inp=INP()
        a1,ls=naive(*inp)
        a2=solve(*inp)
        if a1!=a2:
            print((a1,a2),inp)
            err+=1
        case+=1
    print('Tested',case,'case with',err,'errors')
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'
    
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase

read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

inf=1<<20
def dijkstra(edge,st):
    n=len(edge)
    d=[(0 if st==i else inf) for i in range(n)]
    q=[(0,st)]
    heapify(q)
    v=[False]*n
    while q:
        dist,cur=heappop(q)
        if v[cur]:
            continue
        v[cur]=True
        for dst,dist in edge[cur]:
            alt=d[cur]+dist
            if alt<d[dst]:
                d[dst]=alt
                heappush(q,(alt,dst))
    return d




class GridGraph:
    def __init__(self,h,w,search=None,replacement_of_found='.',mp_def={'
        self.h=h+2
        self.w=w+2
        self.n=self.h*self.w
        self.edge=[[]for i in range(self.n)]
        self.nb=[-1,1,-self.w,self.w]
        
        self.mp=[boundary]*self.w
        self.found={}
        for i in range(self.h-2):
            s=input()
            self.mp+=[boundary]
            for i in range(self.w-2):
                char=s[i]
                if search and char in search:
                    self.found[char]=((i+1)*self.w+i+1)
                    mp_def[char]=mp_def[replacement_of_found]
                self.mp+=[mp_def[char]]
            self.mp+=[boundary]
        self.mp+=[boundary]*self.w
        self.h,self.w,self.mp,self.found
        return

    def create_edge(self,cost_func=lambda x,y:1):
        w=self.w
        nbw=[2,2*w+1,2*w+2,w+1,w+2,+2*w,2*w-1,2*w-2,w-1,w-2]
        for i in range(self.n):
            if self.mp[i]==1:
                continue
            for di in self.nb:
                nx=i+di
                if self.mp[nx]!=1:
                    
                    self.edge[i].append((nx,0))
            
            for di in nbw:
                nx=i+di
                if 0<=nx<self.n and self.mp[nx]!=1:
                    self.edge[i].append((nx,1))
                    self.edge[nx].append((i,1))
            
        return self.edge


    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v

    def __str__(self):
        for i in range(self.h):
            print(self.mp[i*self.w:(i+1)*self.w])
        return ''
 
    def show_map(self,length=2):
        for i in range(self.h):
            print(*[' '*(length-(len(str(j))))+str(j) for j in self.mp[i*self.w:(i+1)*self.w]])

    def show_node_num(self,length=2):
        for i in range(self.h):
            print(*[' '*(length-(len(str(j))))+str(j) for j in range(i*self.w,(i+1)*self.w)])

    def show_map_w_node_num(self,length=2):
        for i in range(self.h):
            print(*[[' '*(length-(len(str(j))))+str(j),self.mp[j]] for j in range(i*self.w,(i+1)*self.w)])
    
    def show_edge(self,length=2):
        for i in range(self.h):
            print(*[[' '*(length-(len(str(j))))+str(j),self.edge[j]] for j in range(i*self.w,(i+1)*self.w)])


    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

show_flg=False
show_flg=True

ans=0

h,w=LI()
sh,sw=LI()
gh,gw=LI()

gg=GridGraph(h,w)
gg.create_edge()
d=dijkstra(gg.edge,sh*gg.w+sw)
ans=d[gh*gg.w+gw]
if ans==inf:
    ans=-1
print(ans)

Solution (Python):
from collections import deque
 

H,W=map(int,input().split())
Ch,Cw=[int(x)-1 for x in input().split()]
Dh,Dw=[int(x)-1 for x in input().split()]
maze=[input() for i in range(H)]
 
dirs=[-2,-1,0,1,2] 

dist=[[float('inf')]*W for _ in range(H)] 
dist[Ch][Cw]=0
dq=deque()
dq.append((0,Ch,Cw)) 
ok=False

while dq:
    k,i,j=dq.popleft()
    if k>dist[i][j]:
        continue
    if i==Dh and j==Dw:
        ok=True
        break
    for di in dirs:
        for dj in dirs:
            if di==dj==0:
                continue
            ni,nj=i+di,j+dj 
            if not (0<=ni<H and 0<=nj<W):
                continue
            if maze[ni][nj]=='
                continue
            if abs(di)+abs(dj)==1: 
                append=dq.appendleft
                nk=k
            else: 
                append=dq.append
                nk=k+1
            if k>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            append((nk,ni,nj))      
if ok:
    ans=dist[Dh][Dw]
else:
    ans=-1
print(ans)

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

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

Q=deque()
Q.append((ch,cw,0))

dx=[1,0,-1,0]
dy=[0,1,0,-1]
ddx=[2,2,2,2,2,-2,-2,-2,-2,-2,1,1,1,1,-1,-1,-1,-1,0,0]
ddy=[-2,-1,0,1,2,-2,-1,0,1,2,2,1,-1,-2,2,1,-1,-2,2,-2]

dp=[[float('inf')]*w for i in range(h)]


while Q:
  p=Q.popleft()
  if p[0]==dh and p[1]==dw:
    print(p[2])
    exit()
  
  for i in range(4):
    nx=p[0]+dx[i]
    ny=p[1]+dy[i]

    if 0<=nx<h and 0<=ny<w and maze[nx][ny]=='.' and p[2]<dp[nx][ny]:
      Q.appendleft((nx,ny,p[2]))
      dp[nx][ny]=p[2]

  for j in range(20):
    nnx=p[0]+ddx[j]
    nny=p[1]+ddy[j]

    if 0<=nnx<h and 0<=nny<w and maze[nnx][nny]=='.' and p[2]+1<dp[nnx][nny]:
      Q.append((nnx,nny,p[2]+1))
      dp[nnx][nny]=p[2]+1


print(-1)

Solution (Python):
from collections import deque
from itertools import product


def main():
    h, w = map(int, input().split())
    c = tuple(map(lambda x: int(x)+1, input().split()))
    d = tuple(map(lambda x: int(x)+1, input().split()))
    s = ['

    move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
    move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

    cost = [[float('inf')] * (w+4) for _ in range(h+4)]
    cost[c[0]][c[1]] = 0
    yet = deque([(c[0], c[1], 0)])
    done = deque()

    while yet:
        y, x, m = yet.popleft()
        done.append((y, x, m))
        
        for dx, dy in move_a_area:
            hh, ww = y + dy, x + dx
            if s[hh][ww] == '
                continue
            cost[hh][ww] = m
            yet.append((hh, ww, m))
        
        if not yet:
            while done:
                y, x, m = done.popleft()
                for dx, dy in move_b_area:
                    hh, ww = y + dy, x + dx
                    if s[hh][ww] == '
                        continue
                    cost[hh][ww] = m + 1
                    yet.append((hh, ww, m + 1))

    print(v if (v := cost[d[0]][d[1]]) < float('inf') else -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 = [input() for i in range(h)]

walk = [(-1, 0), (0, 1), (1, 0), (0, -1)]
warp = [(y, x) for y in range(-2, 3) for x in range(-2, 3)]

q = deque()
q.append((ch, cw))

dist = [[10**7] * w for _ in range(h)]
dist[ch][cw] = 0

while q:
    y, x = q.popleft()
    if [y, x] == [dh, dw]:
        break

    for dy, dx in walk:
        if 0 <= y+dy < h and 0 <= x+dx < w:
            if S[y+dy][x+dx] == '.':
                if dist[y][x] < dist[y+dy][x+dx]:
                    dist[y + dy][x + dx] = dist[y][x]
                    q.appendleft((y+dy, x+dx))

    for dy, dx in warp:
        if 0 <= y+dy < h and 0 <= x+dx < w:
            if S[y+dy][x+dx] == '.':
                if dist[y][x]+1 < dist[y+dy][x+dx]:
                    dist[y + dy][x + dx] = dist[y][x]+1
                    q.append((y+dy, x+dx))

print(dist[dh][dw] if dist[dh][dw] != 10**7 else -1)

Solution (Python):
from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)

Solution (Python):
from collections import deque

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

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  
    for dx, dy in warp:  
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Solution (Python):
from collections import deque

def f1(x,y,xa,ya):
    if reach[xa][ya] > reach[x][y]:
         if c[xa][ya] == ".":
            reach[xa][ya] = reach[x][y]
            r.append([xa,ya])
            q.append([xa,ya])

def f2(x,y,xa,ya):
    if 0 <= xa <= h+1 and 0 <= ya <= w+1:
    
        if reach[xa][ya] > reach[x][y] + 1:
            if c[xa][ya] == ".":
                reach[xa][ya] = reach[x][y] + 1
                q.append([xa,ya])

h,w = map(int,input().split())
cx, cy = map(int,input().split())
dx, dy = map(int,input().split())

c = [0]*(h+2)
for i in range(1,h+1):
    c[i] = [0] + list(input()) + [0]
c[0]  = [0]*(w+2)
c[-1] = [0]*(w+2)

reach = [[float("Inf") for j in range(w+2)] for i in range(h+2)]
q = deque([])

reach[cx][cy] = 0
q.append([cx,cy])

ans = 0

while q:

    
    
    x,y = q.popleft()
    
    r = deque()
    r.append([x,y])
    while r:
        xx,yy = r.popleft()
        
        f1(xx,yy,xx-1,yy)
        f1(xx,yy,xx+1,yy)
        f1(xx,yy,xx,yy-1)
        f1(xx,yy,xx,yy+1)
    
    for i in range(-2,3):
        for j in range(-2,3):
            f2(x,y,x+i,y+j)

if reach[dx][dy] == float("Inf"):
    print(-1)
else:
    print(reach[dx][dy])

Solution (Python):
import heapq
def main():
    h, w = map(int, input().split())
    strt_y, strt_x = map(int, input().split())
    goal_y, goal_x = map(int, input().split())
    stage = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h):
        s = input()
        for j in range(w):
            if s[j] == ".":
                stage[i+2][j+2] = float("inf")
    strt_y += 1
    strt_x += 1
    goal_y += 1
    goal_x += 1
    hq = [[0, strt_y, strt_x]]
    stage[strt_y][strt_x] = 0
    while len(hq) > 0:
        pt, crr_y, crr_x = heapq.heappop(hq)
        if stage[crr_y][crr_x] < pt:
            continue
        if crr_y == goal_y and crr_x == goal_x:
            break
        for i in range(crr_y-2, crr_y+2+1):
            for j in range(crr_x-2, crr_x+2+1):
                if abs(crr_y-i) + abs(crr_x-j) == 1:
                    if pt < stage[i][j]:
                        stage[i][j] = pt
                        heapq.heappush(hq, [pt, i, j])
                else:
                    if pt+1 < stage[i][j]:
                        stage[i][j] = pt+1
                        heapq.heappush(hq, [pt+1, i, j])
    if stage[goal_y][goal_x] == float("inf"):
        print(-1)
    else:
        print(stage[goal_y][goal_x])

if __name__ == "__main__":
    main()

Solution (Python):
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 = [input() for _ in range(h)]

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dxw = [-2, -1, 0, 1, 2, -2, -1, 0, 1, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2, -2, -1, 0, 1, 2]
dyw = [-2, -2, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2]

q = deque()
q.append((ch, cw, 0))
ans = [[10 ** 9] * w for _ in range(h)]
while len(q) > 0:
    x, y, c = q.popleft()
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.appendleft((nx, ny, c))
            ans[nx][ny] = c
    for i in range(24):
        nx, ny = x + dxw[i], y + dyw[i]
        if (
            nx >= 0
            and nx < h
            and ny >= 0
            and ny < w
            and c + 1 < ans[nx][ny]
            and s[nx][ny] == "."
        ):
            q.append((nx, ny, c + 1))
            ans[nx][ny] = c + 1
v = ans[dh][dw]
print(-1 if v == 10 ** 9 else v)

Solution (Python):
import sys
from collections import deque

H, W = map(int, sys.stdin.readline().split())
cy, cx = map(int, sys.stdin.readline().split())
gy, gx = map(int, sys.stdin.readline().split())
cy -= 1
cx -= 1
gy -= 1
gx -= 1
grid = []
for _ in range(H):
    grid.append(sys.stdin.readline().strip())
q = deque()
q.append((cx, cy, 0))
visited_d = {}
visited_e = {}
ans = float("inf")
while q:
    x, y, e = q.popleft()
    if (x, y) in visited_e and visited_e[(x, y)] <= e:
        continue
    visited_e[(x, y)] = e
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
            if nx == gx and ny == gy:
                ans = min(ans, e)
                continue
            if (nx, ny) not in visited_e:
                q.appendleft((nx, ny, e))
    for dx in range(-2, 3):
        for dy in range(-2, 3):
            if abs(dx) == 1 and dy == 0 or abs(dy) == 1 and dx == 0:
                continue
            nx = x + dx
            ny = y + dy
            if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
                if nx == gx and ny == gy:
                    ans = min(ans, e + 1)
                    continue
                if (nx, ny) not in visited_e:
                    q.append((nx, ny, e + 1))
print(-1 if ans == float("inf") else ans)

Solution (Python):


import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from collections import deque

movable = 46
blocked = 35
MAXDist = 1 << 31

def isMovable(p,q):
    if p < 0 or q < 0 or p >= H or q >= W:
        return False
    if maze[p][q] == blocked:
        return False
    return True

H,W = map(int,input().split())
sH,sW = map(int,input().split())
eH,eW = map(int,input().split())

maze = []
distance = []
for _ in range(H):
    maze.append(input())
    distance.append([MAXDist] * W)

distance[sH - 1][sW - 1] = 0
deq = deque()
deq.append((sH - 1, sW - 1, 0))

while len(deq):
    h,w,dist = deq.popleft()
    if dist > distance[h][w]:
        continue
    
    if isMovable(h - 1,w) and distance[h-1][w] > dist:
        distance[h-1][w] = dist
        deq.appendleft((h-1,w,dist))
    if isMovable(h + 1,w) and distance[h+1][w] > dist:
        distance[h + 1][w] = dist
        deq.appendleft((h + 1,w,dist))
    if isMovable(h,w - 1) and distance[h][w - 1] > dist:
        distance[h][w - 1] = dist
        deq.appendleft((h,w - 1,dist))
    if isMovable(h,w + 1) and distance[h][w + 1] > dist:
        distance[h][w + 1] = dist
        deq.appendleft((h,w + 1,dist))

    
    for i in range(h - 2,h + 3):
        for j in range(w - 2, w + 3):
            if isMovable(i,j) and distance[i][j] > dist + 1:
                distance[i][j] = dist + 1
                deq.append((i,j,dist + 1))

print(distance[eH - 1][eW - 1] if distance[eH - 1][eW - 1] != MAXDist else -1)

Solution (Python):
import sys
from collections import deque

h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch,cw=ch-1,cw-1
dh,dw=map(int,input().split())
dh,dw=dh-1,dw-1
s=[[*next(sys.stdin)] for _ in range(h)]

c=-1
for i in range(h):
    for j in range(w):
        if s[i][j]!='.':
            continue
        c+=1
        stk=[(i,j)]
        while stk:
            ii,jj=stk.pop()
            s[ii][jj]=c
            for di,dj in (-1,0),(0,1),(1,0),(0,-1):
                ni,nj=ii+di,jj+dj
                if not (0<=ni<h and 0<=nj<w):
                    continue
                if s[ni][nj]!='.':
                    continue
                stk.append((ni,nj))

n=c+1
cc=dc=-1
dirs=[-2,-1,0,1,2]
adj=[{*()} for _ in range(n)]
for i in range(h):
    for j in range(w):
        u=s[i][j]
        if u=='
            continue
        if i==ch and j==cw:
            cc=u
        elif i==dh and j==dw:
            dc=u
        for di in dirs:
            for dj in dirs:
                if di==dj==0:
                    continue
                ni,nj=i+di,j+dj
                if not (0<=ni<h and 0<=nj<w):
                    continue
                v=s[ni][nj]
                if v=='
                    continue
                if u!=v:
                    adj[u].add(v)
                    adj[v].add(u)

que=deque()                
que.append(cc)
vis={cc}
m=-1
ok=0
while que:
    m+=1
    for _ in range(len(que)):
        u=que.popleft()
        if u==dc:
            ok=1
            break
        for v in adj[u]:
            if v in vis:
                continue
            vis.add(v)
            que.append(v)
    if ok:
        break

if ok:
    print(m)
else:
    print(-1)

Solution (Python):

from collections import deque


def solve(): 
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())
	S=[input() for _ in range(H)]

	
	S = ['
	S.insert(0, '
	S.insert(0, '
	S.append('
	S.append('


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	

	

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	
	walk=[(1,0),(0,1),(-1,0),(0,-1)]
	warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
	

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				
				for i,j in warp:
					dh = h+i
					dw = w+j
					
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":

	

	solve()

Solution (Python):

from collections import deque

def solve(): 
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())
	S=[input() for _ in range(H)]

	
	S = ['
	S.insert(0, '
	S.insert(0, '
	S.append('
	S.append('


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	

	

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	
	walk=[(1,0),(0,1),(-1,0),(0,-1)]
	warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
	

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				
				for i,j in warp:
					dh = h+i
					dw = w+j
					
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":

	

	solve()

Solution (Python):

from collections import deque

def solve(H, W, CH, CW, DH, DW):
	
	S=[input() for _ in range(H)]
	S = ['
	S.insert(0, '
	S.insert(0, '
	S.append('
	S.append('


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	

	

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	
	walk=[(1,0),(0,1),(-1,0),(0,-1)]
	warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
	

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				
				for i,j in warp:
					dh = h+i
					dw = w+j
					
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())

	

	solve(H, W, CH, CW, DH, DW)

Solution (Python):

from collections import deque

def solve(H, W, CH, CW, DH, DW, S):
	
	S = ['
	S.insert(0, '
	S.insert(0, '
	S.append('
	S.append('


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	

	

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	
	walk=[(1,0),(0,1),(-1,0),(0,-1)]
	warp = [ (i,j) for i in range(-2,3) for j in range(-2,3) if (i, j) not in [(0, 0)] + walk ]
	

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				
				for i,j in warp:
					dh = h+i
					dw = w+j
					
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())

	S=[input() for _ in range(H)]

	solve(H, W, CH, CW, DH, DW, S)

Solution (Python):
from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="
    q = [(0, (Ch-1, Cw-1))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Solution (Python):
from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="

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

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()

Solution (Python):
from collections import deque

H,W = map(int, input().split())
C = list(map(int, input().split()))
D = list(map(int, input().split()))
D_y = D[0] -1   
D_x = D[1] -1   
MAP = [list(input()) for i in range(H)]
visited = [[-1] * W for i in range(H)]
visited[C[0]-1][C[1]-1] =0 
moves = [(0,1), (0,-1), (1,0), (-1,0)]

main_q = deque()
magic_q = deque()

main_q.append([C[0]-1, C[1]-1])


while main_q:
    y, x = main_q.popleft()
    magic_q.append([y,x])
    for move in moves:
        dy, dx = move
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or moved_x < 0 or moved_y > H - 1 or moved_x > W -1:
            continue
        if MAP[moved_y][moved_x] == '
            continue
        if MAP[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
            visited[moved_y][moved_x] = visited[y][x]
            main_q.append([moved_y,moved_x])

    
    if not main_q:
        while magic_q:
            y, x = magic_q.popleft()
            for dy in range(-2,3):
                for dx in range(-2,3):
                    moved_y = y + dy
                    moved_x = x + dx

                    if moved_y < 0 or moved_x < 0 or moved_y > H - 1 or moved_x > W -1:
                        continue
                    if MAP[moved_y][moved_x] == '
                        continue
                    if MAP[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                        visited[moved_y][moved_x] = visited[y][x] + 1
                        main_q.append([moved_y,moved_x])

anser = visited[D_y][D_x]
print(anser)