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
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

dist = [10**10]*(h*w)

a = [[]for i in range(2)]
i = 0
a[i].append(start)
dist[start] = 0

while a[0] or a[1]:
    p = a[i].pop()
    y = p//w
    x = p%w
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                q = (y+dy)*w + x+dx
                if abs(dy)+abs(dx)==1:
                    if dist[q]>dist[p]:
                        a[i].append(q)
                        dist[q] = dist[p]
                else:
                    if dist[q]>dist[p]+1:
                        a[i-1].append(q)
                        dist[q] = dist[p] + 1
    if not a[i]:
        i = [1,0][i]


print(-1 if dist[goal]==10**10 else dist[goal])

Solution (Python):
import sys
from itertools import count
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline




def solve(dist, start, goal, moves):
    q = [start]
    c0 = 0
    c1 = 1
    while q:
        nq = []
        while q:
            x = q.pop()
            if x == goal:
                return c0
            if dist[x] < c0:
                continue
            for d,l in moves:
                nx = x+d
                dnx = dist[nx]
                if dnx > c0:
                    dist[nx] = c0
                    q.append(nx)
                elif dnx < 0:
                    for t in l:
                        p = x+t
                        if dist[p] > c1:
                            dist[p] = c1
                            nq.append(p)
        q = nq
        c0 += 1
        c1 += 1
    return -1




if __name__ == '__main__':

    MOVES = (
    ((1, 0), ((2,-1),(2,0),(2,1),(2,2),(1,1))),
    ((-1, 0),((-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1))),
    ((0, 1), ((1,2),(0,2),(-1,2),(-2,2),(-1,1))),
    ((0, -1), ((1,-2),(0,-2),(-1,-2),(2,-2),(1,-1))),
    )

    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)+1,readline().split()))
    goal = tuple(map(lambda i:int(i)+1,readline().split()))

    H += 4
    W += 4

    dist = [-1]*(W*H)
    convert = lambda x,y: x*W+y

    start = convert(*start)
    goal = convert(*goal)

    i = 2*W+2
    for s in read().split():
        for c in s.decode():
            if c == '.':
                dist[i] = 10**7
            i += 1
        i += 4

    moves = tuple((convert(*d),tuple(convert(*d) for d in l)) for d,l in MOVES)

    print(solve(dist,start,goal,moves))

Solution (Python):
from collections import deque
inf=float("inf")


def BFS():
    color=[["white" for _ in range(w)] for _ in range(h)]
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque([])

    x,y=C
    x -=1
    y -=1
    queue.append([x,y])
    D[x][y]=0

    for i in range(h):
        for j in range(w):
            if S[i][j]=="
                color[i][j]="black"

    while len(queue)>0:
        x,y=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if color[X][Y]!="black" and D[X][Y]>D[x][y]:
                    D[X][Y]=D[x][y]
                    color[X][Y]="gray"
                    queue.appendleft([X,Y])

        for i in range(max(0,x-2),min(h,x+3)):
            for j in range(max(0,y-2),min(w,y+3)):
                X,Y=i,j
                if 0<=X<h and 0<=Y<w:
                    if color[X][Y]!="black" and D[X][Y]>D[x][y]+1:
                        D[X][Y]=D[x][y]+1
                        color[X][Y]="gray"
                        queue.append([X,Y])
        color[x][y]="black"

    return D[G[0]-1][G[1]-1]


h,w=map(int,input().split())
C=list(map(int,input().split()))
G=list(map(int,input().split()))
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Solution (Python):
from collections import deque

queue = deque()

H,W = [int(v) for v in input().split()]
ch,cw = [int(v) for v in input().split()]
dh,dw = [int(v) for v in input().split()]

S = [input() for _ in range(H)]
visited = [[-1 for _ in range (W)] for _ in range(H)]

queue.append((cw-1,ch-1,0))

def check(x,y):
    return x > -1 and x < W and y > -1 and y < H and S[y][x] != "

while len(queue) != 0:
    x,y,c = queue.popleft()
    if visited[y][x] != -1:
        continue
    visited[y][x] = c

    for d in [1,-1]:
        if check(x+d,y):
            queue.appendleft([x+d,y,c])
        if check(x,y+d):
            queue.appendleft([x,y+d,c])
    
    for dx in [-2,-1,0,1,2]:
        for dy in [-2,-1,0,1,2]:
            if check(x+dx,y+dy):
                queue.append((x+dx,y+dy,c+1))

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

Solution (Python):


from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            
            
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    if (new_h, new_w) not in reached:
                        qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

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


def BFS():
    D=[[inf for _ in range(w)] for _ in range(h)]
    queue=deque()
    queue.append([Cx-1,Cy-1,0])
    D[Cx-1][Cy-1]=0

    while len(queue)>0:
        x,y,cnt=queue.popleft()
        for i,j in [[1,0],[0,1],[-1,0],[0,-1]]:
            X,Y=x+i,y+j
            if 0<=X<h and 0<=Y<w:
                if S[X][Y]=="." and D[X][Y]>cnt:
                    D[X][Y]=cnt
                    queue.appendleft([X,Y,cnt])

        for X in range(max(0,x-2),min(h,x+3)):
            for Y in range(max(0,y-2),min(w,y+3)):
                if S[X][Y]=="." and D[X][Y]>cnt+1:
                    D[X][Y]=cnt+1
                    queue.append([X,Y,cnt+1])

    return D[Dx-1][Dy-1]


h,w=map(int,input().split())
Cx,Cy=map(int,input().split())
Dx,Dy=map(int,input().split())
S=[list(input()) for _ in range(h)]

D=BFS()
print(D if D!=inf else -1)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    H, W = map(int, readline().split())
    sh, sw = map(int, readline().split())
    gh, gw = map(int, readline().split())
    sh -= 1
    sw -= 1
    gh -= 1
    gw -= 1
    S = read().split()

    dist = [[INF] * W for _ in range(H)]
    walk = ((1, 0), (-1, 0), (0, 1), (0, -1))
    warp = ((-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))

    Q = deque()
    Q.append((sh, sw))
    Q2 = deque()
    dist[sh][sw] = 0

    while Q:
        while Q:
            h, w = Q.popleft()
            d = dist[h][w]
            flag = 0
            for dh, dw in walk:
                nh = h + dh
                nw = w + dw
                if 0<=nh<H and 0<=nw<W:
                    if S[nh][nw] == '.':
                        if dist[nh][nw] > d:
                            dist[nh][nw] = d
                            Q.append((nh,nw))
                    else:
                        flag += 1
            if flag:
                Q2.append((h,w))
        while Q2:
            h, w = Q2.popleft()
            d = dist[h][w]
            for dh, dw in warp:
                nh = h + dh
                nw = w + dw
                if 0<=nh<H and 0<=nw<W:
                    if S[nh][nw] == '.' and dist[nh][nw] == INF:
                        dist[nh][nw] = d + 1
                        Q.append((nh,nw))
    if dist[gh][gw] != INF:
        print(dist[gh][gw])
    else:
        print(-1)



if __name__ == '__main__':
    main()

Solution (Python):


from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  
    reached = set()

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if (h, w) in reached:
            
            
            continue
        reached.add((h, w))

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Solution (Python):
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [[-1]*W for i in range(H)]  
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append((sy, sx))
        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '
                    continue
                V[next_h][next_w] = v
                que.append((next_h, next_w))

    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    
    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

    
    

    
    

    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import count
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


MOVES = [
    ((1, 0), [(2,-1),(2,0),(2,1),(2,2),(1,1)]),
    ((-1, 0),[(-2,-1),(-2,0),(-2,1),(-2,-2),(-1,-1)]),
    ((0, 1), [(1,2),(0,2),(-1,2),(-2,2),(-1,1)]),
    ((0, -1), [(1,-2),(0,-2),(-1,-2),(2,-2),(1,-1)]),
    ]

CONVERTED_MOVES = None

def solve(dist, start, goal):
    q = [start]
    cnt = 0
    while q:
        nq = []
        while q:
            x = q.pop()
            if x == goal:
                return cnt
            if dist[x] < cnt:
                continue
            for d,l in CONVERTED_MOVES:
                nx = x+d
                if dist[nx] > cnt:
                    dist[nx] = cnt
                    q.append(nx)
                if dist[nx] < 0:
                    for t in l:
                        p = x+t
                        if dist[p] > cnt+1:
                            dist[p] = cnt+1
                            nq.append(p)
        q = nq
        cnt += 1

    return -1




if __name__ == '__main__':
    H,W = map(int,readline().split())
    start = tuple(map(lambda i:int(i)+1,readline().split()))
    goal = tuple(map(lambda i:int(i)+1,readline().split()))

    H += 4
    W += 4

    dist = [-1]*(W*H)

    start = start[0]*W+start[1]
    goal = goal[0]*W+goal[1]

    for t,s in zip(count(2*W,W),read().split()):
        for i,c in zip(count(t+2),s.decode()):
            if c == '.':
                dist[i] = 10**7

    convert = lambda x,y: x*W+y
    CONVERTED_MOVES = []
    for d,l in MOVES:
        d = convert(*d)
        l = [convert(*d) for d in l]
        CONVERTED_MOVES.append((d,l))

    print(solve(dist,start,goal))

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

dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
q = deque()

q.append((cx, cy, 0))

visited = [[float("inf") for _ in range(W)] for _ in range(H)]

visited[cy][cx] = 0
ans = float("inf")
while q:
    x, y, c = q.popleft()
    
    if visited[y][x] < c:
        
        continue
    
    
    for dx, dy in dirs:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < W and 0 <= ny < H and grid[ny][nx] != "
            
            if visited[ny][nx] <= c:
                
                continue
            
            visited[ny][nx] = c
            if nx == gx and ny == gy:
                continue
            q.appendleft((nx, ny, c))
    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 visited[ny][nx] < c + 1:
                    
                    continue
                
                visited[ny][nx] = c + 1
                if nx == gx and ny == gy:
                    continue
                q.append((nx, ny, c+1))

if visited[gy][gx] == float("inf"):
    print(-1)
else:
    print(visited[gy][gx])

Solution (Python):






from collections import deque





def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["
    s.append("
    for i in range(H):
        s.append("
    s.append("
    s.append("
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])

if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque
import sys

INF = 10 ** 8

H, W = map(int,input().split())
C = list(map(int,input().split()))
D = list(map(int,input().split()))
MAP = []
for _ in range(H):
    MAP.append(list(input()))
d = [[INF for i in range(W)] for j in range(H)]
tx = [1, 0, -1, 0]
ty = [0, 1, 0, -1]
tx_y = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]

Q = deque()
Q.append([C[0]-1, C[1]-1, 0])

while len(Q) != 0:
    x, y, cnt = Q.popleft()
    
    if x == D[0]-1 and y == D[1]-1:
        print(cnt)
        sys.exit()
    
    for i in range(4):
        nx = x + tx[i]
        ny = y + ty[i]
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt:
            d[nx][ny] = cnt
            Q.appendleft([nx, ny, cnt])
    
    for i, j in tx_y:
        nx = x + i
        ny = y + j
        if 0 <= nx < H and 0 <= ny < W and MAP[nx][ny] == "." and d[nx][ny] > cnt+1:
            d[nx][ny] = cnt+1
            Q.append([nx, ny, cnt+1])

print(-1)

Solution (Python):


from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            
            
            continue
        grid[h][w] = 'R'  

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if 0 <= new_h < height and 0 <= new_w < width:
                if grid[new_h][new_w] == '.':
                    qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

Solution (Python):

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

  
ans = [[-1] * W for i in range(H)]  
ans[Ch][Cw] = 0
from collections import deque
q = deque([[0, Ch, Cw]])  
one = [[0, 1], [0, -1], [1, 0], [-1, 0]]
two = [[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]] 
while q:
  cnt, h, w = q.popleft()
  if ans[h][w] < cnt:
    continue
  for i, j in one:
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt:
          ans[h + i][w + j] = cnt
          q.appendleft([cnt, h + i, w + j])
  for i, j in two:  
    if (0 <= h + i < H) and (0 <= w + j < W) and (maze[h + i][w + j] != "
        if ans[h + i][w + j] == -1 or ans[h + i][w + j] > cnt + 1:
          ans[h + i][w + j] = cnt + 1
          q.append([cnt + 1, h + i, w + j])
              
print(ans[Dh][Dw])

Solution (Python):


from collections import deque


def main():
    height, width = [int(x) for x in input().split()]
    init_h, init_w = [int(x) - 1 for x in input().split()]
    dest_h, dest_w = [int(x) - 1 for x in input().split()]
    grid = [list(input()) for _ in range(height)]

    adjacents = (
        (1, 0),
        (0, 1),
        (-1, 0),
        (0, -1)
    )

    def gen_warp_can_reach():
        for h in range(-2, 3):
            for w in range(-2, 3):
                if h == 0 == w:
                    continue
                if (h, w) in adjacents:
                    continue
                yield (h, w)
    warp_can_reach = tuple(gen_warp_can_reach())
    qu = deque()
    qu.append((init_h, init_w, 0))  

    while qu:
        h, w, warps = qu.popleft()
        if h == dest_h and w == dest_w:
            return warps
        if grid[h][w] == 'R':
            
            
            continue
        grid[h][w] = 'R'  

        for h_delta, w_delta in adjacents:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.appendleft((new_h, new_w, warps))

        for h_delta, w_delta in warp_can_reach:
            new_h, new_w = h + h_delta, w + w_delta
            if new_h < 0 or new_h >= height or new_w < 0 or new_w >= width:
                continue
            if grid[new_h][new_w] == '.':
                qu.append((new_h, new_w, warps + 1))
    return -1


if __name__ == '__main__':
    print(main())

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

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    
    d = [float('inf')]*len(path)
    d[s] = 0

    
    q = [(0,s)]
    heapq.heapify(q)

    
    while q:
        c,p = heapq.heappop(q)

        
        if d[p]<c:
            continue

        
        for to,cost in path[p]:
            
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])

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):
def main():
    from collections import deque
    import sys

    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    c = [input().rstrip() for _ in range(h)]
    cw -= 1
    ch -= 1
    dw -= 1
    dh -= 1
    c[ch] = c[ch][:cw] + "=" + c[ch][cw + 1 :]
    bfs = deque([[cw, ch]])
    warp_before = set()
    warp_after = set()

    for cnt in range(1000000):  
        while bfs:  
            for _ in range(len(bfs)):
                now_x, now_y = bfs.popleft()
                for next_x, next_y in zip([1, 0, -1, 0], [0, 1, 0, -1]):
                    x, y = now_x + next_x, now_y + next_y
                    if 0 <= x < w and 0 <= y < h:
                        if x == dw and y == dh:
                            print(cnt)
                            exit()
                        c_next = c[y][x]
                        if c_next == "
                            warp_before.add((now_x, now_y))
                        if c_next == ".":  
                            c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                            bfs.append([x, y])
        else:
            if not warp_before:
                print(-1)
                exit()
            for now_x, now_y in warp_before:
                
                if c[now_y][now_x] == "=":
                    for next_y in range(-2, 3):
                        for next_x in range(-2, 3):
                            x, y = now_x + next_x, now_y + next_y
                            if 0 <= x < w and 0 <= y < h:
                                warp_after.add((x, y))
            for x, y in warp_after:
                
                if c[y][x] == ".":
                    if x == dw and y == dh:  
                        print(cnt + 1)
                        exit()
                    c[y] = c[y][:x] + "=" + c[y][x + 1 :]
                    bfs.append([x, y])
            warp_before = set()
            warp_after = set()


if __name__ == "__main__":
    main()