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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
# ---------標準入力時--------------
h,w=map(int,readline().split())
ch, cw=map(int,readline().split())
dh, dw=map(int,readline().split())
m=list(map(lambda x: list(x.decode()), readlines()))
# ---------標準入力時--------------
 
ad = [(-1,0), (0,-1), (1,0), (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)]
 
def bfs6():
    '''
    bfs5から少し変更
    あるマス(i,j)から上(i-1,j)下(i+1,j) もしくは 左(i,j-1)右(i,j+1)に歩いて行ける時、
    (i,j)からwarpで行ける範囲は、その上下もしくは左右でカバーされるので、(i,jは考えなくていい)
    これをwarpを考えるときに処理する
    '''
    que1=[]
    que2=[] # queueというよりはメモリ
    m[ch][cw]=str(0)
    que1.append((ch,cw))
 
    while que1!=[]:
        l1=len(que1)
        r1=0 # que1における使用済みindex
 
        # que1の要素(座標)から歩いていけるマス
        while r1<l1:
            i, j=que1[r1]
            r1+=1
            for si, sj in ad:
                if m[i+si][j+sj]=='.': 
                    m[i+si][j+sj]=m[i][j]
                    que1.append((i+si, j+sj))
                    l1+=1
 
        # 歩いていけないマス
        for i,j in que1:
            if (m[i][j]==m[i-1][j] and m[i][j]==m[i+1][j]) or (m[i][j]==m[i][j-1] and m[i][j]==m[i][j+1]):
                continue
            for si, sj in warp:
                if m[i+si][j+sj]=='.':
                    m[i+si][j+sj]=str(int(m[i][j])+1)
                    que2.append((i+si, j+sj))
 
        que1=que2
        que2=[]
###---------------------------------------
 
for i in range(h):
    m[i] = ['#']*2 + m[i] + ['#']*2
    
m = [['#']*(w+4)]*2 + m + [['#']*(w+4)]*2
ch+=1; cw+=1; dh+=1; dw+=1
 
bfs6()
 
if m[dh][dw] == '.':
    print(-1)
else:
    print(m[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
si, sj = map(int, input().split())
gi, gj = map(int, input().split())
si, sj, gi, gj = si - 1, sj - 1, gi - 1, gj - 1
C = [input() for i in range(H)]

dist = [[10 ** 9] * W for _ in range(H)]
dist[si][sj] = 0

que = deque()
que.append((si, sj))

while que:
    i, j = que.popleft()
    d = dist[i][j]
    if i == gi and j == gj:
        break
    for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
        if not (0 <= ni < H and 0 <= nj < W):
            continue
        if d < dist[ni][nj] and C[ni][nj] == ".":
            dist[ni][nj] = d
            que.appendleft((ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            ni, nj = i + di, j + dj
            if not (0 <= ni < H and 0 <= nj < W):
                continue
            if d + 1 < dist[ni][nj] and C[ni][nj] == ".":
                dist[ni][nj] = d + 1
                que.append((ni, nj))

ans = dist[gi][gj]
print(ans if ans != 10 ** 9 else -1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

H,W=map(int,input().split())
si,sj=[int(x)-1 for x in input().split()]
ti,tj=[int(x)-1 for x in input().split()]
A=[[*next(sys.stdin)] for _ in range(H)]

N=-1
for i in range(H):
    for j in range(W):
        if A[i][j]!='.':
            continue
        N+=1
        stk=[(i,j)]
        while stk:
            ii,jj=stk.pop()
            A[ii][jj]=N
            for ni,nj in (ii-1,jj),(ii,jj+1),(ii+1,jj),(ii,jj-1):
                if not (0<=ni<H and 0<=nj<W):
                    continue
                if A[ni][nj]!='.':
                    continue
                stk.append((ni,nj))

s=t=-1
dirs=[-2,-1,0,1,2]
adj=[{*()} for _ in range(N+1)]
for i in range(H):
    for j in range(W):
        u=A[i][j]
        if u=='#':
            continue
        if i==si and j==sj:
            s=u
        elif i==ti and j==tj:
            t=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=A[ni][nj]
                if v=='#':
                    continue
                if u!=v:
                    adj[u].add(v)
                    adj[v].add(u)

que=deque()                
que.append(s)
vis={s}
m=-1
ok=False
while que:
    m+=1
    for _ in range(len(que)):
        u=que.popleft()
        if u==t:
            ok=True
            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)

Submission status: Accepted

Solution code:
from collections import deque

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = []
for _ in range(H):
    s = input()
    S.append(s)

# 上下左右に移動できるところは移動する
# 移動してもたどり着けない場合はワープをそれぞれのますで実行し、まだ到達していない箇所にいく
# これを繰り返す

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

wx = [-2, -1, 0, 1, 2]
wy = [-2, -1, 0, 1, 2]
dp = [[-1] * W for _ in range(H)]
dp[Ch - 1][Cw - 1] = 0


def bfs(x, y, cost, dp, d):
    while len(d) > 0:
        p = d.popleft()
        dw.append(p)
        for i in range(4):
            if p[0] + dx[i] >= 0 and p[0] + dx[i] < W and p[1] + \
                    dy[i] >= 0 and p[1] + dy[i] < H:
                if S[p[1] + dy[i]][p[0] + dx[i]
                                   ] == '.' and dp[p[1] + dy[i]][p[0] + dx[i]] == -1:
                    d.append([p[0] + dx[i], p[1] + dy[i]])
                    dw.append([p[0] + dx[i], p[1] + dy[i]])
                    dp[p[1] + dy[i]][p[0] + dx[i]] = cost

    return cost, dp


ds = deque()
ds.append([Cw - 1, Ch - 1])
c = 0
while True:
    dw = deque()
    cost, dp = bfs(Cw - 1, Ch - 1, c, dp, ds)
    check = False
    while len(dw) > 0:
        p = dw.popleft()
        for m in range(5):
            for n in range(5):
                if p[0] + wx[m] >= 0 and p[0] + wx[m] < W and p[1] + \
                        wy[n] >= 0 and p[1] + wy[n] < H:
                    if S[p[1] + wy[n]][p[0] + wx[m]
                                       ] == '.' and dp[p[1] + wy[n]][p[0] + wx[m]] == -1:
                        ds.append([p[0] + wx[m], p[1] + wy[n]])
                        dp[p[1] + wy[n]][p[0] + wx[m]] = cost + 1
                        check = True
    if check:
        c += 1
    else:
        break

print(dp[Dh - 1][Dw - 1])

Submission status: Accepted

Solution code:
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())
    # 迷路の四方を##で囲む。
    # 移動で枠外にでてしまってindexがないことを阻止するための
    # if文を回避
    maze = ['#' * (w+4)]
    maze.append('#' * (w+4))
    for _ in range(h):
        maze.append('##' + input()[:-1] + '##')
    maze.append('#' * (w+4))
    maze.append('#' * (w+4))
    visited = [[-1] * (w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if maze[i][j] == '#':
                visited[i][j] = -2
    # この条件ではindexを+1しないとダメ
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    visited[ch][cw] = 0
    walk = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    telepo = [[i,j] for i in range(-2, 3) for j in range(-2, 3)]

    q_walk = deque([[ch, cw]])
    q_telepo = deque([])
    while q_walk:
        yw, xw = q_walk.popleft()
        # 行った場所を管理
        q_telepo.append([yw, xw])
        for i, j in walk:
            ny, nx = yw + i, xw + j
            # if ny < 0 or h <= ny or nx < 0 or w <= nx:
            #     continue
            if visited[ny][nx] == -1:
                # 行ったことあれば0にしていく
                visited[ny][nx] = visited[yw][xw]
                q_walk.append([ny, nx])
        # 歩ける場所なくなったらワープ
        if len(q_walk) == 0:
            while q_telepo:
                yt, xt = q_telepo.popleft()
                for i, j in telepo:
                    my, mx = yt + i, xt + j
                    # if my < 0 or h <= my or mx < 0 or w <= mx:
                    #     continue
                    # 次がまだ行ったことないところだったら、今までの値に+1
                    # つまり、テレポートしないといけない場所
                    if visited[my][mx] == -1:
                        visited[my][mx] = visited[yt][xt] + 1
                        q_walk.append([my, mx])
    print(visited[dh][dw])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

INF = int(1e10)

dh = [0, 0, 1, -1]
dw = [1, -1, 0, 0]

def main():
    from builtins import int, map
    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 = [list(input()) for _ in range(H)]

    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0
    queue = deque([(Ch, Cw)])

    while queue:
        (h, w) = queue.popleft()

        for i in range(4):
            dhi, dwi = dh[i], dw[i]
            nh, nw = h + dhi, w + dwi
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if dist[h][w] < dist[nh][nw]:
                    dist[nh][nw] = dist[h][w]
                    queue.appendleft((nh, nw))
        
        # 5x5-grid
        for ddh in range(-2, 3):
            for ddw in range(-2, 3):
                if abs(ddh) + abs(ddw) <= 1:
                    continue
                nh, nw = h + ddh, w + ddw
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if dist[nh][nw] > dist[h][w] + 1:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append((nh, nw))

    if dist[Dh][Dw] == INF:
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
INF = int(1e10)

def main():
    from builtins import int, map
    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)]

    # dist = defaultdict(lambda: float("inf"))
    dist = [[float("inf")] * W for _ in range(H)]
    queue = deque([(Ch, Cw, 0)])

    while queue:
        (h, w, d) = queue.popleft()

        if dist[h][w] == float("inf") or dist[h][w] > d:
            dist[h][w] = d
            
            # 5x5-grid
            for ddh in range(-2, 3):
                for ddw in range(-2, 3):
                    nh, nw = h + ddh, w + ddw
                    if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                        # cost-0 move
                        if abs(ddh) + abs(ddw) <= 1:
                            queue.appendleft((nh, nw, d))
                        # cost-1 move
                        else:
                            queue.append((nh, nw, d + 1))

    if dist[Dh][Dw] == float("inf"):
        print(-1)
    else:
        print(dist[Dh][Dw])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

@njit(cache=True)
def pos(W,h,w):
    return h * W + w


# @njit(cache=True)
def solve(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]



def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = solve(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,i8,i8,i8,i8,b1[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

Solution code:
def resolve():
    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
    maze = []
    for _ in range(h):
        maze.append(list(input()))

    final = [[10**9] * w for _ in range(h)]
    from collections import deque
    nxt = [[ch, cw]]
    nxt = deque(nxt)
    final[ch][cw] = 0

    while nxt:
        nowh, noww = nxt.popleft()
        for i, j in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
            if 0 <= nowh + i < h and 0 <= noww + j < w and maze[nowh + i][noww + j] == ".":
                if final[nowh + i][noww + j] > final[nowh][noww]:
                    final[nowh + i][noww + j] = final[nowh][noww]
                    nxt.appendleft([nowh + i, noww + j])


        for i in range(max(0, nowh - 2), min(h, nowh + 3)):
            for j in range(max(0, noww - 2), min(w, noww + 3)):
                if maze[i][j] == ".":
                    if final[i][j] > final[nowh][noww] + 1:
                        final[i][j] = final[nowh][noww] + 1
                        nxt.append([i, j])
    if final[dh][dw] == 10**9:
        print(-1)
    else:
        print(final[dh][dw])

resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

from collections import deque

q = 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

ban_list = [[-999 for j in range(w)] for i in range(h)]


for i in range(h):
  # 文字列の入力
  s = input()
  for j in range(len(s)):
    ban_list[i][j] = s[j]


ban_list[ch][cw] = 0

cost = 0
ph = ch
pw = cw

q.append([ph, pw])

# 上右下左
ido_h = [-1, 0, 1, 0]
ido_w = [0, 1, 0, -1]

while q:
  ph, pw = q.popleft()
  cost = ban_list[ph][pw]

  for i in range(4):
    nh = ph + ido_h[i]
    nw = pw + ido_w[i]

    if nh < 0 or h -1 < nh or nw < 0 or w -1 < nw:
      continue
    val = ban_list[nh][nw]
    if val == "#" or val == cost:
      continue
    if val == "." or cost < val:
      ban_list[nh][nw] = cost
      q.appendleft([nh, nw])



  # # 上
  # if ph == 0:
  #   pass
  # else:
  #   if ban_list[ph-1][pw] != "#" and ban_list[ph-1][pw] != cost:
  #     if ban_list[ph-1][pw] == "." or cost < ban_list[ph-1][pw]:
  #       ban_list[ph-1][pw] = cost
  #       # appendだとrandom_02.txtがWAになる
  #       q.appendleft([ph-1, pw])
  #   else:
  #     pass

  # # 右
  # if pw == w -1:
  #   pass
  # else:
  #   if ban_list[ph][pw + 1] != "#" and ban_list[ph][pw + 1] != cost:
  #     if ban_list[ph][pw + 1] == "." or cost < ban_list[ph][pw + 1]:
  #       ban_list[ph][pw + 1] = cost
  #       q.appendleft([ph, pw+1])
  #   else:
  #     pass

  # # 下
  # if ph == h -1:
  #   pass
  # else:
  #   if ban_list[ph+1][pw] != "#" and ban_list[ph+1][pw] != cost:
  #     if ban_list[ph+1][pw] == "." or cost < ban_list[ph+1][pw]:
  #       ban_list[ph+1][pw] = cost
  #       q.appendleft([ph+1, pw])
  #   else:
  #     pass

  # # 左
  # if pw == 0:
  #   pass
  # else:
  #   if ban_list[ph][pw - 1] != "#" and ban_list[ph][pw - 1] != cost:
  #     if ban_list[ph][pw - 1] == "." or cost < ban_list[ph][pw - 1]:
  #       ban_list[ph][pw - 1] = cost
  #       q.appendleft([ph, pw-1])
  #   else:
  #     pass


  # ジャンプ--------------
  for i in range(-2, 3):
    if (ph + i < 0) or (h - 1 < ph + i):
      continue

    for j in range(-2, 3):
      if (pw + j < 0) or (w - 1 < pw + j) or (i==0 and j == 0) or (i==0 and j == -1) or (i==0 and j == 1) or (i==-1 and j == 0) or (i==1 and j == 0):
        continue
      if ban_list[ph + i][pw + j] == ".":
        ban_list[ph + i][pw + j] = cost + 1
        q.append([ph + i, pw + j])


result = ban_list[dh][dw]
if result == ".":
  result = -1


print(result)

Submission status: Accepted

Solution code:
from numba import njit
import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

@njit(cache=True)
def pos(W,h,w):
    return h * W + w


# @njit(cache=True)
def solve(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]



def main():
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = solve(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    cc.export('pos', '(i8,i8,i8,)')(pos)
    cc.export('solve', '(i8,i8,i8,i8,i8,i8,b1[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    try:
        from my_module import solve
        from my_module import pos
    except:
        cc_export()
        exit()

    main()

Submission status: Accepted

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or d < dst[nh][nw]:
            dq.appendleft((nh, nw, d))
            dst[nh][nw] = d

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d + 1))
        dst[nh][nw] = d + 1

print(dst[eh][ew])

Submission status: Accepted

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]
dst[sh][sw] = 0

from collections import deque
dq = deque([(sh, sw)])
while dq:
    h, w = dq.popleft()

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1 or dst[h][w] < dst[nh][nw]:
            dst[nh][nw] = dst[h][w]
            dq.appendleft((nh, nw))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] == -1:
            dst[nh][nw] = dst[h][w] + 1
        elif dst[h][w] + 1 < dst[nh][nw]:
            dst[nh][nw] = min(dst[nh][nw], dst[h][w] + 1)
        else: continue
        dq.append((nh, nw))

print(dst[eh][ew])

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
import heapq
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=1<<18

from numba import njit, b1, i4, i8, f8
@njit((i8,i8,i8), cache=True)
# @njit(cache=True)
def pos(W,h,w):
    return h * W + w

@njit((i8,i8,i8,i8,i8,i8,b1[:]), cache=True)
# @njit(cache=True)
def main(H,W,Ch,Cw,Dh,Dw,G):
    Ch-=1
    Cw-=1
    Dh-=1
    Dw-=1

    s = (Ch,Cw)
    t = (Dh,Dw)

    hq = [(0,s)]
    heapq.heapify(hq)
    
    dist = [INF] *(H*W) # sからxでの最短距離
    dist[pos(W,*s)] = 0
    while hq: 
        d,x = heapq.heappop(hq) # sからxまでの最短経路を探索する
        if dist[pos(W,*x)] < d: continue

        h,w = x
        normal = set([(h-1,w),(h+1,w),(h,w+1),(h,w-1)])
        for dh in range(-2,3):
            for dw in range(-2,3):
                new_h,new_w = h+dh,w+dw
                e = (new_h,new_w)
                cost = 1

                if dh == 0 and dw == 0: continue
                if not (0<=new_h<H and 0<=new_w<W): continue
                if G[pos(W,*e)] == 1:  continue
                if e in normal:
                    cost -= 1
                
                if dist[pos(W,*e)] > dist[pos(W,*x)] + cost:
                    dist[pos(W,*e)] = dist[pos(W,*x)] + cost
                    heapq.heappush(hq,(dist[pos(W,*e)],e))

    # print(dist)
    if dist[pos(W,*t)] == INF: 
        dist[pos(W,*t)] = -1
        
    return dist[pos(W,*t)]


if __name__ == "__main__":
    H,W=mi()
    Ch,Cw=mi()
    Dh,Dw=mi()

    G = [0] * H*W
    for i in range(H):
        g = []
        for j,s in enumerate(list(input())):
            G[i*W+j] = s == "#"

    ans = main(H,W,Ch,Cw,Dh,Dw,np.array(G))
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque


def main():

    def bfs(h1, w1, dp):
        """
        -1 - unsearched
        -2 - candidate for warp
        -3 - wall '#'
        """
        queue = deque()
        queue_warp = deque()
        queue.append([h1, w1])
        now = 0

        while queue:
            h1, w1 = queue.popleft()
            fl_up = False
            fl_left = False
            fl_down = False
            fl_right = False

            if h1 > 0:
                if dp[h1-1][w1] == -1 or dp[h1-1][w1] == -2:
                    if m[h1-1][w1] == '.':
                        dp[h1-1][w1] = now
                        queue.append([h1-1, w1])
                    else:
                        dp[h1-1][w1] = -3
                if dp[h1-1][w1] == -3:
                    fl_up = True
                    if h1 > 1:
                        if dp[h1-2][w1] == -1:
                            if m[h1-2][w1] == '.':
                                dp[h1-2][w1] = -2
                                queue_warp.append([h1-2, w1])
                            else:
                                dp[h1-2][w1] = -3
            
            if w1 > 0:
                if dp[h1][w1-1] == -1  or dp[h1][w1-1] == -2:
                    if m[h1][w1-1] == '.':
                        dp[h1][w1-1] = now
                        queue.append([h1, w1-1])
                    else:
                        dp[h1][w1-1] = -3
                if dp[h1][w1-1] == -3:
                    fl_left = True
                    if w1 > 1:
                        if dp[h1][w1-2] == -1:
                            if m[h1][w1-2] == '.':
                                dp[h1][w1-2] = -2
                                queue_warp.append([h1, w1-2])
                            else:
                                dp[h1][w1-2] = -3
            
            if h1 < h - 1:
                if dp[h1+1][w1] == -1 or dp[h1+1][w1] == -2:
                    if m[h1+1][w1] == '.':
                        dp[h1+1][w1] = now
                        queue.append([h1+1, w1])
                    else:
                        dp[h1+1][w1] = -3
                if dp[h1+1][w1] == -3:
                    fl_down = True
                    if h1 < h - 2:
                        if dp[h1+2][w1] == -1:
                            if m[h1+2][w1] == '.':
                                dp[h1+2][w1] = -2
                                queue_warp.append([h1+2, w1])
                            else:
                                dp[h1+2][w1] = -3
            
            if w1 < w - 1:
                if dp[h1][w1+1] == -1 or dp[h1][w1+1] == -2:
                    if m[h1][w1+1] == '.':
                        dp[h1][w1+1] = now
                        queue.append([h1, w1+1])
                    else:
                        dp[h1][w1+1] = -3
                if dp[h1][w1+1] == -3:
                    fl_right = True
                    if w1 < w - 2:
                        if dp[h1][w1+2] == -1:
                            if m[h1][w1+2] == '.':
                                dp[h1][w1+2] = -2
                                queue_warp.append([h1, w1+2])
                            else:
                                dp[h1][w1+2] = -3
            
            if fl_up and fl_left:
                for i in range(max(0, h1-2), h1):
                    for j in range(max(0, w1-2), w1):
                        if dp[i][j] == -1:
                            if m[i][j] == '.':
                                dp[i][j] = -2
                                queue_warp.append([i, j])
                            else:
                                dp[i][j] = -3

            if fl_left and fl_down:
                for i in range(h1+1, min(h, h1+3)):
                    for j in range(max(0, w1-2), w1):
                        if dp[i][j] == -1:
                            if m[i][j] == '.':
                                dp[i][j] = -2
                                queue_warp.append([i, j])
                            else:
                                dp[i][j] = -3
            
            if fl_down and fl_right:
                for i in range(h1+1, min(h, h1+3)):
                    for j in range(w1+1, min(w, w1+3)):
                        if dp[i][j] == -1:
                            if m[i][j] == '.':
                                dp[i][j] = -2
                                queue_warp.append([i, j])
                            else:
                                dp[i][j] = -3

            if fl_right and fl_up:
                for i in range(max(0, h1-2), h1):
                    for j in range(w1+1, min(w, w1+3)):
                        if dp[i][j] == -1:
                            if m[i][j] == '.':
                                dp[i][j] = -2
                                queue_warp.append([i, j])
                            else:
                                dp[i][j] = -3

            if not queue:
                now += 1
                while queue_warp:
                    h1, w1 = queue_warp.popleft()
                    if dp[h1][w1] == -2:
                        dp[h1][w1] = now
                        queue.append([h1, w1])
            
            if dp[dh-1][dw-1] >= 0:
                return dp[dh-1][dw-1]
        
        return dp[dh-1][dw-1]

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

    m = [[] for i in range(h)]
    dp = [[-1]*w for i in range(h)]
    dp[ch-1][cw-1] = 0
    
    for i in range(h):
        m[i] = input()
    
    ans = bfs(ch-1, cw-1, dp)

    print(ans)

main()

Submission status: Accepted

Solution code:
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 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)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

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

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if 0 <= h < H and 0 <= w < W and dst[h][w] < 0 and S[h][w] != '#':
        dst[h][w] = d
        for dh, dw in dhw[:4]: dq.appendleft((h + dh, w + dw, d))
        for dh, dw in dhw[4:]: dq.append((h + dh, w + dw, d+1))

print(dst[eh][ew])