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
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
Sh,Sw = map(int,input().split())
Sh -= 1
Sw -= 1
Gh,Gw = map(int,input().split())
Gh -= 1
Gw -= 1
S = [list(input()) for _ in range(H)]
D = [[-1 for _ in range(W)] for _ in range(H)]
D[Sh][Sw] = -1


walk = [(1,0),(-1,0),(0,1),(0,-1)]
warp = [(x,y) for x in range(-2,3) for y in range(-2,3) if abs(x) + abs(y) > 1]
def validPosition(h,w):
	return 0 <= h and h < H and 0 <= w and w < W

search = [(0, Sh, Sw)]
V = [[False for _ in range(W)] for _ in range(H)]
while D[Gh][Gw] == -1:
	walked = []
	# walk
	while len(search) > 0:
		(d, h, w) = search.pop()
		if D[h][w] >= 0 and d > D[h][w]:
			continue
		V[h][w] = True
		D[h][w] = d
		walked.append((d,h,w))
		for (x,y) in walk:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and S[hh][ww] == "." and D[hh][ww] == -1:
				search.append((d, hh, ww))
	# warp
	next_search=[]
	for (d,h,w) in walked:
		for (x,y) in warp:
			hh,ww = h+x, w+y
			if validPosition(hh, ww) and not V[hh][ww] and S[hh][ww] == "." and D[hh][ww] == -1:
				V[hh][ww] = True
				next_search.append((d+1, hh, ww))
	if len(next_search) == 0:
		break
	search = next_search

print(D[Gh][Gw])

Submission status: Accepted

Solution code:
from collections import deque

def solve(S, N, H, W, Ch, Cw, Dh, Dw):
    d = deque()
    
    d.append((Ch, Cw))
    count = 0
    uplr = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while d:
        tmp = deque()

        while d:
            h, w = d.pop()
            N[h][w] = count
            if h == Dh and w == Dw:
                return count

            for (dh, dw) in uplr:
                if S[h+dh][w+dw] == '.' and N[h+dh][w+dw] == -1:
                    d.append((h+dh, w+dw))
            
            tmp.append((h, w))
        # print(d, tmp)

        while tmp:
            h, w = tmp.pop()
            for dh in range(-2, 3):
                if dh+h < 1 or dh+h > H:
                    continue
                for dw in range(-2, 3):
                    if dw+w < 1 or dw+w > W:
                        continue
                    if S[h+dh][w+dw] == '.' and N[h+dh][w+dw] == -1:
                        d.append((h+dh, w+dw))

        # print(*S, sep='\n')
        # print(*N, sep='\n')
        # print(d, tmp)

        count += 1
    return -1

def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    wall = '#' * (W+2)
    S = [wall] + ['#' + input() + '#' for i in range(H)] + [wall]

    N = [[-1] * (W+2) for i in range(H+2)]
    # print(*S, sep='\n')
    # print(*N, sep='\n')
    # print(H, W, Ch, Cw, Dh, Dw)
    print(solve(S, N, H, W, Ch, Cw, Dh, Dw))

if __name__ == '__main__':
    main()

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

d = deque()
d.append([ch-1, cw-1])
dist = [[float('inf')] * w for _ in range(h)]
dist[ch-1][cw-1] = 0
while d:
    x, y = d.popleft()
    for i in range(-2, 3):
        for j in range(-2, 3):
            if 0 <= x + i < h and 0 <= y + j < w and s[x+i][y+j] == '.':
                if i == 0 and j == 0:
                    continue
                elif (i == 1 and j == 0) or (i == 0 and j == 1) or (i == -1 and j == 0) or (i == 0 and j == -1):
                    if dist[x+i][y+j] > dist[x][y]:
                        dist[x+i][y+j] = dist[x][y]
                        d.appendleft([x+i, y+j])
                else:
                    if dist[x+i][y+j] > dist[x][y] + 1:
                        dist[x+i][y+j] = dist[x][y] + 1
                        d.append([x+i, y+j])

print(dist[dh-1][dw-1] if dist[dh-1][dw-1] != float('inf') else -1)

Submission status: Accepted

Solution code:
def main():
	inf=10**9
	h,w=map(int,input().split())
	a,b=map(int,input().split())
	c,d=map(int,input().split())
	s=[input() for _ in range(h)]
	cnt=[[inf]*w for _ in range(h)]
	LIS=((-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))
	cnt[a-1][b-1]=0
	new_stack=[(a-1,b-1)]
	for i in range(inf):
		if len(new_stack)==0:
			break
		lis=[]
		stack=new_stack.copy()
		new_stack=[]
		while stack:
			r=stack.pop()
			lis.append(r)
			x,y=r[0],r[1]
			for dx,dy in ((-1,0),(0,1),(1,0),(0,-1)):
				if 0<=x+dx<h and 0<=y+dy<w:
					if s[x+dx][y+dy]=="." and cnt[x+dx][y+dy]==inf:
						cnt[x+dx][y+dy]=i
						stack.append((x+dx,y+dy))
		for x,y in lis:
			for dx,dy in LIS:
				if 0<=x+dx<h and 0<=y+dy<w:
					if s[x+dx][y+dy]=="." and cnt[x+dx][y+dy]==inf:
						cnt[x+dx][y+dy]=i+1
						new_stack.append((x+dx,y+dy))		
	print(cnt[c-1][d-1] if cnt[c-1][d-1]!=inf else -1)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    H,W = LI()
    ch, cw = _LI()
    dh, dw = _LI()
    m = [[0] * W for _ in range(H)]
    for i in range(H):
        s = SI()
        for j in range(W):
            if s[j] == "#":
                m[i][j] = -1

    z = collections.deque()
    z.append((ch,cw,1))
    while z:
        x,y,c = z.popleft()
        if m[x][y]: continue
        q = collections.deque()
        q.append((x,y))
        m[x][y] = c
        r = [(x,y)]
        while q:
            x,y = q.popleft()
            if x == dh and y == dw:
                print(c-1)
                return
            for dx,dy in ((0,1),(1,0),(-1,0),(0,-1)):
                nx = x + dx
                ny = y + dy
                if not(0<= nx < H and 0<= ny < W): continue
                if m[nx][ny]: continue
                m[nx][ny] = c
                q.append((nx,ny))
                r.append((nx,ny))
        for x,y in r:
            for dx in range(-2,3):
                nx = x + dx
                if not(0<= nx < H): continue
                for dy in range(-2,3):
                    ny = y + dy
                    if not(0<= ny < W): continue
                    if m[nx][ny]: continue
                    z.append((nx,ny,c+1))
    print(-1)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque


def main():
    h, w = map(int, input().split())
    c = list(map(lambda x: int(x) - 1, input().split()))
    d = list(map(lambda x: int(x) - 1, input().split()))
    grid = [list(input()) for _ in range(h)]
    q = deque([c])
    max_val = 10 ** 10
    dist = [[max_val for _ in range(w)] for _ in range(h)]
    dist[c[0]][c[1]] = 0
    next_d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
    while q:
        now_x, now_y = q.popleft()
        for dx, dy in next_d:
            nx = now_x + dx
            ny = now_y + dy
            if not (0 <= nx < h and 0 <= ny < w):
                continue
            elif grid[nx][ny] == "#":
                continue
            if dist[nx][ny] > dist[now_x][now_y]:
                dist[nx][ny] = dist[now_x][now_y]
                if [nx, ny] == d:
                    continue
                q.appendleft([nx, ny])
        for dx, dy in [[0, 2], [1, 2], [1, 1], [2, 2], [2, 0], [2, 1]]:
            for cx, cy in [[1, 1], [1, -1], [-1, -1], [-1, 1]]:
                nx = now_x + dx * cx
                ny = now_y + dy * cy
                if not (0 <= nx < h and 0 <= ny < w):
                    continue
                elif grid[nx][ny] == "#":
                    continue
                if dist[nx][ny] > dist[now_x][now_y] + 1:
                    dist[nx][ny] = dist[now_x][now_y] + 1
                    if [nx, ny] == d:
                        continue
                    q.append([nx, ny])
    print(dist[d[0]][d[1]] if dist[d[0]][d[1]] != max_val else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

maze=[list(input()) for _ in range(h)]

from collections import deque
stack = deque([(sy,sx)])
maze[sy][sx]=0

checked=[[0]*w for _ in range(h)]


while len(stack)>0:
    (y,x)=stack.popleft()
    if checked[y][x]==0:
        checked[y][x]=1
        if (y,x)==(gy,gx):
            print(maze[y][x])
            exit()
        for (my,mx) in ((1,0),(0,1),(-1,0),(0,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#" and maze[ny][nx]>maze[y][x]):
                    stack.appendleft((ny,nx))
                    maze[ny][nx]=maze[y][x]
                #ワープ
                elif maze[ny][nx]=="#":
                    ny+=my
                    nx+=mx
                    if 0<=ny<h and 0<=nx<w:
                        if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                            stack.append((ny,nx))
                            maze[ny][nx]=maze[y][x]+1
        #斜めのワープを入れる
        for (my,mx) in ((1,1),(-1,-1),(-1,1),(1,-1)):
            for k in (1,2):
                ny=my*k+y
                nx=mx*k+x
                if 0<=ny<h and 0<=nx<w:
                    if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                        stack.append((ny,nx))
                        maze[ny][nx]=maze[y][x]+1
        for (my,mx) in ((1,2),(-1,-2),(-1,2),(1,-2),(2,1),(-2,-1),(-2,1),(2,-1)):
            ny=my+y
            nx=mx+x
            if 0<=ny<h and 0<=nx<w:
                if maze[ny][nx]=="." or (maze[ny][nx]!="#"  and maze[ny][nx]>maze[y][x]+1):
                    stack.append((ny,nx))
                    maze[ny][nx]=maze[y][x]+1

#for item in maze:
    #print(item)
print(-1)

Submission status: Accepted

Solution code:
import math


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    H, W = read_ints()
    Ch, Cw = read_ints()
    Ch -= 1
    Cw -= 1
    Dh, Dw = read_ints()
    Dh -= 1
    Dw -= 1
    table = []
    for _ in range(H):
        table.append(list(input()))
    costs = [
        [math.inf for _ in range(W)] for _ in range(H)
    ]

    def dfs(points, cost):
        Q = list(points)
        discovered = list(points)
        while Q:
            i, j = Q.pop()
            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < H and 0 <= y < W and table[x][y] == '.' and costs[x][y] == math.inf:
                    costs[x][y] = cost
                    Q.append((x, y))
                    discovered.append((x, y))
        reachables = []
        for x, y in discovered:
            for dx in range(-2, 3):
                for dy in range(-2, 3):
                    new_x, new_y = x+dx, y+dy
                    if 0 <= new_x < H and 0 <= new_y < W and table[new_x][new_y] == '.' and costs[new_x][new_y] == math.inf:
                        costs[new_x][new_y] = cost+1
                        reachables.append((new_x, new_y))
        return reachables

    cost = 0
    Q = [(Ch, Cw)]
    costs[Ch][Cw] = 0
    while Q:
        Q = dfs(Q, cost)
        cost += 1
    if costs[Dh][Dw] == math.inf:
        return -1
    return costs[Dh][Dw]


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import collections, itertools
H, W, ch, cw, dh, dw, *S = open(0).read().split()
H, W, ch, cw, dh, dw = [int(_) + 1 for _ in [H, W, ch, cw, dh, dw]]
H += 3
W += 3
S = ['#' * W] + ['#' * W] + ['##' + s + '##'
                             for s in S] + ['#' * W] + ['#' * W]
Dist = [[None] * W for _ in range(H)]
Q = collections.deque([(0, ch, cw)])
while Q:
    d, ox, oy = Q.popleft()
    if Dist[ox][oy] is not None:
        continue
    stack = [[ox, oy]]
    warp = set()
    while stack:
        x, y = stack.pop()
        if (x, y) == (dh, dw):
            print(d)
            exit()
        Dist[x][y] = d
        for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None:
                if S[nx][ny] == '.':
                    stack += [[nx, ny]]
                else:
                    warp.add((x, y))
    for x, y in warp:
        for dx, dy in itertools.product(range(-2, 3), repeat=2):
            nx, ny = x + dx, y + dy
            if Dist[nx][ny] is None and S[nx][ny] == '.':
                Q += [(d + 1, nx, ny)]
print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(2_000_000)

def solve(H, W, CH, DH, CW, DW, S):
    from collections import deque
    costs = [[float("inf")] * W for _ in range(H)]
    
    def bfs():
        q = deque([(CH-1, CW-1, 0)])
        while q:
            h, w, c = q.popleft()
            if h == (DH-1) and w == (DW-1):
                return c
            if costs[h][w] < c:
                continue
            costs[h][w] = c
            for dh, dw in zip((0, 0, 1, -1), (1, -1, 0, 0)):
                nh, nw = h + dh, w + dw
                if not (0 <= nh < H and 0 <= nw < W):
                    continue
                if S[nh][nw] == "#":
                    continue
                if costs[nh][nw] <= c:
                    continue
                costs[nh][nw] = c
                q.appendleft((nh, nw, c))
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    nh, nw = h + dh, w + dw
                    if not (0 <= nh < H and 0 <= nw < W):
                        continue
                    if S[nh][nw] == "#":
                        continue
                    if costs[nh][nw] <= (c + 1):
                        continue
                    costs[nh][nw] = c+1
                    q.append((nh, nw, c+1))
        return -1
    
    return bfs()

    
# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def 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)]
    print(solve(H, W, CH, DH, CW, DW, S))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
from collections import deque

r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
maze = [list(input()) for i in range(r)]

sy -= 1
sx -= 1
gy -= 1
gx -= 1

# キューを使って解く
# キューはdeque([])で定義し，popleft()で取り出す。

def find_shortest():
    # たどり着くまでにかかった回数をいれる多重リスト。
    d = [[float("inf")] * c for i in range(r)]
    # 1ノード降りるときにforで回せるようリスト化しておく
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    ddx = [-2,-2,-2,-2,-2,-1,-1,-1,-1,0,0,1,1,1,1,2,2,2,2,2]
    ddy = [2,1,0,-1,-2,2,1,-1,-2,2,-2,2,1,-1,-2,2,1,0,-1,-2]

    # 接したポイントを取り込む用のqueを定義
    que = deque([])
    queq = deque([])
    # スタート地点をqueに加える。探索の際はqueから取り出すループを回すので最初だけ先に入れておく
    que.append((sy,sx))
    queq.append((sy,sx))
    # スタートからスタートにかかる距離は0なのでinfを0にかえる。
    d[sy][sx] = 0


    while que or queq:

        # queがあるかぎり続ける
        while que:
            # queから座標を取り出す。
            p = que.popleft()
            queq.append(p)
            # 取り出した点がゴールなら終了
            if p[0] == gy and p[1] == gx:
                key = 1
                break
            #　それ以外の時は，接している点を4方向順に取得。一つずつ処理する。
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                # 新しく取得した座標に対しての処理
                # 迷路内に存在する座標であり，壁ではなく，まだ通ったことがなくdがinfの点なら処理する = 新しく取得した道候補の1つ
                if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 道候補をqueに加える。
                    que.append((nx, ny))
                    # その道候補への経路までにかかった経路は加えなくて良い。
                    d[nx][ny] = d[p[0]][p[1]]
        while queq:
            p = queq.popleft()
            #　ワープを使う。
            for i in range(20):
                nx = p[0] + ddx[i]
                ny = p[1] + ddy[i]

                # 新しく取得した座標に対しての処理
                # 迷路内に存在する座標であり，壁ではなく，まだ通ったことがなくdがinfの点なら処理する = 新しく取得した道候補の1つ
                if 0 <= nx < r and 0 <= ny < c and maze[nx][ny] != "#" and d[nx][ny] == float("inf"):
                    # 道候補をqueに加える。
                    que.append((nx, ny))
                    # その道候補への経路までにかかった経路は加える。
                    d[nx][ny] = d[p[0]][p[1]]+1
    if d[gy][gx] != float('inf'):
        return d[gy][gx]
    else:
        return -1

ans = find_shortest()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W = list(map(int,input().split()))
Ch,Cw = list(map(int,input().split()))
Dh,Dw = list(map(int,input().split()))

maze = [["#"]*(W+4)]
maze.append(["#"]*(W+4))
for i in range(H):
    row = ["#","#"]
    row.extend(list(input()))
    row.append("#")
    row.append("#")
    maze.append(row)
maze.append(["#"]*(W+4))
maze.append(["#"]*(W+4))
warp = [[114514]*(W+4) for i in range(H+4)]

queue = deque()
queue.append((Ch+1,Cw+1))
warp[Ch+1][Cw+1] = 0
move_one = set(((1,0),(0,1),(-1,0),(0,-1)))
while queue:
    y,x = queue.popleft()
    for i in range(-2,3):
        for j in range(-2,3):
            if i == 0 and j == 0:
                maze[ny][nx] = "#"
                continue
            ny,nx = y+i,x+j
            if maze[ny][nx] == "#":
                continue
            if (i,j) in move_one:
                warp[ny][nx] = warp[y][x]
                queue.appendleft((ny,nx))
                maze[ny][nx] = "#"
            else:
                if warp[ny][nx] == 114514:
                    warp[ny][nx] = warp[y][x]+1
                    queue.append((ny,nx))

if warp[Dh+1][Dw+1] == 114514:
    print(-1)
else:
    print(warp[Dh+1][Dw+1])

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
H, W = map(int, input().split())
Cy, Cx = map(int, input().split())
Dy, Dx = map(int, input().split())
M = [['#']*(W+4)]+[['#']*(W+4)]+[['#','#'] + list(input()) + ['#','#'] for _ in range(H)]+[['#']*(W+4)]+[['#']*(W+4)]

num_groups = 0
for y in range(2, H+2):
    L = M[y]
    for x in range(2, W+2):
        if L[x] == '.':
            q = [[y, x]]
            while q:
                ty, tx = q.pop()
                M[ty][tx] = num_groups
                if M[ty-1][tx] == '.':
                    q.append([ty-1, tx])
                if M[ty+1][tx] == '.':
                    q.append([ty+1, tx])
                if M[ty][tx-1] == '.':
                    q.append([ty, tx-1])
                if M[ty][tx+1] == '.':
                    q.append([ty, tx+1])
            num_groups += 1 

ds = [[-2,0], [-2,1], [-1,1], [-2,2], [-1,2], [2,0], [1,1], [2,1], [0,2], [1,2], [2,2]]
edges = dd(dict)
for y in range(2, H+2):
    for x in range(2, W+2):
        f = M[y][x]
        if f != '#':
            for dy, dx in ds:
                t = M[y+dy][x+dx]
                if t != '#' and f != t:
                    edges[f][t] = edges[t][f] = 1

start = M[Cy+2-1][Cx+2-1]
goal = M[Dy+2-1][Dx+2-1]
q = set([start])
visited = [False] * num_groups
visited[start] = True
ans = 0
while q:
    nq = set()
    for p in q:
        if p == goal:
            print(ans)
            exit()
        for t in edges[p].keys():
            if not visited[t]:
                nq.add(t)
                visited[t] = True
    q = nq
    ans += 1

print(-1)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 20
# MOD = 10 ** 9 + 7
MOD = 998244353

ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))


# ===CODE===

def main():
    h, w = ns()
    ch, cw = ns()
    ch, cw = ch - 1, cw - 1
    dh, dw = ns()
    dh, dw = dh - 1, dw - 1

    map = [list(input()) for _ in range(h)]

    table = [[-1 for _ in range(w)] for __ in range(h)]
    group = {}

    pos = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    cnt = -1
    for i in range(h):
        for j in range(w):
            if map[i][j] == "." and table[i][j] == -1:
                cnt += 1
                group[cnt] = [[i, j]]
                que = collections.deque()
                que.append([i, j])
                table[i][j] = cnt

                while que:
                    y, x = que.popleft()
                    for py, px in pos:
                        ty = y + py
                        tx = x + px
                        if 0 <= ty < h and 0 <= tx < w:
                            if map[ty][tx] == "." and table[ty][tx] == -1:
                                table[ty][tx] = cnt
                                que.append([ty, tx])
                                group[cnt].append([ty, tx])

    ini_group = table[ch][cw]
    req_group = table[dh][dw]
    done_group = set()
    done_group.add(ini_group)

    nxt = {ini_group}
    ans = 0

    while len(nxt):
        if req_group in done_group:
            break

        tmp = []
        for nxti in nxt:
            tmp.extend(group[nxti])
        que = collections.deque(tmp)

        nxt = set()
        for _ in range(len(que)):
            y, x = que.popleft()
            for py in range(-2, 3):
                for px in range(-2, 3):
                    if i == 0 and j == 0:
                        continue
                    ty = y + py
                    tx = x + px
                    if 0 <= ty < h and 0 <= tx < w:
                        if table[ty][tx] != -1 and table[ty][tx] not in done_group:
                            nxt.add(table[ty][tx])
                            done_group.add(table[ty][tx])

        ans += 1

    print(ans if req_group in done_group else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

def bfs(sx, sy, gx, gy):
    dist = [[-1] * w for _ in range(h)]
    dist[sx][sy] = 0
    q = deque()
    r = deque()
    q.append([sx, sy])
    while True:
        if not q:
            while r:
                x, y = r.popleft()
                for i in range(-2, 3):
                    for j in range(-2, 3):
                        xx, yy = x + i, y + j
                        if 0 <= xx < h and 0 <= yy < w:
                            if s[xx][yy] == "." and dist[xx][yy] == -1:
                                dist[xx][yy] = dist[x][y] + 1
                                q.append([xx, yy])
        if not q:
            return dist[gx][gy]
        x, y = q.popleft()
        r.append([x, y])
        for u in v:
            xx, yy = x + u[0], y + u[1]
            if 0 <= xx < h and 0 <= yy < w:
                if s[xx][yy] == "." and dist[xx][yy] == -1:
                    dist[xx][yy] = dist[x][y]
                    q.append([xx, yy])
    return dist[gx][gy]

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)]
v = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = bfs(ch - 1, cw - 1, dh - 1, dw - 1)
print(ans)

Submission status: Accepted

Solution code:
from collections import *
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=[input() for i in range(H)]
Q=deque()
INF=10**9
D=[[INF]*W for i in range(H)]
D[CH][CW]=0
Q.append((CH,CW))
w4x=[[0,1,0,-1],[]]
w4y=[[1,0,-1,0],[]]
for i in range(5):
  for j in range(5):
    if abs(i-2)+abs(j-2)<=1:
      continue
    w4x[1].append(i-2)
    w4y[1].append(j-2)
v=0
w=0
d=0
while len(Q):
  v=Q.popleft()
  for j in range(2):
    for i in range(len(w4x[j])):
      w=(v[0]+w4y[j][i],v[1]+w4x[j][i])
      if min(w)<0 or w[0]>=H or w[1]>=W:
        continue
      if S[w[0]][w[1]]=='#':
        continue
      d=D[v[0]][v[1]]+j
      if D[w[0]][w[1]]>d:
        D[w[0]][w[1]]=d
        if j:
          Q.append(w)
        else:
          Q.appendleft(w)
if D[DH][DW]==INF:
  print(-1)
else:
  print(D[DH][DW])

Submission status: Accepted

Solution code:
INF = 10**18

def main():

    h, w = map(int, input().split())
    ch, cw = map(int, input().split())
    dh, dw = map(int, input().split())
    ch, cw = ch-1, cw-1
    dh, dw = dh-1, dw-1
    #M = [list(str(input())) for _ in range(h)]

    M = [str(input()) for _ in range(h)]
    #M = ['#'*w] + M + ['#'*w]
    #M = ['#'+c+'#' for c in M]

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

    visit = [[-1]*w for _ in range(h)]
    visit[ch][cw] = 0
    C = [[INF]*w for _ in range(h)]
    C[ch][cw] = 0

    import itertools
    cnt = 0
    while q:
        y, x = q.popleft()
        #if y == dh and x == dw:
            #break
        for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
            ny, nx = y+dy, x+dx
            if 0 <= ny < h and 0 <= nx < w:
                #C[ny][nx] = min(C[y][x], C[ny][nx])
                if C[ny][nx] != C[y][x] and M[ny][nx] != '#':
                    visit[ny][nx] = visit[y][x]
                    C[ny][nx] = min(C[y][x], C[ny][nx])
                    q.appendleft((ny, nx))
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0:
                    continue
                ny, nx = y+dy, x+dx
                if 0 <= ny < h and 0 <= nx < w:
                    #C[ny][nx] = min(C[y][x]+1, C[ny][nx])
                    if visit[ny][nx] == -1 and M[ny][nx] != '#':
                        visit[ny][nx] = visit[y][x]
                        C[ny][nx] = min(C[y][x]+1, C[ny][nx])
                        q.append((ny, nx))
    #print(visit)
    #print(C)
    if visit[dh][dw] == -1:
        print(-1)
    else:
        print(C[dh][dw])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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
S = [0]*H
hoge = 0
for i in range(H):
    S[i] = [-1]*W
    hoge = input()
    for j in range(W):
        if hoge[j] == ".":
            S[i][j] = 10000000

DDD = [0]*25
dddd = 0
for dx in (-2,-1,0,1,2):
    for dy in (-2,-1,0,1,2):
        DDD[dddd] = (dx,dy,dx * dx + dy * dy)
        dddd += 1

D = deque()
D.append((CH,CW,0))
S[CH][CW] = 0
while len(D):
    X,Y,DD = D.pop()
    for dx,dy,a in DDD:
        XX = X + dx
        YY = Y + dy
        if a == 0 or not(0<=XX<H) or not(0<=YY<W) or S[XX][YY] == -1:
            continue
        elif a == 1 and S[XX][YY] > DD:
            D.append((XX,YY,DD))
            S[XX][YY] = DD
        elif S[XX][YY] > DD + 1:
            D.appendleft((XX,YY,DD+1))
            S[XX][YY] = DD + 1

print(-1 if S[DH][DW] == 10000000 else S[DH][DW])

Submission status: Accepted

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

S = ['#'*(W+4)]*(H+4)
for h in range(2, H+2):
    S[h] = '##' + input() + '##'

T = [[-1]*(W+4) for _ in range(H+4)]

f = 0
for h in range(2,H+2):
    for w in range(2,W+2):
        if S[h][w]=='#' or T[h][w]!=-1: continue
        
        queue = [(h,w)]
        iq = 0
        while iq<len(queue):
            ph, pw = queue[iq]
            iq += 1

            if S[ph][pw]=='#' or T[ph][pw]!=-1: continue
            
            T[ph][pw] = f
            queue.append((ph+1,pw  ))
            queue.append((ph-1,pw  ))
            queue.append((ph  ,pw+1))
            queue.append((ph  ,pw-1))

        f += 1

P = [set() for _ in range(f)]
    
for h in range(2,H+2):
    for w in range(2,W+2):
        f = T[h][w]
        if f==-1: continue
        for h2 in range(h-2, h+3):
            for w2 in range(w-2, w+3):
                f2 = T[h2][w2]
                if f2==-1: continue
                if f!=f2: P[f].add(f2)

N = [-1]*len(P)
queue = [(T[Ch+1][Cw+1], 0)]
iq = 0
while iq<len(queue):
    f, n = queue[iq]
    iq += 1

    if N[f]!=-1: continue

    N[f] = n
    for f2 in P[f]: queue.append((f2, n+1))

print(N[T[Dh+1][Dw+1]])