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



Sample input:
4 4
1 1
4 4
..#.
..#.
.#..
.#..


Sample output:
1

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from heapq import heapify, heappush, heappop
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect
import copy

sys.setrecursionlimit(10**6)

# lis_of_lis = [[] for _ in range(N)]


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


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


def S():
    return sys.stdin.readline()[:-1]


def C(line):
    return [sys.stdin.readline() for _ in range(line)]



def main(H, W, c_h, c_w, d_h, d_w):

    que = deque([(c_h, c_w)])
    INF = 1e9
    dist = [[INF]*W for _ in range(H)]
    dist[c_h][c_w] = 0
    while que:
        # print(que)
        tmp = que.popleft()
        h, w = tmp
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if board[new_h][new_w] == '#':
                continue
            if dist[new_h][new_w] <= d:
                continue
            dist[new_h][new_w] = d
            que.appendleft((new_h, new_w))
        # 魔法
        for m_dy in range(-2, 3):
            for m_dx in range(-2, 3):
                new_h = h + m_dy
                new_w = w + m_dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if board[new_h][new_w] == '#':
                    continue
                if dist[new_h][new_w] <= d + 1:
                    continue
                dist[new_h][new_w] = d + 1
                que.append((new_h, new_w))

    ans = dist[d_h][d_w]
    if ans == INF:
        print(-1)
    else:
        print(ans)


H, W = zz()
c_h, c_w = zz()
d_h, d_w = zz()
board = []
c_h -= 1
c_w -= 1
d_h -= 1
d_w -= 1
for i in range(H):
    tmp = S()
    board.append(tmp)
main(H, W, c_h, c_w, d_h, d_w)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
S = tuple(map(lambda x:int(x)-1, input().split()))
G = tuple(map(lambda x:int(x)-1, input().split()))
field = []
for _ in range(H):
    field.append(input())

cost = [[-1] * W for _ in range(H)]

def can_go(pos):
    if pos[0] >= 0 and pos[0] < H and pos[1] >= 0 and pos[1] < W:
        if field[pos[0]][pos[1]] == '.' and cost[pos[0]][pos[1]] == -1:
            return True
        else:
            return False
    else:
        return False

def recursive_walk(pos):
    dests = set()
    stack = [pos]
    while stack:
        pos = stack.pop()
        if pos in dests:
            continue
        dests.add(pos)
        stack += walk(pos)
    return dests

def walk(pos):
    dests = []
    for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        new_pos = (pos[0]+d[0], pos[1]+d[1])
        if can_go(new_pos):
            dests.append(new_pos)
    return dests

def warp(pos):
    dests = []
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            new_pos = (pos[0]+dy, pos[1]+dx)
            if can_go(new_pos):
                dests.append(new_pos)
    return dests

q = deque()
q.append([S, 0])

while q:
    pos, c = q.popleft()
    if cost[pos[0]][pos[1]] != -1:
        continue
    cost[pos[0]][pos[1]] = c
    if pos == G:
        break
    warp_from = [pos]
    for dest in recursive_walk(pos):
        if cost[dest[0]][dest[1]] == -1:
            cost[dest[0]][dest[1]] = c
            warp_from.append(dest)
    warp_to = set()
    for fr in warp_from:
        for dest in warp(fr):
            if cost[dest[0]][dest[1]] == -1:
                warp_to.add(dest)
    for dest in warp_to:
        q.append((dest, c+1))
print(cost[G[0]][G[1]])

Submission status: Accepted

Solution code:
def main():
    import sys,heapq
    input = sys.stdin.buffer.readline
 
    h,w = map(int,input().split())
    cx,cy = map(int,input().split())
    dx,dy = map(int,input().split())
    cx -= 1
    cy -= 1
    dx -= 1
    dy -= 1
 
    start = cx*w + cy
    goal = dx*w + dy
 
 
    s = []
    for _ in range(h):
        s.append(list(input()))
 
    dg = 10**7
 
 
    edge = [[] for _ in range(h*w)]
    for xy in range(h*w):
        x,y = divmod(xy,w)
        if s[x][y] == 35:
            continue
        for i in range(-2,3):
            for j in range(-2,3):
                if i == 0 and j == 0:
                    continue
                if 0 <= x+i < h and 0 <= y+j < w and s[x+i][y+j] == 46:
                    #上下左右/ワープ
                    if (i == 0 and abs(j) == 1) or (j == 0 and abs(i) == 1):
                        edge[xy].append( (x+i)*w + y+j )
                    else:
                        edge[xy].append(dg + (x+i)*w + y+j )
 
    d = [float("inf")]*(h*w)
    d[start] = 0
 
    tank = []
 
    for e in edge[start]:
        heapq.heappush(tank,e)
 
 
    while tank:
        now = heapq.heappop(tank)
        cost,xy = divmod(now,dg)
        if d[xy] != float("inf"):
            continue
        d[xy] = cost
        if xy == goal:
            break
        for nxt in edge[xy]:
            if nxt >= dg:
                if d[nxt-dg] == float("inf"):
                    heapq.heappush(tank,(cost+1)*dg + nxt-dg)
            else:
                if d[nxt] == float("inf"):
                    heapq.heappush(tank,cost*dg + nxt)
 
    if d[goal] == float("inf"):
        print(-1)
    else:
        print(d[goal])
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
cy, cx = map(int, input().split())
sy, sx = map(int, input().split())
tiles = [list(input()) for _ in range(H)]

# initialization
INF = 10**4
arrived = [[INF for _ in range(W)] for __ in range(H)]
paths = deque()
warps = deque()
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
moves = [-2, -1, 0, 1, 2]
arrived[cy-1][cx-1] = 0
paths.append([cx-1, cy-1])
count = 0

# BFS
while(len(paths) > 0):
  while(len(paths) > 0):
    nx, ny = paths.popleft()
    if ny == sy-1 and nx == sx-1:
      print(count)
      exit()
    for i in range(4):
      if 0 <= nx+dx[i] < W and 0 <= ny+dy[i] < H and arrived[ny+dy[i]][nx+dx[i]] > count and tiles[ny+dy[i]][nx+dx[i]] == '.':
        paths.append([nx+dx[i], ny+dy[i]])
        arrived[ny+dy[i]][nx+dx[i]] = count
    for x in moves:
      for y in moves:
        if 0 <= nx+x < W and 0 <= ny+y < H and arrived[ny+y][nx+x] == INF and tiles[ny+y][nx+x] == '.':
          warps.append([nx+x, ny+y])
  count += 1
  while(len(warps) > 0):
    nx, ny = warps.popleft()
    if arrived[ny][nx] == INF:
      arrived[ny][nx] = count
      paths.append([nx, ny])
print(-1)

Submission status: Accepted

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

INF = 10**9
m = [[INF]*W for _ in range(H)]
m[ch][cw] = 0

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

cnt = 0
while q:
    cnt += 1
    h, w, n = q.popleft()
    for i, j in [(0,1), (0,-1), (1,0), (-1,0)]:
        if (h+i<0 or w+j<0) or (h+i>=H or w+j>=W):
            continue
        if m[h+i][w+j] <= n:
            continue
        if s[h+i][w+j] == '#':
            continue
        m[h+i][w+j] = n
        q.appendleft((h+i, w+j, n))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if (h+i<0 or w+j<0) or (h+i>=H or w+j>=W):
                continue
            if m[h+i][w+j] <= n+1:
                continue
            if s[h+i][w+j] == '#':
                continue
            m[h+i][w+j] = n + 1
            q.append((h+i, w+j, n+1))
if m[dh][dw] == INF:
    print(-1)
else:
    print(m[dh][dw])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
H,W = map(int , input().split())
sh,sw = map(int , input().split())
eh,ew = map(int , input().split())
mv_a_pts = [[-1,0],[1,0],[0,-1],[0,1]]
mv_b_pts = [(-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, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
maze = [input() for _ in range(H)]
warp_cnts = [[None]*(W) for j in range(H)]
 
def mv_a():
  while len(mv_a_tgs):
    h,w = mv_a_tgs.pop()
    mv_b_tgs.append([h,w])
    warp_cnts[h][w] = cnt
    for vh,vw in mv_a_pts:
      tgh = h + vh
      tgw = w + vw
      if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
        if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
          mv_a_tgs.append([tgh,tgw])

def mv_b():
  while len(mv_b_tgs):
    h,w = mv_b_tgs.pop()
    for vh,vw in mv_b_pts:
      tgh = h + vh
      tgw = w + vw
      if 0 <= tgh <= H-1 and 0 <= tgw <= W-1 :
        if warp_cnts[tgh][tgw] is None and maze[tgh][tgw] != "#":
          mv_a_tgs.append([tgh,tgw])
        
mv_b_tgs=[]
mv_a_tgs = [[sh-1,sw-1]]
cnt = 0
while len(mv_a_tgs)>0:
  mv_a()
  mv_b()
  cnt+=1
print(-1 if warp_cnts[eh-1][ew-1] is None else warp_cnts[eh-1][ew-1])

Submission status: Accepted

Solution code:
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())
W_ = W + 4
H_ = H + 4
S = ["#" * W_] * 2 + ["##" + input() + "##" for _ in range(H)] + ["#" * W_] * 2

INF = float('inf')
costs = [[INF] * W_ for _ in range(H_)]
costs[C_h + 1][C_w + 1] = 0
d0 = deque()
d0.append((C_h + 1, C_w + 1, 0))
d1 = deque()
while d0:
    h, w, c = d0.popleft()
    d1.append((h, w, c))
    for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        hh = h + i
        ww = w + j
        if S[hh][ww] == '.' and c < costs[hh][ww]:
            costs[hh][ww] = c
            d0.appendleft((hh, ww, c))
    if len(d0) == 0:
        while d1:
            h, w, c = d1.popleft()
            for i in range(5):
                for j in range(5):
                    hh = h + i - 2
                    ww = w + j - 2
                    if S[hh][ww] == '.' and c + 1 < costs[hh][ww]:
                        costs[hh][ww] = c + 1
                        d0.append((hh, ww, c + 1))

if costs[D_h + 1][D_w + 1] != INF:
    ans = costs[D_h + 1][D_w + 1]
else:
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys 
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W = map(int,readline().split())
sx,sy = map(int,readline().split())
gx,gy = map(int,readline().split())
sx -= 1; sy -= 1
gx -= 1; gy -= 1

grid = [readline().decode().rstrip() for _ in range(H)]
INF = 10 ** 31
dist = [[INF]*W for _ in range(H)]

X = [(0,1),(-1,0),(0,-1),(1,0)]
Y = [(-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)]
# 0-1 bfs
def ZeroOne_bfs():
    while q:
        x,y = q.popleft()
        for dx,dy in X:
            nx = x + dx; ny = y + dy
            if not(0 <= nx < H and 0 <= ny < W):
                continue
            d = dist[x][y]
            if grid[nx][ny] == '.':
                if d < dist[nx][ny]:
                    dist[nx][ny] = d
                    q.appendleft((nx,ny))
                    
        for dx,dy in Y:
            nx = x + dx; ny = y + dy
            if not(0 <= nx < H and 0 <= ny < W):
                continue
            d = dist[x][y] + 1
            if grid[nx][ny] == '.':
                if d < dist[nx][ny]:
                    dist[nx][ny] = d 
                    q.append((nx,ny))

q = deque([(sx,sy)])
dist[sx][sy] = 0
ZeroOne_bfs()
ans = dist[gx][gy]

print(ans if ans != INF else -1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
def dfs(h, w, num):
    done[h][w] = num
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nh, nw = h+dh, w+dw
        if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
            continue
        if done[nh][nw] == -1:
            dfs(nh, nw, num)
num = 0
for i in range(H):
    for j in range(W):
        if done[i][j] == -1 and S[i][j] == ".":
            dfs(i, j, num)
            num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

from collections import deque
import heapq
INF = 10**18

def dijkstra(start, G):
    done = [False]*(len(G))
    dist = [INF]*(len(G))
    dist[start] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        _, cur = heapq.heappop(h)
        if done[cur]: continue
        done[cur] = True
        for to, cost in G[cur]:
            if dist[cur]+cost < dist[to]:
                dist[to] = dist[cur]+cost
                heapq.heappush(h, [dist[to], to])
    return dist

H, W = map(int, input().split())
sh, sw = map(lambda x: int(x)-1, input().split())
gh, gw = map(lambda x: int(x)-1, input().split())
S = [input() for _ in range(H)]
done = [[-1]*W for _ in range(H)]
q = deque()
num = 0
for ii in range(H):
    for jj in range(W):
        if done[ii][jj] != -1: continue
        q.append((ii, jj))
        done[ii][jj] = num
        while q:
            h, w = q.popleft()
            for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nh, nw = h+dh, w+dw
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                if done[nh][nw] == -1:
                    q.append((nh, nw))
                    done[nh][nw] = num
        num += 1
G = [[] for _ in range(num)]
done2 = {}
for h in range(H):
    for w in range(W):
        if S[h][w] != ".": continue
        fr = done[h][w]
        for ii in range(-2, 3):
            for jj in range(-2, 3):
                nh, nw = h+ii, w+jj
                if not (0 <= nh < H and 0 <= nw < W and S[nh][nw] == "."):
                    continue
                to = done[nh][nw]
                if fr != to and (not (fr, to) in done2):
                    done2[(fr, to)] = True
                    done2[(to, fr)] = True
                    G[fr].append((to, 1))
                    G[to].append((fr, 1))
D = dijkstra(done[sh][sw], G)
ans = D[done[gh][gw]]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
si, sj = map(int, input().split())
ti, tj = map(int, input().split())
s = [input() for _ in range(h)]
si -= 1
sj -= 1
ti -= 1
tj -= 1

INF = 10**9
di = [-1, 0, 1, 0]
dj = [0, -1, 0, 1]
dist = [[INF] * w for _ in range(h)]
q = deque()
dist[si][sj] = 0
q.appendleft([si, sj])

while q:
    i, j = q.popleft()
    d = dist[i][j]
    for v in range(4):
        ni = i + di[v]
        nj = j + dj[v]
        if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
        if s[ni][nj] == '#': continue
        if dist[ni][nj] <= d: continue
        dist[ni][nj] = d
        q.appendleft([ni, nj])
    for ei in range(-2, 3):
        for ej in range(-2, 3):
            ni = i + ei
            nj = j + ej
            if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
            if s[ni][nj] == '#': continue
            if dist[ni][nj] <= d+1: continue
            dist[ni][nj] = d+1
            q.append([ni, nj])

ans = dist[ti][tj]
if ans == INF: ans = -1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
 
 
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, 0), (-1, 1), (-1, 2),
        (0, -2), (0, -1), (0, 1), (0, 2),
        (1, -2), (1, -1), (1, 0), (1, 1), (1, 2),
        (2, -2), (2, -1), (2, 0), (2, 1), (2, 2),]
 
 
def get_warped(walked, map_):
    warped = deque()
    while walked:
        h, w = walked.popleft()
        for i, j in warp:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                warped.append((h2, w2))
                map_[h2][w2] = map_[h][w] + 1
    return warped, map_
 
 
def get_walked(candidate, map_):
    walked = deque()
    while candidate:
        h, w = candidate.popleft()
        walked.append((h, w))
        for i, j in walk:
            h2 = h + i
            w2 = w + j
            if -1 < h2 < H and -1 < w2 < W and map_[h2][w2] == '.':
                candidate.append((h2, w2))
                map_[h2][w2] = map_[h][w]
    return walked, map_
 
H, W = map(int, input().split())
s_h, s_w = [i-1 for i in map(int, input().split())]
d_h, d_w = [i-1 for i in map(int, input().split())]
map_ = [list(input()) for i in range(H)]
 
candidate = deque([(s_h, s_w)])
map_[s_h][s_w] = 0
 
while candidate:
    walked, map_ = get_walked(candidate, map_)
    candidate, map_ = get_warped(walked, map_)
 
for h in range(H):
    for w in range(W):
        if map_[h][w] == '.':
            map_[h][w] = -1
 
print(map_[d_h][d_w])

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce, lru_cache
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def MAP1()  : return map(lambda x:int(x)-1,input().split())
def LIST()  : return list(MAP())
def LIST1() : return list(MAP1())

def bfs():
    d = [[inf]*w for i in range(h)]

    dy_dx0 = [[0,1],[1,0],[0,-1],[-1,0]] 
    dy_dx1 = [[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]]

    que = deque([])
    que.append((sy, sx))
    d[sy][sx] = 0
 
    while que:
        p = que.popleft()
        if p[0] == gy and p[1] == gx:
            break
        for i in range(4):
            ny = p[0] + dy_dx0[i][0]
            nx = p[1] + dy_dx0[i][1]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] > d[p[0]][p[1]]:
                que.appendleft((ny,nx))
                d[ny][nx] = d[p[0]][p[1]]

        for i in range(20):
            ny = p[0] + dy_dx1[i][0]
            nx = p[1] + dy_dx1[i][1]
 
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != '#' and d[ny][nx] == inf:
                que.append((ny,nx))
                d[ny][nx] = d[p[0]][p[1]] + 1 
 
    return d[gy][gx]

h, w = MAP()
sy, sx = MAP1()
gy, gx = MAP1()
s = [input() for _ in range(h)]
ans = bfs()
if ans == inf:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import base64

exec(base64.b64decode(b'aW1wb3J0IHN1YnByb2Nlc3MKaW1wb3J0IHN5cwoKY29kZSA9IHIiIiIjaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8Y2Fzc2VydD4KI2luY2x1ZGUgPGNjdHlwZT4KI2luY2x1ZGUgPGNocm9ubz4KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y29tcGxleD4KI2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxkZXF1ZT4KI2luY2x1ZGUgPGlvbWFuaXA+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPG51bWVyaWM+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHJhbmRvbT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8dHVwbGU+CiNpbmNsdWRlIDx1dGlsaXR5PgojaW5jbHVkZSA8dmVjdG9yPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnVzaW5nIGludDY0ID0gbG9uZyBsb25nOwoKI2RlZmluZSBhbGwoJCkgYmVnaW4oJCksIGVuZCgkKQojZGVmaW5lIHJhbGwoJCkgcmJlZ2luKCQpLCByZW5kKCQpCgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgZXJhcXVlKHN0ZDo6dmVjdG9yPFQ+JiB2ZWMpIHsKICB2ZWMuZXJhc2Uoc3RkOjp1bmlxdWUodmVjLmJlZ2luKCksIHZlYy5lbmQoKSksIHZlYy5lbmQoKSk7CiAgcmV0dXJuOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIGludCBsb3dlcl9wb3NpdGlvbihjb25zdCBzdGQ6OnZlY3RvcjxUPiYgdmVjLCBUIHZhbCkgewogIHJldHVybiBzdGF0aWNfY2FzdDxpbnQ+KHN0ZDo6ZGlzdGFuY2UoCiAgICAgIHZlYy5iZWdpbigpLCBzdGQ6Omxvd2VyX2JvdW5kKHZlYy5iZWdpbigpLCB2ZWMuZW5kKCksIHZhbCkpKTsKfQoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGluZSBpbnQgdXBwZXJfcG9zaXRpb24oY29uc3Qgc3RkOjp2ZWN0b3I8VD4mIHZlYywgVCB2YWwpIHsKICByZXR1cm4gc3RhdGljX2Nhc3Q8aW50PihzdGQ6OmRpc3RhbmNlKAogICAgICB2ZWMuYmVnaW4oKSwgc3RkOjp1cHBlcl9ib3VuZCh2ZWMuYmVnaW4oKSwgdmVjLmVuZCgpLCB2YWwpKSk7Cn0KCnRlbXBsYXRlIDxjbGFzcyBUPgppbmxpbmUgc3RkOjpzdHJpbmcgdG9fYmluYXJ5KFQgbikgewogIGFzc2VydChuID4gMCk7CiAgc3RkOjpzdHJpbmcgcmV0ID0gIiI7CiAgd2hpbGUgKG4pIHJldCArPSAobiAmIDEpID8gJzEnIDogJzAnLCBuID4+PSAxOwogIHN0ZDo6cmV2ZXJzZShyZXQuYmVnaW4oKSwgcmV0LmVuZCgpKTsKICByZXR1cm4gcmV0Owp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KaW5saW5lIHZvaWQgcHJpbnRsbihUIHZhbCkgewogIHN0ZDo6Y291dCA8PCB2YWwgPDwgJ1xuJzsKfQoKdGVtcGxhdGUgPGNsYXNzIFQ+CmlubGluZSB2b2lkIHByaW50bG4oY29uc3Qgc3RkOjp2ZWN0b3I8VD4mIHZlYykgewogIGludCBzeiA9IHZlYy5zaXplKCk7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBzejsgKytpKSBzdGQ6OmNvdXQgPDwgdmVjW2ldIDw8ICIgXG4iW2kgPT0gc3ogLSAxXTsKfQoKaW5saW5lIHZvaWQgWWVzKGJvb2wgY29uZCkgewogIHByaW50bG4oY29uZCA/ICJZZXMiIDogIk5vIik7Cn0KCmlubGluZSB2b2lkIFlFUyhib29sIGNvbmQpIHsKICBwcmludGxuKGNvbmQgPyAiWUVTIiA6ICJOTyIpOwp9Cgp0ZW1wbGF0ZSA8Y2xhc3MgVD4KdXNpbmcgYmluYXJ5X2hlYXAgPSBzdGQ6OnByaW9yaXR5X3F1ZXVlPFQsIHN0ZDo6dmVjdG9yPFQ+LCBzdGQ6OmdyZWF0ZXI8VD4+OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CnN0ZDo6aXN0cmVhbSYgb3BlcmF0b3I+PihzdGQ6OmlzdHJlYW0mIGlzLCBzdGQ6OnZlY3RvcjxUPiYgdmVjKSB7CiAgZm9yIChUJiBlIDogdmVjKSBpcyA+PiBlOwogIHJldHVybiBpczsKfQoKdGVtcGxhdGUgPGNsYXNzIFQsIGNsYXNzIFU+CnN0ZDo6aXN0cmVhbSYgb3BlcmF0b3I+PihzdGQ6OmlzdHJlYW0mIGlzLCBzdGQ6OnBhaXI8VCwgVT4mIHApIHsKICByZXR1cm4gaXMgPj4gcC5maXJzdCA+PiBwLnNlY29uZDsKfQoKdGVtcGxhdGUgPGNsYXNzIFR1cGxlLCBzdGQ6OnNpemVfdC4uLiBJcz4Kdm9pZCB0dXBsZV9pbihzdGQ6OmlzdHJlYW0mIGlzLCBUdXBsZSYgdHAsIHN0ZDo6aW5kZXhfc2VxdWVuY2U8SXMuLi4+KSB7CiAgKChpcyA+PiBzdGQ6OmdldDxJcz4odHApKSwgLi4uKTsKfQoKdGVtcGxhdGUgPGNsYXNzLi4uIEFyZ3M+CnN0ZDo6aXN0cmVhbSYgb3BlcmF0b3I+PihzdGQ6OmlzdHJlYW0mIGlzLCBzdGQ6OnR1cGxlPEFyZ3MuLi4+JiB0cCkgewogIHR1cGxlX2luKGlzLCB0cCwgc3RkOjppbmRleF9zZXF1ZW5jZV9mb3I8QXJncy4uLj57fSk7CiAgcmV0dXJuIGlzOwp9CgoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIGdyYXBoIHsKIHB1YmxpYzoKICBncmFwaChpbnQgbikgOiBuXyhuKSB7IGRhdGFfLnJlc2l6ZShuXyk7IH0KICBzdHJ1Y3QgZWRnZSB7CiAgICBpbnQgZnJvbSwgdG87CiAgICBUIGNvc3Q7CgogICAgZWRnZShpbnQgZnJvbV8sIGludCB0b18sIFQgY29zdF8pIDogZnJvbShmcm9tXyksIHRvKHRvXyksIGNvc3QoY29zdF8pIHt9CiAgfTsKICBpbnQgbl87CiAgc3RkOjp2ZWN0b3I8c3RkOjp2ZWN0b3I8aW50Pj4gZGF0YV87CiAgc3RkOjp2ZWN0b3I8ZWRnZT4gZWRnZXNfOwoKICB2aXJ0dWFsIHZvaWQgYWRkKGludCBmcm9tLCBpbnQgdG8sIFQgY29zdCkgPSAwOwp9OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIGZvcmVzdCA6IHB1YmxpYyBncmFwaDxUPiB7CiBwdWJsaWM6CiAgdXNpbmcgZ3JhcGg8VD46Om5fOwogIHVzaW5nIGdyYXBoPFQ+OjpkYXRhXzsKICB1c2luZyBncmFwaDxUPjo6ZWRnZXNfOwoKICBmb3Jlc3QoaW50IG4pIDogZ3JhcGg8VD4obikge30KCiAgdm9pZCBhZGQoaW50IGZyb20sIGludCB0bywgVCBjb3N0ID0gMSkgewogICAgYXNzZXJ0KDAgPD0gZnJvbSAmJiBmcm9tIDwgbl8gJiYgMCA8PSB0byAmJiB0byA8IG5fKTsKICAgIGludCBpZCA9IGVkZ2VzXy5zaXplKCk7CiAgICBhc3NlcnQoaWQgPCBuXyAtIDEpOwogICAgZGF0YV9bZnJvbV0uZW1wbGFjZV9iYWNrKGlkKTsKICAgIGRhdGFfW3RvXS5lbXBsYWNlX2JhY2soaWQpOwogICAgZWRnZXNfLmVtcGxhY2VfYmFjayhmcm9tLCB0bywgY29zdCk7CiAgfQp9OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIGRpZ3JhcGggOiBwdWJsaWMgZ3JhcGg8VD4gewogcHVibGljOgogIHVzaW5nIGdyYXBoPFQ+OjpuXzsKICB1c2luZyBncmFwaDxUPjo6ZGF0YV87CiAgdXNpbmcgZ3JhcGg8VD46OmVkZ2VzXzsKCiAgZGlncmFwaChpbnQgbikgOiBncmFwaDxUPihuKSB7fQoKICB2b2lkIGFkZChpbnQgZnJvbSwgaW50IHRvLCBUIGNvc3QgPSAxKSB7CiAgICBhc3NlcnQoMCA8PSBmcm9tICYmIGZyb20gPCBuXyAmJiAwIDw9IHRvICYmIHRvIDwgbl8pOwogICAgaW50IGlkID0gZWRnZXNfLnNpemUoKTsKICAgIGRhdGFfW2Zyb21dLmVtcGxhY2VfYmFjayhpZCk7CiAgICBlZGdlc18uZW1wbGFjZV9iYWNrKGZyb20sIHRvLCBjb3N0KTsKICB9CgogIGRpZ3JhcGg8VD4gcmV2ZXJzZSgpIGNvbnN0IHsKICAgIGRpZ3JhcGg8VD4gcmV2KG5fKTsKICAgIGZvciAoY29uc3QgYXV0byYgW2Zyb20sIHRvLCBjb3N0XSA6IGVkZ2VzXykgewogICAgICByZXYuYWRkKHRvLCBmcm9tLCBjb3N0KTsKICAgIH0KICAgIHJldHVybiByZXY7CiAgfQp9OwoKdGVtcGxhdGUgPGNsYXNzIFQ+CmNsYXNzIHVuZGlncmFwaCA6IHB1YmxpYyBncmFwaDxUPiB7CiBwdWJsaWM6CiAgdXNpbmcgZ3JhcGg8VD46Om5fOwogIHVzaW5nIGdyYXBoPFQ+OjpkYXRhXzsKICB1c2luZyBncmFwaDxUPjo6ZWRnZXNfOwoKICB1bmRpZ3JhcGgoaW50IG4pIDogZ3JhcGg8VD4obikge30KCiAgdm9pZCBhZGQoaW50IGZyb20sIGludCB0bywgVCBjb3N0ID0gMSkgewogICAgYXNzZXJ0KDAgPD0gZnJvbSAmJiBmcm9tIDwgbl8gJiYgMCA8PSB0byAmJiB0byA8IG5fKTsKICAgIGludCBpZCA9IGVkZ2VzXy5zaXplKCk7CiAgICBkYXRhX1tmcm9tXS5lbXBsYWNlX2JhY2soaWQpOwogICAgZGF0YV9bdG9dLmVtcGxhY2VfYmFjayhpZCk7CiAgICBlZGdlc18uZW1wbGFjZV9iYWNrKGZyb20sIHRvLCBjb3N0KTsKICB9Cn07CgoKdGVtcGxhdGUgPGNsYXNzIFQ+CnN0ZDo6dmVjdG9yPFQ+IGRpamtzdHJhKGNvbnN0IGdyYXBoPFQ+JiBnLCBpbnQgcykgewogIGFzc2VydCgwIDw9IHMgJiYgcyA8IGcubl8pOwogIHN0ZDo6dmVjdG9yPFQ+IGRpc3QoZy5uXywgc3RkOjpudW1lcmljX2xpbWl0czxUPjo6bWF4KCkpOwogIHN0cnVjdCBQYWlyIHsKICAgIFQgZDsKICAgIGludCB2OwogICAgUGFpcihUIGRfLCBpbnQgdl8pIDogZChkXyksIHYodl8pIHt9CiAgICBib29sIG9wZXJhdG9yPChjb25zdCBQYWlyJiByaHMpIGNvbnN0IHsKICAgICAgcmV0dXJuIGQgPiByaHMuZDsKICAgIH0KICB9OwogIC8vc3RkOjpwcmlvcml0eV9xdWV1ZTxQYWlyLCBzdGQ6OnZlY3RvcjxQYWlyPiwgc3RkOjpncmVhdGVyPFBhaXI+PiBwcTsKICBzdGQ6OnByaW9yaXR5X3F1ZXVlPFBhaXI+IHBxOwogIGRpc3Rbc10gPSAwOwogIHBxLmVtcGxhY2UoMCwgcyk7CiAgd2hpbGUgKCFwcS5lbXB0eSgpKSB7CiAgICBhdXRvIFtkLCB2XSA9IHBxLnRvcCgpOwogICAgcHEucG9wKCk7CiAgICBpZiAoZGlzdFt2XSA8IGQpIGNvbnRpbnVlOwogICAgZm9yIChpbnQgaWQgOiBnLmRhdGFfW3ZdKSB7CiAgICAgIGNvbnN0IGF1dG8mIFtmcm9tLCB0bywgY29zdF0gPSBnLmVkZ2VzX1tpZF07CiAgICAgIGludCBueHQgPSBmcm9tIF4gdG8gXiB2OwogICAgICBpZiAoZGlzdFtueHRdID4gZGlzdFt2XSArIGNvc3QpIHsKICAgICAgICBkaXN0W254dF0gPSBkaXN0W3ZdICsgY29zdDsKICAgICAgICBwcS5lbXBsYWNlKGRpc3Rbbnh0XSwgbnh0KTsKICAgICAgfQogICAgfQogIH0KICByZXR1cm4gZGlzdDsKfQoKZGlncmFwaDxpbnQ+IGdyaWRfdG9fZGlncmFwaChjb25zdCBzdGQ6OnZlY3RvcjxzdGQ6OnN0cmluZz4mIHN2KSB7CiAgaW50IGggPSBzdi5zaXplKCksIHcgPSBzdlswXS5zaXplKCk7CiAgZGlncmFwaDxpbnQ+IGcoaCAqIHcpOwogIGNvbnN0ZXhwciBpbnQgZHhbNF0gPSB7MSwgMCwgLTEsIDB9LCBkeVs0XSA9IHswLCAxLCAwLCAtMX07CiAgYXV0byBPdXQgPSBbJl0oaW50IHgsIGludCB5KSB7IHJldHVybiAoeCA8IDAgfHwgeCA+PSBoIHx8IHkgPCAwIHx8IHkgPj0gdyk7IH07CiAgYXV0byBDb21wcmVzcyA9IFsmXShpbnQgeCwgaW50IHkpIHsgcmV0dXJuIHggKiB3ICsgeTsgfTsKICBmb3IgKGludCBpID0gMDsgaSA8IGg7ICsraSkgewogICAgZm9yIChpbnQgaiA9IDA7IGogPCB3OyArK2opIHsKICAgICAgZm9yIChpbnQgayA9IDA7IGsgPCA0OyArK2spIHsKICAgICAgICBpbnQgbnggPSBpICsgZHhba10sIG55ID0gaiArIGR5W2tdOwogICAgICAgIGlmIChPdXQobngsIG55KSkgY29udGludWU7CiAgICAgICAgaWYgKHN2W2ldW2pdID09ICcuJyAmJiBzdltueF1bbnldID09ICcuJykgewogICAgICAgICAgZy5hZGQoQ29tcHJlc3MoaSwgaiksIENvbXByZXNzKG54LCBueSksIDApOwogICAgICAgIH0KICAgICAgfQogICAgICBmb3IgKGludCBrID0gLTI7IGsgPD0gMjsgKytrKSB7CiAgICAgICAgZm9yIChpbnQgbCA9IC0yOyBsIDw9IDI7ICsrbCkgewogICAgICAgICAgaW50IG54ID0gaSArIGssIG55ID0gaiArIGw7CiAgICAgICAgICBpZiAoT3V0KG54LCBueSkpIGNvbnRpbnVlOwogICAgICAgICAgaWYgKGFicyhrKSArIGFicyhsKSA9PSAxKSBjb250aW51ZTsKICAgICAgICAgIGlmIChzdltpXVtqXSA9PSAnLicgJiYgc3ZbbnhdW255XSA9PSAnLicpIHsKICAgICAgICAgICAgZy5hZGQoQ29tcHJlc3MoaSwgaiksIENvbXByZXNzKG54LCBueSksIDEpOwogICAgICAgICAgfQogICAgICAgIH0KICAgICAgfQogICAgfQogIH0KICByZXR1cm4gZzsKfQoKCmludCBtYWluKCkgewogIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogIGNpbi50aWUobnVsbHB0cik7CgogIGludCBoLCB3OyBjaW4gPj4gaCA+PiB3OwogIGludCBjaCwgY3c7IGNpbiA+PiBjaCA+PiBjdzsgLS1jaDsgLS1jdzsKICBpbnQgZGgsIGR3OyBjaW4gPj4gZGggPj4gZHc7ICAtLWRoOyAtLWR3OwogIHZlY3RvcjxzdHJpbmc+IHMoaCk7IGNpbiA+PiBzOwogIGRpZ3JhcGg8aW50PiBnID0gZ3JpZF90b19kaWdyYXBoKHMpOwogCiAgdmVjdG9yIGRpc3QgPSBkaWprc3RyYShnLCBjaCAqIHcgKyBjdyk7CiAKICBpbnQgYW5zID0gZGlzdFtkaCAqIHcgKyBkd107CiAgaWYgKGFucyA9PSBudW1lcmljX2xpbWl0czxpbnQ+OjptYXgoKSkgYW5zID0gLTE7CiAgY291dCA8PCBhbnMgPDwgZW5kbDsKCiAgcmV0dXJuIDA7Cn0KIiIiCgp3aXRoIG9wZW4oJ3NvbC5jcHAnLCAndycpIGFzIGY6CiAgICBmLndyaXRlKGNvZGUpCgpzdWJwcm9jZXNzLlBvcGVuKFsnZysrJywgJy1zdGQ9YysrMTcnLCAnLU8yJywgJ3NvbC5jcHAnXSkuY29tbXVuaWNhdGUoKQpzdWJwcm9jZXNzLlBvcGVuKFsnLi9hLm91dCddLCBzdGRpbj1zeXMuc3RkaW4sIHN0ZG91dD1zeXMuc3Rkb3V0KS5jb21tdW5pY2F0ZSgp'))