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, 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()))
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 = defaultdict(lambda: float('inf'))
visited[start] = 0

while queue:
	n, d = queue.popleft()
	if n == end:
		print(d)
		exit()
	if visited[n] != d:
		continue
	i, j = n
	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 (di, dj) in [(1,0),(-1,0),(0,1),(0,-1)]:
				nd = d
				if nd < visited[(ni,nj)]:
					queue.appendleft(((ni,nj), nd))
					visited[(ni,nj)] = nd
			else:
				nd = d+1
				if nd < visited[(ni,nj)]:
					queue.append(((ni,nj), nd))
					visited[(ni,nj)] = nd
print(-1)

Submission status: Accepted

Solution code:
import sys, math

# input = sys.stdin.readline

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
S = [[1 if s=='.' else 0 for s in input()] for _ in range(H)]
costs = [[math.inf]*W for _ in range(H)]
costs[Ch-1][Cw-1] = 0
que = [(0, Ch-1, Cw-1)]
next_que = []

while len(next_que)>0 or len(que)>0:
    while len(que)>0:
        c, h, w = que.pop(0)
        if c >= costs[Dh-1][Dw-1]:
            print(costs[Dh-1][Dw-1])
            sys.exit()
        for i, j in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
            if i < 0 or j < 0 or i>=H or j>=W:
                continue
            if i == Dh - 1 and j == Dw - 1:
                print(c)
                sys.exit()
            if S[i][j] and costs[i][j] > c:
                costs[i][j] = c
                que.append((c, i, j))
        for dw in [-2, -1, 0, 1, 2]:
            for dh in [-2, -1, 0, 1, 2]:
                if w+dw < 0 or h+dh < 0 or w+dw>=W or h+dh>=H:
                    continue
                if S[h+dh][w+dw] and costs[h+dh][w+dw] > c+1:
                    costs[h+dh][w+dw] = c+1
                    next_que.append((c+1, h+dh, w+dw))
    que = next_que
    next_que = []

print(-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())
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:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import sys
import numpy as np

def solve(H, W, Cy, Cx, Dy, Dx, S):
    inf = 1<<60
    Cy -= 1
    Cx -= 1
    Dy -= 1
    Dx -= 1
    st0 = [(Cy,Cx,0)]
    st1 = [(0,0,0)]*0
    D = np.full((H, W), inf)
    D[Cy, Cx] = 0
    while st0 or st1:
        if not st0:
            st0 = st1
            st1 = [(0,0,0)]*0
        y, x, d = st0.pop()
        if D[y, x] != d:
            continue
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                uy = y + dy
                ux = x + dx
                if 0<=uy<H and 0<=ux<W and S[uy,ux]==0:
                    if abs(dy)+abs(dx) <= 1:
                        if D[uy, ux] > d:
                            st0.append((uy, ux, d))
                            D[uy, ux] = d
                    else:
                        if D[uy, ux] > d + 1:
                            st1.append((uy, ux, d+1))
                            D[uy, ux] = d+1
    ans = D[Dy, Dx] if D[Dy, Dx] != inf else -1
    return ans

numba_compile([
    [solve, "i8(i8,i8,i8,i8,i8,i8,u1[:,:])"]
])

def main():
    H, W = map(int, sys.stdin.buffer.readline().split())
    Cy, Cx = map(int, sys.stdin.buffer.readline().split())
    Dy, Dx = map(int, sys.stdin.buffer.readline().split())
    S = np.empty((H, W), dtype=np.uint8)
    for i in range(H):
        S[i] = np.frombuffer(sys.stdin.buffer.readline()[:-1], dtype=np.uint8) == ord("#")
    ans = solve(H, W, Cy, Cx, Dy, Dx, S)
    print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque
def bfs(sl, visited, sy, sx, gy, gx, h, w):
    q = deque([(sy,sx,0)])
    q_warp = deque([])
    visited[sy][sx] = 0

    while q:
        while q:
            y, x, d = q.popleft()
            if (y, x) == (gy, gx):
                return visited[gy][gx]
            for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                ny, nx = y+j, x+k
                if ny >= h or nx >= w or ny < 0 or nx < 0:
                    continue
                if sl[ny][nx] == '.' and (visited[ny][nx] == -1 or visited[ny][nx] > visited[y][x]):
                    visited[ny][nx] = visited[y][x]
                    q.appendleft((ny,nx,d))

            for j in range(-2,3):
                for k in range(-2,3):
                    ny, nx = y+j, x+k
                    if ny >= h or nx >= w or ny < 0 or nx < 0: continue
                    if sl[ny][nx] == '.' and visited[ny][nx] == -1:
                        visited[ny][nx] = visited[y][x] + 1
                        q.append((ny,nx,d))

    return -1


h, w = map(int, input().split()) 
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
sl = [list(input()) for _ in range(h)]
visited = [ [-1]*w for i in range(h)]
ans = bfs(sl,visited,ch-1,cw-1,dh-1,dw-1,h,w)
print(ans)

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

WALL = -100
INI = -1
PASSED = 0

S = [[0] * w for _ in range(h)]
for i in range(h):
    tmp = input()
    for j in range(w):
        if tmp[j] == '#':
            S[i][j] = WALL
        else:
            S[i][j] = INI

S[Ch][Cw] = 0
direction = [[0, -1], [-1, 0], [0, 1], [1, 0]]


def dfs(y, x, d):
    d.append((y, x))
    if y == Dh and x == Dw:
        print(S[y][x])
        exit()
    for dy, dx in direction:
        next_y = y + dy
        next_x = x + dx
        if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
            continue
        if S[next_y][next_x] == INI:
            #print("y = ", y, "x = ", x, "next_y = ", next_y, "next_x = ", next_x)
            S[next_y][next_x] = S[y][x]
            dfs(next_y, next_x, d)

def bfs(y, x, d):
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            next_y = y + dy
            next_x = x + dx
            if next_y < 0 or next_y >= h or next_x < 0 or next_x >= w:
                continue
            if S[next_y][next_x] == INI:
                d.append((next_y, next_x))
                #print("S[u][x] = ", S[y][x])
                S[next_y][next_x] = S[y][x] + 1
    return False

def show(S):
    for y in range(h):
        for x in range(w):
            if S[y][x] == WALL:
                print("#", end="")
            elif S[y][x] == INI:
                print(".", end="")
            else:
                print(S[y][x], end="")
        print()

d = deque()
d.append((Ch, Cw))
d2 = deque()
while len(d):
    while(len(d)):
        y, x = d.popleft()
        dfs(y, x, d2)

    while len(d2):
        y2, x2 = d2.popleft()
        #print("y2 = ", y2, "x2 = ", x2)
        #show(S)
        bfs(y2, x2, d)

print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
sys.setrecursionlimit(10**6)
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(H, W, Ch, Cw, Dh, Dw, data):
    # data = list(data.reshape(-1))
    N = HEIGHT * WIDTH
    visited = [0] * N

    start = (Ch + 1) * WIDTH + (Cw + 1)
    goal = (Dh + 1) * WIDTH + (Dw + 1)
    q = []
    nextJump = set()
    q.append(start)

    currentDistance = 0
    while True:
        while q:
            p = q.pop()
            if p == goal:
                return currentDistance
            if visited[p]:
                continue
            for dx in [-2, -1, 0, +1, +2]:
                for dy in [-WIDTH * 2, -WIDTH, 0, WIDTH, WIDTH * 2]:
                    nextJump.add(p + dx + dy)
            visited[p] = 1
            for d in [-1, +1, -WIDTH, +WIDTH]:
                if data[p + d] and not visited[p + d]:
                    q.append(p + d)

        # no continuous cell
        for p in nextJump:
            if not data[p]:
                continue
            if visited[p]:
                continue
            q.append(p)

        currentDistance += 1
        nextJump = set()
        if not q:
            return -1


def readMap(H, W):
    global SENTINEL, HEIGHT, WIDTH
    SENTINEL = 2
    HEIGHT = H + SENTINEL * 2
    WIDTH = W + SENTINEL * 2
    data = [0] * (HEIGHT * WIDTH)
    ok = ord(".")
    for i in range(H):
        S = input().strip()
        y = (i + SENTINEL) * WIDTH
        for j in range(W):
            data[y + (j + SENTINEL)] = 1 if S[j] == ok else 0
    return data


def main():
    # parse input
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    D = readMap(H, W)
    print(solve(H, W, Ch, Cw, Dh, Dw, D))


# tests
T1 = """
4 4
1 1
4 4
..#.
..#.
.#..
.#..
"""
TEST_T1 = """
>>> as_input(T1)
>>> main()
1
"""

T2 = """
4 4
1 4
4 1
.##.
####
####
.##.
"""
TEST_T2 = """
>>> as_input(T2)
>>> main()
-1
"""

T3 = """
4 4
2 2
3 3
....
....
....
....
"""
TEST_T3 = """
>>> as_input(T3)
>>> main()
0
"""

T4 = """
4 5
1 2
2 5
#.###
####.
#..##
#..##
"""
TEST_T4 = """
>>> as_input(T4)
>>> main()
2
"""


def _test():
    import doctest
    doctest.testmod()
    g = globals()
    for k in sorted(g):
        if k.startswith("TEST_"):
            doctest.run_docstring_examples(g[k], g)


def as_input(s):
    "use in test, use given string as input file"
    import io
    f = io.StringIO(s.strip())
    g = globals()
    g["input"] = lambda: bytes(f.readline(), "ascii")
    g["read"] = lambda: bytes(f.read(), "ascii")


input = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

if sys.argv[-1] == "-t":
    print("testing")
    _test()
    sys.exit()

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]
dij4=[(0,1),(1,0),(-1,0),(0,-1)]

def solve():
    aa = [[-1] * w for _ in range(h)]
    stack = [(si, sj, 0)]

    while stack:
        wall = []
        while stack:
            i, j, d = stack.pop()
            crash = False
            for di, dj in dij4:
                ni, nj = i + di, j + dj
                if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                if aa[ni][nj] != -1: continue
                if ss[ni][nj]: crash = True
                else:
                    aa[ni][nj] = d
                    stack.append((ni, nj, d))
            if crash: wall.append((i, j, d))

        for i, j, d in wall:
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if di == 0 and dj == 0: continue
                    ni, nj = i + di, j + dj
                    if ni < 0 or ni >= h or nj < 0 or nj >= w: continue
                    if ss[ni][nj]: continue
                    if aa[ni][nj] != -1: continue
                    aa[ni][nj] = d + 1
                    stack.append((ni, nj, d + 1))

    print(aa[gi][gj])

h,w=MI()
si,sj=MI1()
gi,gj=MI1()
ss=[[1 if c=="#" else 0 for c in SI()] for _ in range(h)]
solve()

Submission status: Accepted

Solution code:
from collections import deque
import sys
def input():return sys.stdin.readline().strip()
def main():
    H, W = map(int, input().split())
    sh, sw = map(int, input().split())
    sh -= 1; sw -= 1
    start = (sh+2)*(W+4) + 2 + sw
    dh, dw = map(int, input().split())
    dh -= 1; dw -= 1
    goal = (dh+2)*(W+4) + 2 + dw

    field = "#"*(W+4)*2
    field += "##" + "####".join([ input() for _ in range(H)]) + "##"
    field += "#"*(W+4)*2

    move = [-1, 1, -(W+4), W+4]
    ex_left = [-2*(W+4)-2, -(W+4)-2, -2, (W+4)-2, 2*(W+4)-2, -(W+4)-1, (W+4)-1]
    ex_right = [-2*(W+4)+2, -(W+4)+2, +2, (W+4)+2, 2*(W+4)+2, -(W+4)+1, (W+4)+1]
    ex_up = [-2*(W+4)-2, -2*(W+4)-1, -2*(W+4), -2*(W+4)+1, -2*(W+4)+2, -(W+4)-1, -(W+4)+1]
    ex_down = [2*(W+4)-2, 2*(W+4)-1, 2*(W+4), 2*(W+4)+1, 2*(W+4)+2, (W+4)-1, (W+4)+1]

    INF = 10 ** 18
    num = [INF] * (H+4) * (W+4)
    warped = [False] * (H+4) * (W+4)

    def bfs(s):
        q = deque()
        num[s] = 0
        q.append((s, 0))
    
        while q:
            now, cost = q.popleft()

            # warpしたものの既に来ていた場合はスルー
            if cost > num[now]:
                continue
            else:
                num[now] = cost

            if now == goal:
                return

            for i, dx in enumerate(move):
                nx = now + dx
                if field[nx] == "." and num[nx] == INF:
                    q.appendleft((nx, cost))
                    num[nx] = cost

                elif field[nx] == "#":
                    if i == 0:
                        ex = ex_left
                    elif i == 1:
                        ex = ex_right
                    elif i == 2:
                        ex = ex_up
                    else:
                        ex = ex_down

                    for dx2 in ex:
                        nx2 = now + dx2
                        if field[nx2] == "." and num[nx2] == INF and not warped[nx2]:
                            q.append((nx2, cost+1))
                            warped[nx2] = True
    
    bfs(start)

    if num[goal] == INF:
        print(-1)
    else:
        print(num[goal])

    
    # for i in range(0, (H+4)*(W+4), W+4):
    #     print(field[i:i+W+4])
    
    # print(start)
    # print(start//(W+4), start%(W+4))
    # print(goal)
    # print(goal//(W+4), goal%(W+4))
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.appendleft((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
from heapq import heappop, heappush


def solve(h, w, s, t, field):
    WARP = (-(w * 2 + 10), -(w * 2 + 9), -(w * 2 + 8), -(w * 2 + 7), -(w * 2 + 6),
            -(w + 6), -(w + 5), -(w + 3), -(w + 2),
            -2, 2,
            w + 2, w + 3, w + 5, w + 6,
            w * 2 + 6, w * 2 + 7, w * 2 + 8, w * 2 + 9, w * 2 + 10)
    WALK = (-(w + 4), -1, 1, w + 4)

    q = [(0, s)]
    visited = np.zeros((h + 4) * (w + 4), np.int8)
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        if visited[v]:
            continue
        visited[v] = 1
        for d in WALK:
            if field[v + d] or visited[v + d]:
                continue
            heappush(q, (cost, d + v))
        for d in WARP:
            if field[v + d] or visited[v + d]:
                continue
            heappush(q, (cost + 1, d + v))

    return -1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8,i8,i1[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8,i8,i8,i8,i1[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

h, w = map(int, sys.stdin.readline().split())
ch, cw = map(int, sys.stdin.readline().split())
dh, dw = map(int, sys.stdin.readline().split())
field = np.ones((h + 4) * (w + 4), dtype=np.int8)
for i in range(h):
    line = sys.stdin.readline().strip()
    field[(i + 2) * (w + 4) + 2:(i + 2) * (w + 4) + w + 2] = list(map('.#'.index, line))
s = (ch + 1) * (w + 4) + cw + 1
t = (dh + 1) * (w + 4) + dw + 1
ans = solve(h, w, s, t, field)
print(ans)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
from collections import deque
todo=deque([[0,Ch,Cw]])
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo:
  cnt,nh,nw=todo.popleft()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.appendleft([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        todo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])

Submission status: Accepted

Solution code:
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )

# if ch==dh and cw==dw:
#   print(0)
#   exit()

INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    # if M[h][w] == "#": M[h][w] = -1

ch -= 1
cw -= 1
dh -= 1
dw -= 1

M[ch][cw] = 0
# M[dh][dw] = "G"

# _pa(M)


from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

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

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      Q.appendleft((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      Q.appendleft((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))

# _pa(M)

if ans == INF: ans = -1
print(ans)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    H,W = LMIIS()
    Ch,Cw = LMIIS()
    Ch -= 1
    Cw -= 1
    Dh,Dw = LMIIS()
    Dh -= 1
    Dw -= 1
    S = []
    for i in range(H):
        S.append(input())
    
    num_warp = []
    for i in range(H):
        num_warp.append([-1]*W)
    
    


    def check_and_move(y,x,d):
        if 0 <= y < H and 0 <= x < W and num_warp[y][x] == -1 and S[y][x] == '.':
            num_warp[y][x] = d
            return True
        return False


    # 歩行はDFS, ワープはBFS
    targets = deque([(Ch,Cw,0)])
    while targets:
        y,x,d = targets.pop()
        if not check_and_move(y,x,d):
            continue

        if y == Dh and x == Dw:
            break

        for y2,x2 in [(y-1,x),(y,x+1),(y+1,x),(y,x-1)]:
            targets.append((y2,x2,d))

        for y2,x2 in[
                (y-2,x-2),(y-2,x-1),(y-2,x),(y-2,x+1),(y-2,x+2),
                (y-1,x-2),(y-1,x-1),(y-1,x+1),(y-2,x+2),
                (y,x-2),(y,x+2),
                (y+1,x-2),(y+1,x-1),(y+1,x+1),(y+1,x+2),
                (y+2,x-2),(y+2,x-1),(y+2,x),(y+2,x+1),(y+2,x+2)
            ]:
            targets.appendleft((y2,x2,d+1))

    print(num_warp[Dh][Dw])



    
main()

Submission status: Accepted

Solution code:
####################################################################
import sys
def _p(*_a):
  #return
  _s=" ".join(map(str,_a))
  #print(_s)
  sys.stderr.write(_s+"\n")
####################################################################
def _pa(_aa):
  #return
  for _a in _aa: _p(_a)
####################################################################
H,W = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
M = list( list(input()) for _ in range(H) )

if ch==dh and cw==dw:
  print(0)
  exit()

INF = 10**18

for h in range(H):
  for w in range(W):
    if M[h][w] == ".": M[h][w] = INF
    # if M[h][w] == "#": M[h][w] = -1

ch -= 1
cw -= 1
dh -= 1
dw -= 1

M[ch][cw] = 0
# M[dh][dw] = "G"

# _pa(M)


from collections import deque
Q = deque()
Q.append((ch,cw))

ans = INF

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

  for ih,iw in [(1,0), (-1,0), (0,1), (0,-1)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w], M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w] < M[nh][nw]:
      M[nh][nw] = M[h][w]
      Q.appendleft((nh,nw))
      continue

    if M[h][w] > M[nh][nw]:
      M[h][w] = M[nh][nw]
      Q.appendleft((h,w))

  for ih,iw in [(1,1), (1,-1), (-1,1), (-1,-1), (2,0), (2,1), (2,2), (2,-1), (2,-2), (1,2), (1,-2), (0,2), (0,-2), (-1,2), (-1,-2), (-2,0), (-2,1), (-2,-2), (-2,-1), (-2,-2)]:
    nh = h + ih
    nw = w + iw
    if nh < 0 or H <= nh: continue
    if nw < 0 or W <= nw: continue
    if M[nh][nw] == "#": continue

    if nh == dh and nw == dw:
      M[nh][nw] = min(M[h][w]+1, M[dh][dw])
      ans = min(ans, M[nh][nw])
      continue

    if M[h][w]+1 < M[nh][nw]:
      M[nh][nw] = M[h][w]+1
      Q.append((nh,nw))
      continue

    if M[h][w] > M[nh][nw]+1:
      M[h][w] = M[nh][nw]+1
      Q.append((h,w))

# _pa(M)

if ans == INF: ans = -1
print(ans)

Submission status: Accepted

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

import sys
import pprint
from collections import deque


sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	h, w = map(int, sys.stdin.readline().split())
	ch, cw = map(int, sys.stdin.readline().split())
	dh, dw = map(int, sys.stdin.readline().split())
	s = [sys.stdin.readline().rstrip() for i in [0]*h]
	graph = [[[] for i in [0]*w] for j in [0]*h]
	
	def getMaze(x, y):
		if not (0 <= x < w and 0 <= y < h):
			return -1
		return s[y][x]

	for y in range(h):
		for x in range(w):
			if s[y][x] == "#":
				continue
			


	# log.print(graph)
	stack = deque([(cw-1, ch-1)])
	dist = [[float("inf")]*w for i in range(h)]
	while len(stack) != 0:
		x, y = stack.popleft()
		log.print(x, y, dist[y][x])
		if dist[y][x] == float("inf"):
			dist[y][x] = 0
		d = dist[y][x]
		nexts = []
		for i in range(-2, 2+1):
			for j in range(-2, 2+1):
				if (i, j) == (0, 0):
					continue
				if getMaze(x + i, y + j) == ".":
					if (i, j) in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
						nexts.append((x + i, y + j, 0))
					else:
						nexts.append((x + i, y + j, 1))
		for next in nexts:
			nx, ny, cost = next
			if dist[ny][nx] > d + cost:
				dist[ny][nx] = d + cost
				if cost == 1:
					stack.append((nx, ny))
				else:
					stack.appendleft((nx, ny))
	log.print(dist)
	if dist[dh-1][dw-1] == float("inf"):
		print(-1)
	else:
		print(dist[dh-1][dw-1])
	
	


main()

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.appendleft((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])