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
from collections import deque

h,w=map(int,input().split())
ch,cw=map(int,input().split())
ch,cw=ch-1,cw-1
dh,dw=map(int,input().split())
dh,dw=dh-1,dw-1
s=[[*next(sys.stdin)] for _ in range(h)]

c=-1
for i in range(h):
    for j in range(w):
        if s[i][j]!='.':
            continue
        c+=1
        stk=[(i,j)]
        while stk:
            ii,jj=stk.pop()
            s[ii][jj]=c
            for di,dj in (-1,0),(0,1),(1,0),(0,-1):
                ni,nj=ii+di,jj+dj
                if not (0<=ni<h and 0<=nj<w):
                    continue
                if s[ni][nj]!='.':
                    continue
                stk.append((ni,nj))

n=c+1
cc=dc=-1
dirs=[-2,-1,0,1,2]
adj=[{*()} for _ in range(n)]
for i in range(h):
    for j in range(w):
        u=s[i][j]
        if u=='#':
            continue
        if i==ch and j==cw:
            cc=u
        elif i==dh and j==dw:
            dc=u
        for di in dirs:
            for dj in dirs:
                if di==dj==0:
                    continue
                ni,nj=i+di,j+dj
                if not (0<=ni<h and 0<=nj<w):
                    continue
                v=s[ni][nj]
                if v=='#':
                    continue
                if u!=v:
                    adj[u].add(v)
                    adj[v].add(u)

que=deque()                
que.append(cc)
vis={cc}
m=-1
ok=0
while que:
    m+=1
    for _ in range(len(que)):
        u=que.popleft()
        if u==dc:
            ok=1
            break
        for v in adj[u]:
            if v in vis:
                continue
            vis.add(v)
            que.append(v)
    if ok:
        break

if ok:
    print(m)
else:
    print(-1)

Submission status: Accepted

Solution code:
# import numpy as np
from collections import deque

# 関数化しただけで、実行速度が半分になった部分あり。。。
def solve(): #H, W, CH, CW, DH, DW, S):
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())
	S=[input() for _ in range(H)]

	# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
	S = ['##{}##'.format(row) for row in S]
	S.insert(0, '##{}##'.format('#' * W))
	S.insert(0, '##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	# Cost = np.full((H,W),MAX_COST)

	# print(S)

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	# used = set()
	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 ]
	# print(warp)

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				# print("updl ", i,j,dh,dw,c)
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				# print(h,w,c)
				for i,j in warp:
					dh = h+i
					dw = w+j
					# print(i,j)
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":

	# S=[input() for _ in range(H)]

	solve() #H, W, CH, CW, DH, DW, S)

Submission status: Accepted

Solution code:
# import numpy as np
from collections import deque

def solve(): #H, W, CH, CW, DH, DW, S):
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())
	S=[input() for _ in range(H)]

	# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
	S = ['##{}##'.format(row) for row in S]
	S.insert(0, '##{}##'.format('#' * W))
	S.insert(0, '##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	# Cost = np.full((H,W),MAX_COST)

	# print(S)

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	# used = set()
	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 ]
	# print(warp)

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				# print("updl ", i,j,dh,dw,c)
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				# print(h,w,c)
				for i,j in warp:
					dh = h+i
					dw = w+j
					# print(i,j)
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":

	# S=[input() for _ in range(H)]

	solve() #H, W, CH, CW, DH, DW, S)

Submission status: Accepted

Solution code:
# import numpy as np
from collections import deque

def solve(H, W, CH, CW, DH, DW):#, S):
	# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
	S=[input() for _ in range(H)]
	S = ['##{}##'.format(row) for row in S]
	S.insert(0, '##{}##'.format('#' * W))
	S.insert(0, '##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	# Cost = np.full((H,W),MAX_COST)

	# print(S)

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	# used = set()
	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 ]
	# print(warp)

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				# print("updl ", i,j,dh,dw,c)
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				# print(h,w,c)
				for i,j in warp:
					dh = h+i
					dw = w+j
					# print(i,j)
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())

	# S=[input() for _ in range(H)]

	solve(H, W, CH, CW, DH, DW)#, S)

Submission status: Accepted

Solution code:
# import numpy as np
from collections import deque

def solve(H, W, CH, CW, DH, DW, S):
	# 後の条件分岐を簡略化するためワープしても迷路外に出ないように壁で囲む
	S = ['##{}##'.format(row) for row in S]
	S.insert(0, '##{}##'.format('#' * W))
	S.insert(0, '##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))
	S.append('##{}##'.format('#' * W))


	MAX_COST = 10 ** 9
	Cost=[ [ MAX_COST for _ in range(W+4)] for _ in range(H+4)]
	# Cost = np.full((H,W),MAX_COST)

	# print(S)

	ans = -1

	cost0 = deque()

	cost0.append((CH+1,CW+1,0))
	Cost[CH+1][CW+1] = 0;

	# used = set()
	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 ]
	# print(warp)

	cost1 = deque()

	while cost0:
		h,w,c=cost0.popleft()
		cost1.append((h,w,c))

		for i,j in walk:
			dh = h+i
			dw = w+j
			if S[dh][dw] == '.' and c < Cost[dh][dw]:
				Cost[dh][dw] = c
				# print("updl ", i,j,dh,dw,c)
				cost0.appendleft((dh,dw,Cost[dh][dw]))

		if len(cost0) == 0:

			while cost1:
				h,w,c=cost1.popleft()
				# print(h,w,c)
				for i,j in warp:
					dh = h+i
					dw = w+j
					# print(i,j)
					if S[dh][dw] == '.' and c + 1 < Cost[dh][dw]:
						Cost[dh][dw] = c + 1
						cost0.append((dh,dw,Cost[dh][dw]))


	if Cost[DH+1][DW+1] == MAX_COST:
		print(-1)
	else:
		print(Cost[DH+1][DW+1])


if __name__ == "__main__":
	H,W=map(int,input().split())
	CH,CW=map(int,input().split())
	DH,DW=map(int,input().split())

	S=[input() for _ in range(H)]

	solve(H, W, CH, CW, DH, DW, S)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = [[1 if i=="#" else 0 for i in input()] for _ in range(H)]
    q = [(0, (Ch-1, Cw-1))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch-1][Cw-1] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if ((abs(dh)==1 and dw==0) or (dh==0 and abs(dw)==1)) and costs[hh][ww] > costs[h][w]:
                    costs[hh][ww] = costs[h][w]
                    heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    ans = costs[Dh-1][Dw-1]
    print(ans if ans!=INF else -1)


solve()

Submission status: Accepted

Solution code:
from heapq import heappop, heappush
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())

    l = []
    for _ in range(H):
        s = input()
        l.append([1 if i=="#" else 0 for i in s])

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    q = [(0, (Ch, Cw))]
    INF = 10**12
    costs = [[INF]*W for _ in range(H)]
    costs[Ch][Cw] = 0

    while q:
        cost, pos = heappop(q)
        h, w = pos
        for dh in range(-2, 3):
            for dw in range(-2, 3):
                hh = h+dh
                ww = w+dw
                if not (0<=hh<H and 0<=ww<W):
                    continue
                if l[hh][ww]:
                    continue
                
                if (abs(dh)==1 and abs(dw)==0) or (abs(dh)==0 and abs(dw)==1):
                    if costs[hh][ww] > costs[h][w]:
                        costs[hh][ww] = costs[h][w]
                        heappush(q, (cost, (hh, ww)))
                elif costs[hh][ww] > costs[h][w]+1:
                    costs[hh][ww] = costs[h][w]+1
                    heappush(q, (cost+1, (hh, ww)))

    print(costs[Dh][Dw] if costs[Dh][Dw]!=INF else -1)


solve()

Submission status: Accepted

Solution code:
"""
dp[i][j] => マスi,jに到達するのに必要なワープ回数。
近隣5*5のマスから
"""


def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    H,W = map(int,input().split())
    Ch,Cw = map(int,input().split())
    Ch -= 1
    Cw -= 1
    Dh,Dw = map(int,input().split())
    Dh -= 1
    Dw -= 1
    maze = [list(input()) for _ in range(H)]

    que = deque([(Ch,Cw,0)])
    nxQue = deque([])
    adjecents = [(1,0),(0,1),(-1,0),(0,-1)]
    INF = 10**13
    for _ in range(INF):
        if not que:
            if nxQue:
                que = nxQue
                nxQue = deque([])
                continue
            else:
                break
        h,w,worp = que.popleft()
        if maze[h][w] == "#" or (maze[h][w]!="." and maze[h][w] <= worp):
            continue
        else:
            maze[h][w] = worp
            for a,b in adjecents:
                nxh,nxw = h+a,w+b
                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw]>worp):
                    que.append((nxh,nxw,worp))
                elif 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]=="#":
                    if b == 0:
                        for i in range(a,a*3,a):
                            for j in range(-2,3,1):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
                    else:
                        for i in range(-2,3,1):
                            for j in range(b,b*3,b):
                                nxh,nxw = h+i,w+j
                                if 0<=nxh < H and 0<=nxw < W and maze[nxh][nxw]!="#" and (maze[nxh][nxw]=="." or maze[nxh][nxw] > worp+1):
                                    nxQue.append((nxh,nxw,worp+1))
    
    if maze[Dh][Dw] == "#" or maze[Dh][Dw] == ".":
        print(-1)
    else:
        print(maze[Dh][Dw])
main()

Submission status: Accepted

Solution code:
from collections import defaultdict
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
d = {'#': -1, '.': 0}
ss = [
    list(map(lambda x: d[x], input().rstrip()))
    for i in range(h)
]

canmove = defaultdict(set)

def dfs(c, x, y):
    global ss
    if not (0 <= x < w and 0 <= y < h):
        return
    if ss[y][x] != 0:
        return
    ss[y][x] = c
    dfs(c, x - 1, y)
    dfs(c, x + 1, y)
    dfs(c, x, y - 1)
    dfs(c, x, y + 1)

c = 1
for y in range(h):
    for x in range(w):
        if ss[y][x] == 0:
            dfs(c, x, y)
            c += 1

for y in range(h):
    for x in range(w):
        if ss[y][x] <= 0:
            continue

        for j in range(y - 2, y + 3):
            if not (0 <= j < h):
                continue
            for i in range(x - 2, x + 3):
                if not (0 <= i < w):
                    continue
                if ss[j][i] <= 0:
                    continue
                c1 = ss[y][x]
                c2 = ss[j][i]
                if c1 != c2:
                    canmove[c1].add(c2)
                    canmove[c2].add(c1)

cs = ss[ch][cw]
cd = ss[dh][dw]
if cs == cd:
    print(0)
    exit(0)

q = [cs]
visited = [False] * c
visited[cs] = True
ans = 1
while q:
    nq = []

    for cc in q:
        for cm in canmove[cc]:
            if cm == cd:
                print(ans)
                exit(0)
            if not visited[cm]:
                visited[cm] = True
                nq.append(cm)
    q = nq
    ans += 1
print(-1)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

Submission status: Accepted

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

from collections import deque

INF = 10 ** 12


H, W = map(int, input().split())
s_i, s_j = map(lambda x: int(x) - 1, input().split())
t_i, t_j = map(lambda x: int(x) - 1, input().split())
field = [input() for _ in range(H)]

# 1. bfs でワープなしで到達できるマスを探索
# 2. 1 で見つかったマスから一回ワープして到達できるマスを探索
# 3. 1, 2 を繰り返す


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]

warp_times = [[INF for j in range(W)] for i in range(H)]
que = deque()

warp_times[s_i][s_j] = 0
que.append((s_i, s_j, 0))

while que:
    i, j, times = que.popleft()
    # ワープ無しで到達できるマスの探索
    for di, dj in walk:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times:
                warp_times[i_adj][j_adj] = times
                que.appendleft((i_adj, j_adj, times))

    # ワープ有りで到達できるマスの探索
    for di, dj in warp:
        i_adj, j_adj = i + di, j + dj
        if 0 <= i_adj < H and 0 <= j_adj < W and field[i_adj][j_adj] == '.':
            if warp_times[i_adj][j_adj] > times + 1:
                warp_times[i_adj][j_adj] = times + 1
                # ワープ無しで到達できるマスを探索しきった後に探索するため、単に append
                que.append((i_adj, j_adj, times + 1))

ans = warp_times[t_i][t_j] if warp_times[t_i][t_j] < INF else '-1'
print(ans)

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:
from pprint import pprint
from collections import deque

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

INF=float("inf")

maze=[input() for _ in range(h)]
dist=[[INF]*w for _ in range(h)]

q=deque()
p=[]

dist[ch][cw]=0
q.append((ch,cw))


while q:
    x,y=q.popleft()
    d=dist[x][y]
    for i in range(-2,3):
        for j in range(-2,3):
            if abs(i)+abs(j)==1:
                xx=x+i
                yy=y+j
                if 0<=xx<=h-1 and 0<=yy<=w-1:
                    if maze[xx][yy]==".":
                        if dist[xx][yy]>d:
                            dist[xx][yy]=d
                            q.appendleft((xx,yy))
            if abs(i)+abs(j)>=2:
                xx=x+i
                yy=y+j
                if 0<=xx<=h-1 and 0<=yy<=w-1:
                    if maze[xx][yy]==".":
                        if dist[xx][yy]>d+1:
                            dist[xx][yy]=d+1
                            q.append((xx,yy))
                            
ans=dist[dh][dw]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint
from collections import deque

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

INF=float("inf")

maze=[input() for _ in range(h)]
dist=[[INF]*w for _ in range(h)]

q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0

while q:
    while q:
        x,y=q.popleft()
        # (x,y)は到達訪問済み
        d=dist[x][y]
        for i in range(-2,3):
            for j in range(-2,3):
                # absの和が1、上下左右
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    # 範囲内の時
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        # 道のとき
                        if maze[xx][yy]==".":
                            # 未到達の時
                            # ※非ワープで未到達
                            if dist[xx][yy]>d:
                                # 移動前のdist[x][y]と同じコスト
                                dist[xx][yy]=d
                                q.append((xx,yy))
                # ワープ
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    # 範囲内の時
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        # 道のとき
                        if maze[xx][yy]==".":
                            # 未到達の時
                            if dist[xx][yy]>d+1:
                                # ワープを使うと
                                # 移動前+1する
                                dist[xx][yy]=d+1
                                p.append((xx,yy))

    cur+=1
    q=deque(p)
    p=[]


ans=dist[dh][dw]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from pprint import pprint
from collections import deque
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
INF=float("inf")
maze=[input() for _ in range(h)]
dist=[[INF]*w for _ in range(h)]
q=deque()
p=[]
q.append((ch,cw))
dist[ch][cw]=0
cur=0
# pprint(dist)
# exit()
while q:
    while q:
        x,y=q.popleft()
        # (x,y)は到達訪問済み
        d=dist[x][y]
        for i in range(-2,3):
            for j in range(-2,3):
                # absの和が1、上下左右
                if abs(i)+abs(j)==1:
                    xx=x+i
                    yy=y+j
                    # 範囲内の時
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        # 道のとき
                        if maze[xx][yy]==".":
                            # 未到達の時
                            if dist[xx][yy]>d:
                                # 移動前のdist[x][y]と同じコスト
                                dist[xx][yy]=d
                                q.append((xx,yy))
                # ワープ 
                if abs(i)+abs(j)>=2:
                    xx=x+i
                    yy=y+j
                    if 0<=xx<=h-1 and 0<=yy<=w-1:
                        if maze[xx][yy]==".":
                            if dist[xx][yy]>d+1:
                                dist[xx][yy]=d+1
                                p.append((xx,yy))
                                
   
    cur+=1
    q=deque(p)
    p=[]
            

# pprint(dist)
ans=dist[dh][dw]
if ans==INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H, W = list(map(int, input().split()))
Ch, Cw = list(map(lambda x: int(x) - 1, input().split()))
Dh, Dw = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
maze = [[-1]*W for _ in range(H)]

def walk(h, w, warp_n):
    ans = []
    if maze[h][w] != -1:
        return []
    else:
        maze[h][w] = warp_n
        ans += [(h, w)]
        
    return ans

queue = deque([(Ch, Cw, 0)])
while queue:
    h, w, warp_n = queue.popleft()
    if maze[h][w] != -1:
        continue
    maze[h][w] = warp_n
    # walk
    for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            if not (0 <= h+dh < H and 0 <= w+dw < W):
                continue
            if S[h+dh][w+dw] == '#':
                continue
            queue.appendleft((h+dh, w+dw, warp_n))
    # warp
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if not (0 <= h+dh < H and 0 <= w+dw < W):
                continue
            if S[h+dh][w+dw] == '#':
                continue
            if dh == 0 and dw == 0:
                continue
            queue.append((h+dh, w+dw, warp_n+1))

print(maze[Dh][Dw])

Submission status: Accepted

Solution code:
from collections import deque
h,w = map(int, input().split())
c = tuple(map(int, input().split()))
d = tuple(map(int, input().split()))
m = ['#' for _ in range(h+2)]
m[0] += '#'*w
m[h+1] += '#'*w
que = deque()
que.append(c)
warp = [[10**12 for _ in range(w+1)] for _ in range(h+1)]
for i in range(1,h+1):  m[i] += input()+'#'
up = lambda x,y: 1 if 0<x-1 and m[x-1][y]=='.' else 0
down = lambda x,y: 1 if x+1<=h and m[x+1][y]=='.' else 0
right = lambda x,y: 1 if y+1<=w and m[x][y+1]=='.' else 0
left = lambda x,y: 1 if 0<y-1 and m[x][y-1]=='.' else 0

def jump(x,y,cost):
  deq = deque()
  for i in range(x-2,x+3):
    if i<=0 or h<i:  continue
    for j in range(y-2,y+3):
      if j<=0 or w<j:  continue
      if m[i][j] == '.' and warp[i][j]==10**12:
        warp[i][j] = cost+1
        deq.append((i,j))
  return deq
  
warp[c[0]][c[1]] = 0
while que:
  q = que.popleft()
  row = q[0]
  col = q[1]
  cost = warp[row][col]
  if up(row,col) and warp[row-1][col]>cost:
    que.appendleft((row-1,col))
    warp[row-1][col] = cost
  if down(row,col) and warp[row+1][col]>cost:
    que.appendleft((row+1,col))
    warp[row+1][col] = cost
  if right(row,col) and warp[row][col+1]>cost:
    que.appendleft((row,col+1))
    warp[row][col+1] = cost
  if left(row,col) and warp[row][col-1]>cost:
    que.appendleft((row,col-1))
    warp[row][col-1] = cost
  que.extend(jump(row,col,cost))

if warp[d[0]][d[1]] != 10**12:  print(warp[d[0]][d[1]])
else:  print(-1)

Submission status: Accepted

Solution code:
#-------------------- fast io --------------------
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# ------------------- fast io --------------------

from math import gcd, ceil

def pre(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[j - 1]
        while j and s[i] != s[j]:
            j = pi[j - 1]
        if s[i] == s[j]:
            j += 1
        pi[i] =  j
    return pi

def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)

def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else '0' * (length - len(y)) + y



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

board = []
for i in range(h):
    board += [input()]

from collections import deque
q = deque()
q.append((ch - 1, cw - 1))
ds = [1e9] * (h * w)
ds[(ch - 1) * w + cw - 1] = 0
di = ((1, 0), (0, 1), (-1, 0), (0, -1))
while q:
    r, c = q.popleft()
    for k in di:
        nr, nc = r + k[0], c + k[1]
        if 0 <= nr < h and 0 <= nc < w and board[nr][nc] == '.' and ds[nr * w + nc] > ds[r * w + c]:
            ds[nr * w + nc] = ds[r * w + c]
            q.appendleft((nr, nc))
    for nr in range(r - 2, r + 3):
        for nc in range(c - 2, c + 3):
            if 0 <= nr < h and 0 <= nc < w and board[nr][nc] == '.' and ds[nr * w + nc] > ds[r * w + c] + 1:
                ds[nr * w + nc] = ds[r * w + c] + 1
                q.append((nr, nc))

if ds[(dh - 1) * w + dw - 1] > 1e8:
    print(-1)
else:
    print(ds[(dh - 1) * w + dw - 1])