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:
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 i in range(H)]
di=[[-1 for _ in range(W)] for _ in range(H)]
adj=[]
for i in range(-1,2):
  for j in range(-1,2):
    if i==0 or j==0:
      adj.append((i,j))
warp=[]
for i in range(-2,3):
  for j in range(-2,3):
    if (i,j) not  in adj:
      warp.append((i,j))
adj.remove((0,0))
from collections import deque
dq=deque([(CH,CW,0)])
while dq:
  h,w,d=dq.popleft()
  if 0<=h<H and 0<=w<W and di[h][w]<0 and maze[h][w]=='.':
    di[h][w]=d
  else:
    continue
  for i in range(len(adj)):
    dq.appendleft((h+adj[i][0],w+adj[i][1],d))
  for i in range(len(warp)):
    dq.append((h+warp[i][0],w+warp[i][1],d+1))
print(di[DH][DW])

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
def Dijkstra(graph,s):
    INF = 10**9
    dist = [INF]*len(graph)
    dist[s] = 0
    #nn_node = [-1]*len(graph) #nearest neighborのnode
    #checked=[False]*len(graph) #dist 確定
    heap = [(0,s)]
    while heap:
        cost,node = hq.heappop(heap)
        if cost>dist[node]:continue
        for weight,nex in graph[node]:
            d = cost+weight
            if d<dist[nex]:
                dist[nex] = d
                #nn_node[nex] = node
                hq.heappush(heap,(d,nex))
    for i in range(len(dist)):
        if dist[i] == INF:
            dist[i] = -1
    return dist #,nn_node

dyx = [(-1,0),(1,0),(0,1),(0,-1)]
INF=10**9
H,W = ma()
ch,cw = ma()
ch-=1;cw-=1
dh,dw=ma()
dh-=1;dw-=1
area= []
for h in range(H):
    area.append(input())

group = [[-1]*W for h in range(H)]
def BFS(sy,sx,idx):
    que = collections.deque()
    que.append((sy,sx))
    group[sy][sx]=idx
    while que:
        h,w = que.popleft()
        for dy,dx in dyx:
            if (0<=h+dy<H )and (0<=w+dx<W):
                if area[h+dy][w+dx] =="." and group[h+dy][w+dx] ==-1:
                    group[h+dy][w+dx] = idx
                    que.append((h+dy,w+dx))


idx = 0
for h in range(H):
    for w in range(W):
        if area[h][w] =="." and group[h][w] ==-1:
            BFS(h,w,idx)
            idx+=1
            #print(group)

tree = [set() for _ in range(idx)]
dyx2 = [(i,j) for i in range(-2,3) for j in range(-2,3)]
dyx2.remove((0,0))

for h in range(H):
    for w in range(W):
        if area[h][w]=="#":
            continue
        g = group[h][w]
        for dy,dx in dyx2:
            if (0<=h+dy<H )and (0<=w+dx<W) and (area[h+dy][w+dx]=="."):
                if (g !=group[h+dy][w+dx]):
                    tree[g].add((1,group[h+dy][w+dx]))
                    tree[group[h+dy][w+dx]].add((1,g))
dist = Dijkstra(tree,group[ch][cw])

#print(group)
#print(tree)
#print(dist)
print(dist[group[dh][dw]])

Submission status: Accepted

Solution code:
from collections import deque
H,W = list(map(int,input().split()))
start = list(map(lambda x:int(x)-1,input().split()))
goal = list(map(lambda x:int(x)-1,input().split()))
A = [input() for _ in range(H)]
visited = [[0]*W for _ in range(H)]
B = deque([[start[0],start[1],0]])
warp = []
for i in range(-2,3):
    for j in range(-2,3):
            warp.append([i,j])

num = -1

while B:
    y,x,n = B.popleft()
    if visited[y][x] == 1:continue
    if [y,x] == goal:
        num = n
        break
    visited[y][x] = 1
    for dy,dx in [[1,0],[0,1],[-1,0],[0,-1]]:
        if (y+dy<0)|(x+dx<0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.appendleft([y+dy,x+dx,n])
    for dy,dx in warp:
        if (y+dy<0)|(x+dx<0)|(y+dy>=H)|(x+dx>=W):continue
        if (A[y+dy][x+dx]==".")&(visited[y+dy][x+dx]==0):
            B.append([y+dy,x+dx,n+1])

print(num)

Submission status: Accepted

Solution code:
h, w = map(int,input().split())
si, sj = map(int,input().split())
gi, gj = map(int,input().split())
S = [input() for i in range(h)]
n = h * w

si-=1
sj-=1
gi-=1
gj-=1

# M = [[] for i in range(h*w)]

A = [[-1,0],[1,0],[0,1],[0,-1]]
B = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i!=0 or j!=0) and (not ([i, j] in A)):
            B.append([i, j])

# for i in range(h):
#     for j in range(w):
#         if S[i][j] == ".":
#             for a in A:
#                 ai = i + a[i]
#                 aj = j + a[j]
#                 if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
#                     M[i*w+j].append([ai*w+aj, 0])
#             for a in B:
#                 ai = i + a[i]
#                 aj = j + a[j]
#                 if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
#                     M[i*w+j].append([ai*w+aj, 1])

from collections import deque
D = deque()

V = [0] * n
DI = [float("inf")] * n
s = si*w+sj
g = gi*w+gj
DI[s] = 0

D.append([s, 0])

while len(D) > 0:
    d = D.popleft()
    x = d[0]
    we = d[1]
    if V[x] == 0:
        V[x] = 1
        DI[x] = we
        i = x//w
        j = x%w
        for a in A:
            ai = i + a[0]
            aj = j + a[1]
            if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                D.appendleft([ai*w+aj, we])
        for a in B:
            ai = i + a[0]
            aj = j + a[1]
            if 0 <= ai < h and 0 <= aj < w and S[ai][aj] == ".":
                D.append([ai*w+aj, we+1])

# print(DI)
# print(DI[g])
ans = DI[g]
if DI[g] == float("inf"):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
def l():
    return [int(x) for x in input().split()]
def main():
    H,W=l()
    ch,cw=l()
    dh,dw=l()
    ch-=1
    cw-=1
    dw-=1
    dh-=1
    s=[[-2 if x=='#' else -1 for x in list(input())] for _ in range(H)]
    pad1=[-2,-2]
    pad2=[[-2]*(W+4)]*2
    s=pad2+[pad1+x+pad1 for x in s]+pad2
    move1=[(-1,0),(1,0),(0,-1),(0,1)]
    move2=list(set([(i,j) for i in range(-2,3) for j in range(-2,3)])-set(move1)-set([(0,0)]))
    q1=[(0,ch+2,cw+2)]
    q2=[]
    s[ch+2][cw+2]=0
    def mark(c,h,w):
        if -2<=h<H+2 and -2<=w<W+2 and s[h][w]==-1:
        #if s[h][w]==-1:
            s[h][w]=c
            q1.append((c,h,w))
    while q1:
        #print(q1)
        c,h,w=q1.pop()
        for i,j in move1:
            mark(c,h+i,w+j)
        q2.append((c+1,h,w))
        if not q1:
            for c,h,w in q2:
                for i,j in move2:
                    mark(c,h+i,w+j)
            q2=[]
    ans=s[dh+2][dw+2]
    if ans>=0:
        print(ans)
    else:
        print(-1)
main()

Submission status: Accepted

Solution code:
import copy
import sys
from collections import deque
H, W = map(int,input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
check_visited = [[False] * W for _ in range(H)]
dq = deque([[0, C[0], C[1]]])
while dq:
   d, i, j = dq.popleft()
   if [i, j] == D:
      print(d)
      exit()
   if check_visited[i][j]:
      continue
   check_visited[i][j] = True
   for move_h, move_w in [[-1,0], [1,0], [0,-1], [0,1]]:
      new_i = i + move_h
      new_j = j + move_w
      if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
         dq.appendleft([d, new_i, new_j])
   for move_h in range(-2, 3):
      for move_w in range(-2, 3):
         if [move_h, move_w] == [0, 0]:
            continue
         new_i = i + move_h
         new_j = j + move_w
         if 0 <= new_i <= H-1 and 0 <= new_j <= W-1 and S[new_i][new_j] == '.' and (not check_visited[new_i][new_j]) :
            dq.append([d+1, new_i, new_j])
print(-1)
#コードに関しては, sotanishyさんのコードを参考にした.
#writing this, I referred to Mr.sotanishy's submitted code.

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
C=list(map(int,input().split()))
D=list(map(int,input().split()))
S=[]
ischecked=[[-1]*W for _ in range(H)]
for _ in range(H):
    s=input()
    S.append(s)
walkq=deque()
walkq.append([C[0]-1,C[1]-1])
warpq=deque()

def Walk(h,w):
    if 0<=h<H and 0<=w<W:
        if ischecked[h][w]==-1 and S[h][w]==".":
            walkq.append([h,w])
def Warp(h,w,warp):
    if 0<=h<H and 0<=w<W:
        if ischecked[h][w]==-1 and S[h][w]==".":
            warpq.append([h,w,warp+1])

warp=0
ans=-1
while 1:
    if len(walkq)!=0:
        now=walkq.popleft()
    elif len(warpq)!=0:
        now=warpq.popleft()
        warp=now[2]
    else:
        break
    h=now[0]
    w=now[1]
    if ischecked[h][w]==-1:
        ischecked[h][w]=warp
        Walk(h-1,w)
        Walk(h+1,w)
        Walk(h,w-1)
        Walk(h,w+1)
        for i in range(5):
            for j in range(5):
                Warp(h-2+i,w-2+j,warp)
    if h==D[0]-1 and w==D[1]-1:
        ans=ischecked[h][w]
        break
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                # moveB_q.append([nx, ny])

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])


    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])
                

    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

h,w = mp()
ch, cw = mp()
dh,dw = mp()
ch += 1
cw += 1
dh += 1
dw += 1
grid = []
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))
ans_grid = []
for i in range(h):
    u = ["#", "#"]
    a = list(input())
    for j in range(w):
        u.append(a[j])
    u.append("#")
    u.append("#")
    grid.append(u)
grid.append(["#"]*(w+4))
grid.append(["#"]*(w+4))

for i in range(h+4):
    ans_grid.append([int(1e6+2)]*(w+4))
# print(grid)
# print(ans_grid)

from collections import deque
def bfs(x,y):
    q = deque([])
    used = set()
    q.append((x,y))
    used.add((x,y))
    ans_grid[x][y] = 0
    while q:
        here = q.popleft()
        move = [(here[0]-1, here[1]),
                (here[0], here[1]-1),
                (here[0], here[1]+1),
                (here[0]+1, here[1])]
        warp = [(here[0]-2, here[1]-2), (here[0]-2, here[1]-1), (here[0]-2, here[1]), (here[0]-2, here[1]+1), (here[0]-2, here[1]+2),
                (here[0]-1, here[1]-2), (here[0]-1, here[1]-1), (here[0]-1, here[1]+1), (here[0]-1, here[1]+2),
                (here[0], here[1]-2), (here[0], here[1]+2),
                (here[0]+1, here[1]-2), (here[0]+1, here[1]-1), (here[0]+1, here[1]+1), (here[0]+1, here[1]+2),
                (here[0]+2, here[1]-2), (here[0]+2, here[1]-1), (here[0]+2, here[1]), (here[0]+2, here[1]+1), (here[0]+2, here[1]+2)]
        for i in range(len(warp)):
            u = warp[i][0]
            v = warp[i][1]
            if grid[u][v] == "." and ans_grid[u][v] > ans_grid[here[0]][here[1]]+1:
                ans_grid[u][v] = min(ans_grid[u][v], ans_grid[here[0]][here[1]]+1)
                q.append((u,v))
        for i in range(len(move)):
            u = move[i][0]
            v = move[i][1]
            if (move[i] not in used or ans_grid[u][v] > ans_grid[here[0]][here[1]]) and grid[u][v] == ".":
                ans_grid[u][v] = min(ans_grid[here[0]][here[1]], ans_grid[u][v])
                q.appendleft((u,v))
                used.add((u,v))

bfs(ch,cw)
ans = ans_grid[dh][dw]
# print(ans_grid)
if ans == int(1e6+2):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
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)]

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

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    x, y = moveA_q.pop()
    moveB_q.append([x, y])
    for dx, dy in zip(dx_list, dy_list):
        nx, ny = x + dx, y + dy
        if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
            continue
        if scores[ny][nx] == float('inf'):
        # if scores[ny][nx] > scores[y][x]:
            scores[ny][nx] = scores[y][x]
            moveA_q.append([nx, ny])

    if not moveA_q:
        # 移動bで動けるマスをmodeA_qに格納
        while moveB_q:
            x, y = moveB_q.pop()
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    nx, ny = x + dx, y + dy
                    if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                        continue
                    if scores[ny][nx] == float('inf'):
                    # if scores[ny][nx] > scores[y][x]:
                        moveA_q.append([nx, ny])
                        scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
A = []
for i in range(H):
  A.append([])
  s = input()
  for j in range(W):
    if s[j] == '.':
      A[-1].append(0)
    else:
      A[-1].append(1)
P = [[1e6 for i in range(W)] for j in range(H)]
P[Ch][Cw] = 0
D = deque([[Ch, Cw]])
while len(D):
  d = D.pop()
  for i in range(-2, 3):
    for j in range(-2, 3):
      if 0 <= d[0]+i < H and 0 <= d[1]+j < W and A[d[0]+i][d[1]+j] == 0:
        if (i + j == 1 or i + j == -1) and i*j == 0 and P[d[0]][d[1]] < P[d[0]+i][d[1]+j]:
          D.append([d[0]+i, d[1]+j])
          P[d[0]+i][d[1]+j] = P[d[0]][d[1]]
        elif P[d[0]][d[1]]+1 < P[d[0]+i][d[1]+j]:
          D.appendleft([d[0]+i, d[1]+j])
          P[d[0]+i][d[1]+j] = P[d[0]][d[1]] + 1
if P[Dh][Dw] == 1e6:
  print(-1)
else:
  print(P[Dh][Dw])

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())

    y, x = map(int, input().split())
    start = (x+1, y+1)

    y, x = map(int, input().split())
    goal = (x+1, y+1)

    dist_table = [[-2] * (W+4)]
    dist_table.append([-2] * (W+4))
    for _ in range(H):
        row = '##' + input() + '##'
        row = [-1 if c == '.' else -2 for c in row]
        dist_table.append(row)
    dist_table.append([-2] * (W+4))
    dist_table.append([-2] * (W+4))



    sx, sy = start
    dist_table[sy][sx] = 0

    move1 = ((-1, 0), (1, 0), (0, 1), (0, -1))
    move2 = ((-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))

    queue1 = [start]
    queue2 = []

    while queue1:
        now_x, now_y = queue1.pop()
        if (now_x, now_y) == goal:
            break
        queue2.append((now_x, now_y))
        dist = dist_table[now_y][now_x]
        for dx, dy in move1:
            tx, ty = now_x + dx, now_y + dy
            if dist_table[ty][tx] == -1:
                dist_table[ty][tx] = dist
                queue1.append((tx, ty))
        if len(queue1) == 0:
            while queue2:
                now_x, now_y = queue2.pop()
                dist = dist_table[now_y][now_x]
                for dx, dy in move2:
                    tx, ty = now_x + dx, now_y + dy
                    if dist_table[ty][tx] == -1:
                        dist_table[ty][tx] = dist + 1
                        queue1.append((tx, ty))
    gx, gy = goal
    print(dist_table[gy][gx])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((b1[:, :], i8, i8, i8, i8), cache=True)
def main(wall, Sx, Sy, Tx, Ty):
    INF = 1 << 30
    H, W = wall.shape
    S = Sx * W + Sy
    T = Tx * W + Ty
    dist = np.full(H * W, INF, np.int64)
    deq = np.empty(H * W + 100, np.int64)
    dist[S] = 0
    deq[0], l, r = S, 0, 1
    while l < r:
        v, l = deq[l], l + 1
        vx, vy = divmod(v, W)
        # そのままあるく
        for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            wx, wy = vx + dx, vy + dy
            if not (0 <= wx < H):
                continue
            if not (0 <= wy < W):
                continue
            if wall[wx, wy]:
                continue
            w = wx * W + wy
            if dist[w] <= dist[v]:
                continue
            dist[w] = dist[v]
            deq[l - 1], l = w, l - 1
        # ワープする
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                wx, wy = vx + dx, vy + dy
                if not (0 <= wx < H):
                    continue
                if not (0 <= wy < W):
                    continue
                if wall[wx, wy]:
                    continue
                w = wx * W + wy
                if dist[w] <= dist[v] + 1:
                    continue
                dist[w] = dist[v] + 1
                deq[r], r = w, r + 1
    ans = dist[T]
    if ans == INF:
        ans = -1
    return ans

H, W = map(int, readline().split())
Sx, Sy = map(lambda x: int(x) - 1, readline().split())
Tx, Ty = map(lambda x: int(x) - 1, readline().split())
wall = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W] == b'#'

print(main(wall, Sx, Sy, Tx, Ty))

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

INF = 10**12
path = [[INF] * w for _ in range(h)] #ここに各マスの移動コストを記録する

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] #ワープするときの移動

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)

Submission status: Accepted

Solution code:
from operator import itemgetter, attrgetter
import sys
readlines = sys.stdin.readlines
input = sys.stdin.readline
 
class RadixHeap:
    def __init__(self, C=1 << 31):
        self.last = 0
        self.size = 0
        self.v = [[] for _ in range(C.bit_length()+1)]
 
    def push(self, key, val):
        self.size += 1
        self.v[(key ^ self.last).bit_length()].append((key, val))
 
    def pop(self):
        v = self.v
        if not v[0]:
            i = 1
            while not v[i]:
                i += 1
            vi = v[i]
            new_last, _ = min(vi, key=itemgetter(0))
            for key, val in vi:
                v[(key ^ new_last).bit_length()].append((key, val))
            self.last = new_last
            vi.clear()
        self.size -= 1
        return v[0].pop()
 
    def __len__(self): return self.size

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 = readlines()
 
INF = 10**10
D = [[INF]*W for _ in [0]*H]
 
q = RadixHeap()
q.push(0, Ch*W+Cw)
 
while q:
    d, ij = q.pop()
    i, j = divmod(ij, W)
 
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            I = i+di
            J = j+dj
            if 0 <= I < H and 0 <= J < W and S[I][J] == '.':
                if abs(di)+abs(dj) == 1:
                    if D[I][J] <= d:
                        continue
                    D[I][J] = d
                    q.push(d, I*W+J)
                else:
                    if D[I][J] <= d+1:
                        continue
                    D[I][J] = d+1
                    q.push(d+1, I*W+J)
 
ans = D[Dh][Dw]
print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**8)

def main():
    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 = [list(input()) for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    cnt = [[float('inf')] * W for _ in range(H)]
    dh = [1,0,-1,0]
    dw = [0,1,0,-1]
    visited[Ch][Cw] = True
    cnt[Ch][Cw] = 0
    Q = deque([[Ch,Cw]])
    while Q:
        h, w = Q.popleft()
        c = cnt[h][w]
        if h == Dh and w == Dw:
            break
        for i in range(4):
            nh = h + dh[i]
            nw = w + dw[i]
            if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                if cnt[nh][nw] > c:
                    cnt[nh][nw] = c
                    Q.appendleft([nh,nw])
        nc = c + 1
        for j in range(-2,3):
            for k in range(-2,3):
                nh = h + j
                nw = w + k
                if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == '.':
                    if cnt[nh][nw] > nc:
                        cnt[nh][nw] = nc
                        Q.append([nh,nw])

    if cnt[Dh][Dw] == float('inf'):
        print(-1)
    else:
        print(cnt[Dh][Dw])




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from heapq import *

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=list(sys.stdin)

ans=-1
hp=[(0,si,sj)]
dirs=[-2,-1,0,1,2]
dist=[[float('inf')]*W for _ in range(H)]
dist[si][sj]=0
while hp:
    k,i,j=heappop(hp)
    if i==ti and j==tj:
        ans=k
        break
    if k>dist[i][j]:
        continue
    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 A[ni][nj]=='#':
                continue
            if abs(di)+abs(dj)==1:
                nk=k
            else:
                nk=k+1
            if nk>=dist[ni][nj]:
                continue
            dist[ni][nj]=nk
            heappush(hp,(nk,ni,nj))

print(ans)