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())
c = tuple(map(lambda x: int(x) - 1, input().split()))
d = tuple(map(lambda x: int(x) - 1, input().split()))
maze = [[ch == '#' for ch in input().rstrip()] for _ in range(H)]
 
from sys import exit
from collections import deque
from itertools import product
que = deque([(*c, 0)])
passed = set()
while que:
    h,w,dist = que.popleft()
#         print(f'{h=},{w=}')
    if (h,w) == d:
        print(dist)
        exit()
    if (h,w) in passed:
        continue
    passed.add((h,w))
    for dh, dw in [[0,1], [0,-1], [1,0], [-1,0]]:
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'no_warp: {nh=},{nw=}')
            que.appendleft((nh, nw, dist))

    for dh,dw in [
        [-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], 
    ]: 
        nh = h + dh
        nw = w + dw
        if 0 <= nh < H and 0 <= nw < W and (nh,nw) not in passed and not maze[nh][nw]:
#                 print(f'warp: {nh=},{nw=}')
            que.append((nh, nw, dist + 1))
print(-1)

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    dq = deque([(ch-1, cw-1)])
    check = [[-1]*w for i in range(h)]
    check[ch-1][cw-1] = 0
    count = 0

    # 判定式
    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1
    allCheck = lambda x,y: (not inMaze(x,y)) or isWall(x,y) or isChecked(x,y)

    # 移動先
    walk = [(0,1), (0,-1), (1,0), (-1,0)]
    warp = [(dy, dx) for dy in range(-2,3) for dx in range(-2,3)]

    while True:
        walked = []
        while dq:
            y, x = dq.popleft()
            walked.append((y, x))
            for dy, dx in walk:
                ny = y+dy
                nx = x+dx
                if allCheck(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in walked:
            for dy, dx in warp:
                ny = y+dy
                nx = x+dx
                if allCheck(nx, ny):
                    continue
                check[ny][nx] = count
                dq.append((ny, nx))
        if not dq:
            break

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
from collections import deque
#======================================================#
def main():
    h, w = MII()
    ch, cw = MII()
    dh, dw = MII()
    maze = [IS() for _ in range(h)]
    dq = deque([(ch-1, cw-1)])
    check = [[-1]*w for i in range(h)]
    check[ch-1][cw-1] = 0
    count = 0

    # 判定式
    inMaze = lambda x,y: 0 <= y < h and 0 <= x < w
    isWall = lambda x,y: maze[y][x] == '#'
    isChecked = lambda x,y: check[y][x] != -1
    allCheck = lambda x,y: (not inMaze(x,y)) or isWall(x,y) or isChecked(x,y)

    # 移動先
    walk = [(0,1), (0,-1), (1,0), (-1,0)]
    warp = [(dy, dx) for dy in range(-2,3) for dx in range(-2,3)]

    while True:
        tmp = []
        while dq:
            y, x = dq.popleft()
            tmp.append((y, x))
            for dy, dx in walk:
                ny = y+dy
                nx = x+dx
                if allCheck(nx, ny):
                    continue
                check[ny][nx] = count
                dq.appendleft((ny, nx))

        count += 1
        for y, x in tmp:
            for dy, dx in warp:
                ny = y+dy
                nx = x+dx
                if allCheck(nx, ny):
                    continue
                check[ny][nx] = count
                dq.append((ny, nx))
        if not dq:
            break

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools

input = sys.stdin.readline


def ST():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


h, w = MI()
Ch, Cw = MI()
Dh, Dw = MI()

S = [["#"] * (w + 4), ["#"] * (w + 4)]
for _ in range(h):
    S.append(["#", "#"] + list(ST()) + ["#", "#"])
S.append(["#"] * (w + 4))
S.append(["#"] * (w + 4))

dxy = ((0, 1), (0, -1), (1, 0), (-1, 0), (0, 0))
wxy = tuple(
    (x, y)
    for x, y in itertools.product([-2, -1, 0, 1, 2], repeat=2)
    if (x, y) not in dxy
)
dxy = ((0, 1), (0, -1), (1, 0), (-1, 0))

wq = {(Ch + 1, Cw + 1)}
cost = 0
while wq:
    q = wq
    passed = set()
    while q:
        qq = set()
        for y, x in q:
            if y == Dh + 1 and x == Dw + 1:
                print(cost)
                exit()
            passed.add((y, x))
            S[y][x] = "#"
            for dy, dx in dxy:
                ny, nx = y + dy, x + dx
                if S[ny][nx] == "#":
                    continue
                # if ny == Dh + 1 and nx == Dw + 1:
                #     print(cost)
                #     exit()
                qq.add((ny, nx))
                # S[ny][nx] = "#"
        q = qq

    # print(cost, set(passed))
    wq = set()
    for y, x in passed:
        for dy, dx in wxy:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == "#":
                continue
            wq.add((ny, nx))

    cost += 1

print(-1)

Submission status: Accepted

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

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)
    q = [(0,S)]
    while q:
        dv, v = heappop(q)
        if dv > dist[v]:
            continue
        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] <= dv:
                continue
            dist[w] = dv
            heappush(q, (dv, w))
        # ワープする
        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] <= dv + 1:
                    continue
                dist[w] = dv + 1
                heappush(q, (dv+1, w))
    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:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() # narr((2,3), int)
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
#visited = narr((H, W), lambda: float('inf'))
visited = [[float('inf')] * W for _ in range(H)]
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '#': continue
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
print(-1)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)

Submission status: Accepted

Solution code:
#dequeでappendとappendleftを管理
from collections import deque

def inc(y, x):
	return 0 <= y < H and 0 <= x < W

H, W = map(int, input().split())
Sy, Sx = map(int, input().split())
Gy, Gx = map(int, input().split())
"""
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()
"""
a = [input() for i in range(H)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

#同じ大きさの行列を作って最短路をメモする発想がなかった
visit = [[-1 for i in range(W)] for j in range(H)]
visit[Sy-1][Sx-1]=0 #sy-1, sx-1に注意
deq = deque([(Sy-1, Sx-1)])

while deq:
    h, w = deq.pop()
    for dh, dw in zip(DH, DW):
        x = w+dw; y=h+dh
        if inc(y, x)==False or a[y][x]=='#':
            continue
        if visit[y][x]==-1 or visit[y][x]>visit[h][w]:
            visit[y][x] = visit[h][w]
            deq.append((y,x))
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if inc(h+dh, w+dw)==False or a[h+dh][w+dw]=='#':
                continue
            if visit[h+dh][w+dw]==-1: 
                visit[h+dh][w+dw] = visit[h][w]+1
                deq.appendleft((h+dh, w+dw))
if visit[Gy-1][Gx-1] == 1e8:
    print(-1)
else:
    print(visit[Gy-1][Gx-1])

Submission status: Accepted

Solution code:
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
#narr = lambda d, f: narr(d[:-1], lambda: [f() for _ in range(d[-1])]) if d else f() # narr((2,3), int)
mat = lambda x, y, v: [[v]*y for _ in range(x)]
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
C = rl()
D = rl()
M = []
for i in range(H):
	s = rs()
	M.append(s)

start = tuple([C[0]-1, C[1]-1])
end = tuple([D[0]-1, D[1]-1])

queue = deque()
queue.append((start, 0))
#visited = narr((H, W), lambda: float('inf'))
#visited = [[float('inf')] * W for _ in range(H)]
visited = mat(H, W, float('inf'))
visited[start[0]][start[1]] = 0

ds = [(1,0),(-1,0),(0,1),(0,-1)]
while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	i, j = n
	if visited[i][j] != d:
		continue
	nd = d
	for di, dj in ds:
		ni, nj = i+di, j+dj
		if not (0 <= ni < H and 0 <= nj < W): continue
		if M[ni][nj] == '#': continue
		if nd < visited[ni][nj]:
			queue.appendleft(((ni,nj), nd))
			visited[ni][nj] = nd
	nd = d+1
	for di in range(-2, 3):
		for dj in range(-2, 3):
			if (di, dj) == (0,0): continue
			ni, nj = i+di, j+dj
			if not (0 <= ni < H and 0 <= nj < W): continue
			if M[ni][nj] == '#': continue
			if nd < visited[ni][nj]:
				queue.append(((ni,nj), nd))
				visited[ni][nj] = nd
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())

maze = [list(input()) for i in range(h)]
ans = [[-1]*w for i in range(h)]

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

ans[ch-1][cw-1]=0
def bfs(ans):
  qu = deque([])
  qu.append([cw-1,ch-1])
  while qu:
    zahyou=qu.popleft()
    x=zahyou[0]
    y=zahyou[1]
    count=0
    for i in range(4):
      if 0 <= x+dx[i] < w and 0 <= y+dy[i] < h:
        if maze[y+dy[i]][x+dx[i]]=="." and (ans[y+dy[i]][x+dx[i]]>ans[y][x] or ans[y+dy[i]][x+dx[i]]==-1):
          qu.appendleft([x+dx[i],y+dy[i]])
          ans[y+dy[i]][x+dx[i]] = ans[y][x]
          count+=1
    if count!=4:
      for i in range(x-2,x+3):
        for j in range(y-2,y+3):
          if 0<=i<w and 0<=j<h:
            if maze[j][i]=="." and (ans[j][i]>ans[y][x]+1 or ans[j][i]==-1):
              ans[j][i]=(ans[y][x]+1)
              qu.append([i,j])

bfs(ans)
print(ans[dh-1][dw-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())

mp = [input() for _ in range(H)]
ds1 = [[0,-1],[0,1],[-1,0],[1,0]]
ds2 = [[i,j] for i in range(-2,3) for j in range(-2,3)]

memo = [[0]*W for _ in range(H)]
memo[CH][CW] = 1

h1 = deque([(CH,CW)])
h2 = deque([])
ans = 0

while 1:
  while h1:
    t = h1.popleft()
    h2.append(t)
    for d in ds1:
      if t[0]+d[0] >= 0 and t[0]+d[0] < H \
         and t[1]+d[1] >= 0 and t[1]+d[1] < W:
        if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 0:
          memo[t[0]+d[0]][t[1]+d[1]] = 1
          h1.append((t[0]+d[0], t[1]+d[1]))
  if memo[DH][DW] == 1:
    print(ans)
    exit()
  ans += 1

  while h2:
    t = h2.popleft()
    for d in ds2:
      if t[0]+d[0] >= 0 and t[0]+d[0] < H \
         and t[1]+d[1] >= 0 and t[1]+d[1] < W:
        if mp[t[0]+d[0]][t[1]+d[1]] == '.' and memo[t[0]+d[0]][t[1]+d[1]] == 0:
          memo[t[0]+d[0]][t[1]+d[1]] = 1
          h1.append((t[0]+d[0], t[1]+d[1]))
          
  if not h1:
    print(-1)
    exit()

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

grid = [[0 for _ in range(W)] for _ in range(H)]
grid[Ch][Cw] = 1

stack1=[(Ch,Cw)]
stack2=[]

answer=0

while 1:
    while stack1:
        sh,sw=stack1.pop()
        stack2.append((sh,sw))
        for i,j in [(-1,0),(1,0),(0,1),(0,-1)]:
            nh,nw = sh+i, sw+j
            if 0<=nh<H and 0<=nw<W and S[nh][nw]!="#" and grid[nh][nw]==0:
                if nh==Dh and nw==Dw:
                    print(answer)
                    exit()
                grid[nh][nw]=1
                stack1.append((nh,nw))
    answer+=1

    while stack2:
        sh,sw=stack2.pop()
        for i in range(-2,3):
            for j in range(-2,3):
                nh,nw = sh+i,sw+j
                if 0<=nh<H and 0<=nw<W and S[nh][nw]!="#" and grid[nh][nw]==0:
                    if nh==Dh and nw==Dw:
                        print(answer)
                        exit()
                    grid[nh][nw]=1
                    stack1.append((nh,nw))

    if not stack1:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
NX = [1, 0, -1, 0]
NY = [0, 1, 0, -1]
PX = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2]
PY = [-2, -1, 0, 1, 2, -2, -1, 1, 2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for i in range(4):
        nx = x + NX[i]
        ny = y + NY[i]
        if 0 <= nx < w and 0 <= ny < h and S[ny][nx] != "#":
            if grid[ny][nx] == -1 or grid[ny][nx] > count:
                grid[ny][nx] = count
                que.appendleft((count, ny, nx))
    for i in range(20):
        px = x + PX[i]
        py = y + PY[i]
        if 0 <= px < w and 0 <= py < h and S[py][px] != "#":
            if grid[py][px] == -1 or grid[py][px] > count + 1:
                grid[py][px] = count + 1
                que.append((count + 1, py, px))

print(grid[dh][dw])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

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
rows,cols = h,w

OK = "."
NG = "#"

ss = np.array([[c=="#" for c in input()] for _ in range(h)])
@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    # dx = [0,1,0,-1]
    # dy = [1,0,-1,0]
#     dx = []
#     dy = []
#     vvs = []
#     for i in range(-2,3):
#         for j in range(-2,3):
#             if not (i==j==0):
#                 dx.append(i)
#                 dy.append(j)
#                 if abs(i)+abs(j)>1:
#                     vvs.append(1)
#                 else:
#                     vvs.append(0)
    while q:
#         print(seen)
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        # print(pnum,divmod(pu,w))
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
#         for xx,yy,vv in zip(dx,dy,vvs):
    #         x = ux+xx
    #         y = uy+yy
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
print(main(ss,ch,cw,dh,dw))

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 = [list(input()) for _ in range(H)]
dist = [[-1] * W for _ in range(H)]

move = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if i == 0 and j == 0:
            continue
        move.append((i, j))
q = deque()
q.append((0, ch, cw))
while q:
    c, h, w = q.popleft()
    if dist[h][w] >= 0:
        continue
    dist[h][w] = c
    for hh, ww in move:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] < 0:
            if (hh, ww) in ((0,1), (1,0), (-1,0), (0,-1)):
                q.appendleft((c, h+hh, w+ww)) # 徒歩は前に追加
            else:
                q.append((c+1, h+hh, w+ww)) # ワープは後ろに追加

print(dist[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
S = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and S[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
                que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])

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

grid = []
for i in range(H):
    grid.append(input().rstrip())

d = deque()
d.append((Ch-1, Cw-1, 0))

memo = [[[False] * W for _ in range(H)] for _ in range(2)]
memo[0][Ch-1][Cw-1] = True

searched = [[False] * W for _ in range(H)]

ans = -1

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

    if searched[h][w]:
        continue

    searched[h][w] = True

    if h == Dh-1 and w == Dw-1:
        ans = c
        break

    for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        if 0 <= h+i < H and 0 <= w+j < W:
            if grid[h+i][w+j] == '.':
                if not memo[0][h+i][w+j] and not searched[h+i][w+j]:
                    memo[0][h+i][w+j] = True
                    d.appendleft((h+i, w+j, c))

    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= h+i < H and 0 <= w+j < W:
                if grid[h+i][w+j] == '.':
                    if not memo[0][h+i][w+j] and not memo[1][h+i][w+j] and not searched[h+i][w+j]:
                        memo[1][h+i][w+j] = True
                        d.append((h+i, w+j, c+1))

print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = (int(x) for x in input().split())
ch, cw = (int(x) - 1 for x in input().split())
dh, dw = (int(x) - 1 for x in input().split())
s = [list(input()) for _ in range(h)]
grid = [[-1] * w for _ in range(h)]
grid[ch][cw] = 0
walk = [[0, 1], [0, -1], [1, 0], [-1, 0]]
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]]

que = deque([(0, ch, cw)])
while que:
    count, y, x = que.popleft()
    if grid[y][x] < count:
        continue
    for NY, NX in walk:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count:
                grid[y + NY][x + NX] = count
                que.appendleft((count, y + NY, x + NX))
    for NY, NX in warp:
        if 0 <= y + NY < h and 0 <= x + NX < w and s[y + NY][x + NX] != '#':
            if grid[y + NY][x + NX] == -1 or grid[y + NY][x + NX] > count + 1:
                grid[y + NY][x + NX] = count + 1
                que.append((count + 1, y + NY, x + NX))

print(grid[dh][dw])

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch -= 1
cw -= 1
dh, dw = map(int, input().split())
dh -= 1
dw -= 1
S = [list(input()) for _ in range(H)]
dist = [[float("inf")] * W for _ in range(H)]

# x = []
# for i in range(5):
#     for j in range(5):
#         if i == 3 and j == 3:
#             continue
#         x.append((i-2, j-2))
# x = set(x)
y = {(0, 1), (1, 0), (-1, 0), (0, -1)}
# x = x - y

from collections import deque
q = deque()
q.append((ch, cw))
dist[ch][cw] = 0
while q:
    h, w = q.popleft()
    for hh, ww in y:
        if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w]:
            dist[h+hh][w+ww] = dist[h][w]
            q.appendleft((h+hh, w+ww))
    for hh in range(-2, 3):
        for ww in range(-2, 3):
            if 0 <= h+hh < H and 0 <= w+ww < W and S[h+hh][w+ww] == "." and dist[h+hh][w+ww] > dist[h][w] + 1:
                dist[h+hh][w+ww] = dist[h][w] + 1
                q.append((h+hh, w+ww))

if dist[dh][dw] == float("inf"):
    print(-1)
else:
    print(dist[dh][dw])

Submission status: Accepted

Solution code:
from collections import deque

def inc(y, x):
	return 0 <= y < H and 0 <= x < W

H, W = map(int, input().split())
Sy, Sx = map(int, input().split())
Gy, Gx = map(int, input().split())
"""
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()
"""
a = [input() for i in range(H)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

#同じ大きさの行列を作って最短路をメモする発想がなかった
visit = [[1e8 for i in range(W)] for j in range(H)]
visit[Sy-1][Sx-1]=0 #sy-1, sx-1に注意
deq = deque([(Sy-1, Sx-1)])

while deq:
    h, w = deq.pop()
    for dh, dw in zip(DH, DW):
        x = w+dw; y=h+dh
        if inc(y, x)==False or a[y][x]=='#':
            continue
        if visit[y][x] > visit[h][w]:
            visit[y][x] = visit[h][w]
            deq.append((y,x))
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if inc(h+dh, w+dw)==False or a[h+dh][w+dw]=='#':
                continue
            if visit[h+dh][w+dw] > visit[h][w]+1: 
                visit[h+dh][w+dw] = visit[h][w]+1
                deq.appendleft((h+dh, w+dw))
if visit[Gy-1][Gx-1] == 1e8:
    print(-1)
else:
    print(visit[Gy-1][Gx-1])

Submission status: Accepted

Solution code:
max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

import sys
from itertools import count
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


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

CONVERTED_MOVES = None

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

    return -1




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

    H += 4
    W += 4

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

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

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

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

    # print(CONVERTED_MOVES)

    print(solve(dist,start,goal))