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

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

def main():

    ##########################################
    import heapq
    class Dijkstra():
        """
        ・有向 / 無向は問わない(無向の場合は，逆向きの辺もたす)
        ・負のコストがない場合のみ
        ・計算量はO(E log|V|)　
        ・heapを使うことで頂点を走査する必要がなくなる（代わりに，距離更新したものは確定でなくともqueに入れておく）
        ・復元なし
        """

        #最短のpathをたす


        class Edge():
            #重み付き有向辺

            def __init__(self, _to, _cost):
                self.to =_to
                self.cost = _cost

        def __init__(self, V):
            #引数Vは頂点数
            self.inf=10**20
            self.G = [[] for _ in range(V)] #隣接リストG[u][i]が頂点uのi番目の辺
            self. _E = 0 #辺の数
            self._V = V #頂点数

        #proparty - 辺の数
        def E(self):
            return self._E

        #proparty - 頂点数
        def V(self):
            return self._V

        def add(self, _from, _to, _cost):
            #2頂点と辺のコストを追加
            self.G[_from].append(self.Edge(_to,_cost))
            self._E +=1

        def add2(self, _from, _to, _cost):
            #2頂点と辺のコスト（無向）を追加
            self.G[_from].append(self.Edge(_to, _cost))
            self.G[_to].append(self.Edge(_from, _cost))
            self._E +=2

        def shortest_path(self,s):#,g):
            #始点sから頂点iまでの最短経路長のリストを返す
            que = [] #priority queue
            d = [self.inf] * self.V()

            #prev = [None]*self.V() #prev[j]は，sからjへ最短経路で行くときのjの一つ前の場所
            #復元で使う

            d[s] = 0
            heapq.heappush(que,(0,s)) #始点の距離と頂点番号をヒープに追加

            while len(que)!=0:
                #キューに格納されてある中で一番コストが小さい頂点を取り出す
                cost,v = heapq.heappop(que)

                #キューに格納された最短経路長候補がdの距離よりも大きい場合に処理をスキップ
                if d[v] < cost:
                    continue

                #頂点vに隣接する各頂点iに対して，vを経由した場合の距離を計算して，これがd[i]よりも小さい場合に更新
                for i in range(len(self.G[v])):
                    e = self.G[v][i] #vのi個目の隣接辺
                    if d[e.to] > d[v] + e.cost:
                        d[e.to] = d[v] + e.cost #更新

                        #prev[e.to] = v
                        #復元で使う

                        heapq.heappush(que,(d[e.to],e.to)) #queに新たな最短経路長候補を追加

            """#sからgまでの最短経路
            path = []
            pos = g #今いる場所，ゴールで初期化
            for _ in range(self.V()+1):
                path.append(pos)
                if pos == s:
                    break
                #print("pos:",format(pos))
                pos = prev[pos]
            path.reverse()
            #print(path)"""

            return d#,path
    ########################
    ################
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots():全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            #根を探す&つなぎかえる
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

            if self.parents[x] > self.parents[y]:
                x, y = y, x

            self.parents[x] += self.parents[y]
            self.parents[y] = x

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            return {r: self.members(r) for r in self.roots()}

        def __str__(self):
            return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

    ################


    mod=10**9+7
    H,W=MI()
    ch,cw=MI()
    dh,dw=MI()
    ch+=1
    cw+=1
    dh+=1
    dw+=1
    
    S=[]
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    for i in range(H):
        s=["#"]*2 + list(input()) + ["#"]*2
        S.append(s)
    S.append(["#"]*(W+4))
    S.append(["#"]*(W+4))
    
    
    dx=[0,0,1,-1]
    dy=[1,-1,0,0]
    
    dx2=[-2,-2,-2,-2,-2,  -1,-1,-1,-1,   0,0,   1, 1,1,1,   2, 2,2,2,2]
    dy2=[-2,-1, 0, 1, 2,  -2,-1, 1, 2,  -2,2,  -2,-1,1,2,  -2,-1,0,1,2]
    
    uf=UnionFind((W+4)*(H+4))
    
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j]==".":
                for k in range(4):
                    ii=i+dx[k]
                    jj=j+dy[k]
                    if S[ii][jj]==".":
                        fro=i*(W+4)+j
                        to=ii*(W+4)+jj
                        uf.union(fro,to)
    
    roots=[[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if S[i][j]==".":
                now=i*(W+4)+j
                root=uf.find(now)
                roots[i][j]=root
                
    roots_uf=uf.roots()
    from collections import defaultdict
    dd = defaultdict(int)
    
    cur=0
    for v in roots_uf:
        dd[v]=cur
        cur+=1
    
    djk=Dijkstra(len(roots_uf))
                
                
    for i in range(2,H+2):
        for j in range(2,W+2):
            if S[i][j]==".":
                for k in range(20):
                    ii=i+dx2[k]
                    jj=j+dy2[k]
                    if S[ii][jj]==".":
                        fro=roots[i][j]
                        to=roots[ii][jj]
                        if fro!=to:
                            djk.add(dd[fro],dd[to],1)
                            
    
    s=dd[roots[ch][cw]]
    g=dd[roots[dh][dw]]
    D=djk.shortest_path(s)
    ans=D[g]
    if ans>=10**6+5:
        ans=-1
    print(ans)                
    
    
                

main()

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def toi(h,w):
	return h*10000 + w
	
def fromi(v):
	return v//10000, v%10000

def main():
	#a = int(input())
	h, w = tin()
	#s = input()
	ch, cw = tin()
	start_h,start_w = ch-1,cw-1
	dh,dw = tin()
	goal_h, goal_w=dh-1, dw-1
	ll=[input() for _ in range(h)]
	pll=[[-1]*w for _ in range(h)]
	egg = [[] for _ in range(w*h)]
	
	mark=-1
	for hi in range(h):
		for wi in range(w):
			if ll[hi][wi]=='#':
				continue
			if pll[hi][wi] >= 0:
				continue
			mark+=1
			qq=collections.deque()
			qq.append(toi(hi,wi))
			open_list=set()
			open_list.add(toi(hi,wi))
			while len(qq)>0:
				nv = qq.popleft()
				nh, nw = fromi(nv)
				pll[nh][nw] = mark
				for dh,dw in [[1,0], [-1,0], [0,1], [0,-1]]:
					if nh + dh < 0 or nh + dh >= h:
						continue
					if nw + dw < 0 or nw + dw >= w:
						continue
					if toi(nh+dh,nw+dw) in open_list:
						continue
					if ll[nh + dh][nw+dw]=='#':
						egg[mark].append([nh,nw,dh,dw])
						continue
					if pll[nh + dh][nw+dw] > 0:
						continue
					qq.append(toi(nh + dh, nw+dw))
					open_list.add(toi(nh+dh,nw+dw))
					
	#print(pll)
	if pll[start_h][start_w] == pll[goal_h][goal_w]:
		return 0
	#for l in egg:	
	#	print(l)
	
	qqq=collections.deque()
	qqq.append((pll[start_h][start_w],0))
	g_pos=pll[goal_h][goal_w]
	open_list=set()
	open_list.add(-1)
	#pa('tttt')
	while len(qqq)>0:
		pos, cost = qqq.popleft()
		if pos == g_pos:
			return cost
		for [nh,nw,_h,_w] in egg[pos]:
			for dh in [-2,-1,0,1,2]:
				for dw in [-2,-1,0,1,2]:
					nnh = nh + dh
					nnw = nw + dw
					if nnh < 0 or nnh >= h:
						continue
					if nnw < 0 or nnw >= w:
						continue
					vv = pll[nnh][nnw]
					if vv in open_list:
						continue
					qqq.append((vv, cost+1))
					open_list.add(vv)
					#pa((vv,g_pos))
		
	return -1
		
		
			
		
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

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

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

s=[]
for i in range(h):
    sub=input().rstrip()
    s.append(sub)

check=[[-1]*w for i in range(h)]
stack=[(ch-1,cw-1)]
check[ch-1][cw-1]=0
d=[(1,0),(-1,0),(0,1),(0,-1)]


count=0

while True:
    temp=[]
    while len(stack)>0:
        now=stack.pop()
        temp.append(now)
        for i in d:
            x=now[0]+i[0]
            y=now[1]+i[1]
            if 0<=x<=h-1 and 0<=y<=w-1:
                if s[x][y]=='.':
                    if check[x][y]==-1:
                        check[x][y]=count
                        stack.append((x,y))

    count+=1
    for k in temp:
        for i in range(-2,3):
            for j in range(-2,3):
                x=k[0]+i
                y=k[1]+j
                if 0 <= x <= h - 1 and 0 <= y <= w - 1:
                    if s[x][y] == '.':
                        if check[x][y] == -1:
                            check[x][y]=count
                            stack.append((x,y))
    if len(stack)==0:
        break

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

Submission status: Accepted

Solution code:
import sys
from collections import deque, defaultdict

sys.setrecursionlimit(10000)

H, W = map(int, input().split())
C = tuple(map(int, input().split()))
D = tuple(map(int, input().split()))
S = [list(input()) for _ in range(H)]

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

def dfs(h, w, i):
    S[h][w] = i

    for dh, dw in d:
        nh = h + dh
        nw = w + dw
        if nh < 0 or nh >= H or nw < 0 or nw >= W:
            continue
        if S[nh][nw] != '.':
            continue
        dfs(nh, nw, i)

# 番号を振る
count = 1
for h in range(H):
    for w in range(W):
        if S[h][w] != '.':
            continue
        dfs(h, w, count)
        count += 1

# グラフを構築
graph = {}
for i in range(1, count):
    graph[i] = set()

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue

        for dh in range(-2, 3):
            for dw in range(-2, 3):
                nh = h + dh
                nw = w + dw
                if nh < 0 or nh >= H or nw < 0 or nw >= W:
                    continue
                if S[nh][nw] == '#':
                    continue
                graph[S[h][w]].add(S[nh][nw])

start = S[C[0]-1][C[1]-1]
goal = S[D[0]-1][D[1]-1]

# 最短経路を求める
def bfs(start, goal):
    queue = deque([start])
    visited = set()
    visited.add(start)
    dist = defaultdict(int)
    dist[start] = 0
    while queue:
        current_vertex = queue.popleft()
        for v in graph[current_vertex]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                dist[v] = dist[current_vertex] + 1
    return dist[goal] if goal in dist else -1

ans = bfs(start, goal)

print(ans)

Submission status: Accepted

Solution code:
import heapq
import sys


def input(): return sys.stdin.readline().rstrip()


H, W = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
data = [[0]*W for i in range(H)]

for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == ".":
            data[i][j] = 1
        else:
            data[i][j] = 0


def trans(h, w):
    return W*(h) + w


P = [(0, -1), (0, 1), (1, 0), (-1, 0)]
DXY = []
for i in range(0, 3):
    for j in range(-2, 3):
        if i==0 and j==0:
            pass
        else:
            DXY.append((i,j))
            
G = [[] for i in range(H*W)]
H_L = [i for i in range(H)]
W_L = [i for i in range(W)]
for i in H_L:
    for j in W_L:
        if data[i][j] == 1:
            for dx, dy in P:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 0))
                        G[v].append((u, 0))
            for dx, dy in DXY:
                if 0 <= dx+i < H and 0 <= dy+j < W and data[dx+i][dy+j] == 1:
                        u, v = trans(i, j), trans(dx+i, dy+j)
                        G[u].append((v, 1))
                        G[v].append((u, 1))


D = [10**6+100 for i in range(H*W)]
D[trans(ch-1, cw-1)] = 0
que = []
heapq.heapify(que)
heapq.heappush(que, (0, trans(ch-1, cw-1)))

while que:
    cost, v = heapq.heappop(que)
    if D[v] < cost:
        continue
    for node, cost in G[v]:
        if D[node] > D[v] + cost:
            D[node] = D[v] + cost
            heapq.heappush(que, (D[node], node))

ans = D[trans(dh-1, dw-1)]

if ans == 10**6+100:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappop, heappush

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

a = [(-1, 0), (1, 0), (0, -1), (0, 1)]
b = [(i % 5 - 2, i // 5 - 2) for i in range(25) if (i % 5 - 2, i // 5 - 2) not in a]

d = [[H * W] * W for _ in range(H)]
d[Ch][Cw] = 0
Q = [(0, Ch, Cw)]
while Q:
    now_d, h, w = heappop(Q)
    if now_d > d[h][w]:
        continue
    if (h, w) == (Dh, Dw):
        break
    for ah, aw in a:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w]:
                d[nh][nw] = d[h][w]
                heappush(Q, (d[nh][nw], nh, nw))
    for ah, aw in b:
        nh, nw = h + ah, w + aw
        if 0 <= nh < H and 0 <= nw < W and S[nh][nw] == ".":
            if d[nh][nw] > d[h][w] + 1:
                d[nh][nw] = d[h][w] + 1
                heappush(Q, (d[nh][nw], nh, nw))

if d[Dh][Dw] == H * W:
    ans = -1
else:
    ans = d[Dh][Dw]
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
import sys, copy, itertools
input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
#SUBMAP =[['#']+['#']+list(input().rstrip())+['#']+['#'] for i in range(h)]
#MAP = [['#']*(w+4)] +[['#']*(w+4)]+SUBMAP+[['#']*(w+4)]+[['#']*(w+4)]
MAP =[list(input().rstrip()) for i in range(h)]
#print(MAP)

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

MOVE = [[1,0],[-1,0],[0,1],[0,-1]]
JUMP = [[-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]]
STACK = deque([(ch,cw)])
STACKX = deque([(ch,cw)])
#print(STACKX)

ans = -1 #見つからなかった場合
MAP[ch][cw]=0
#print(MAP)

while STACKX:
  
  while STACK:
    y, x = STACK.popleft()
    for dy,dx in MOVE:
      ny = y + dy
      nx = x + dx
      if not(0 <= ny < h) or not(0 <= nx < w) or MAP[ny][nx]!='.':
        STACKX.append((y,x))
        continue
      else:
        STACK.append((ny,nx))
        MAP[ny][nx] = MAP[y][x]
   
  #print(MAP)
  if MAP[dh][dw] != '.':
    ans = MAP[dh][dw]
  
  #print(STACKX)
  yy, xx = STACKX.popleft()
  for dyy,dxx in JUMP:
    nyy = yy + dyy
    nxx = xx + dxx
    if not(0 <= nyy < h) or not(0 <= nxx < w) or MAP[nyy][nxx]!='.':
      continue
    else:
      STACK.append((nyy,nxx))
      MAP[nyy][nxx] = MAP[yy][xx] + 1


      
      
#print(MAP)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

h,w = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
b = read().split()

sh -= 1; sw -= 1; gh -= 1; gw -= 1

#print(b)

from collections import deque

def nbd(nh,nw,dv):
    if dv < res[nh][nw]:
        res[nh][nw] = dv
        q.appendleft((dv,nh,nw))
    return 




INF = 1<<30
res = [[INF]*w for _ in range(h)] #startからの最短距離
res[sh][sw] = 0
q = deque([(0,sh,sw)]) #(そこまでの距離、点)
while q:
    dv,vh,vw = q.popleft()
    if res[vh][vw] < dv: continue
    if vh==gh and vw==gw: break
    
    if vh and b[vh-1][vw]==".":
        nbd(vh-1,vw,dv)
    if vw and b[vh][vw-1]==".":
        nbd(vh,vw-1,dv)
    if vh+1<h and b[vh+1][vw]==".":
        nbd(vh+1,vw,dv)
    if vw+1<w and b[vh][vw+1]==".":
        nbd(vh,vw+1,dv)
    
    for i in range(-2,3):
        nh = vh+i
        if nh < 0 or nh >= h: continue
        for j in range(-2,3):
            nw = vw + j
            if nw < 0 or nw >= w: continue
            if abs(i)+abs(j) > 1:
                if b[nh][nw] == "." and dv+1 < res[nh][nw]:
                    res[nh][nw] = dv+1
                    q.append((dv+1,nh,nw))


ans = res[gh][gw]
if ans != INF:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H,W = map(int,input().split())
INF = 1000000
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
maze = []
maze.append(['#']*(W+2))
for i in range(H):
    maze.append(['#']+list(input())+['#'])
maze.append(['#']*(W+2))
dis = [[INF]*(W+2) for _ in range(H+2)]
d = deque()
nextd = []
dis[Ch][Cw] = 0
d.append((Ch,Cw))
dy = [0,1,0,-1]
dx = [1,0,-1,0]
cur = 0
while d:
    while d:
        y,x = d.popleft()
        if dis[y][x] == cur:
            for i in range(4):
                newy = y+dy[i]
                newx = x+dx[i]
                if maze[newy][newx] == '.':
                    if dis[newy][newx] > cur:
                        dis[newy][newx] = cur
                        d.append((newy,newx))
            for DY in range(-2,3):
                for DX in range(-2,3):
                    if abs(DX)+abs(DY) >= 2:
                        newy = y+DY
                        newx = x+DX
                        if newy <= H and newy >= 1 and newx <= W and newx >= 1: 
                            if maze[newy][newx] == '.':
                                if dis[newy][newx] > cur+1:
                                    dis[newy][newx] = cur+1
                                    nextd.append((newy,newx))
    cur += 1
    d = deque(nextd)
    nextd = []
if dis[Dh][Dw] == INF:
    print(-1)
else:
    print(dis[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())

edge = [["#" for _ in range(W+2)]]
center = [["#"] + list(input()) + ["#"] for i in range(H)]
A_array = edge + center + edge

#セルをグループ毎に分割
cells_grouped = dict()
group_no = 1

edge = [[1 for _ in range(W+2)]]
center = [[1] + [0 for _ in range(W+2)] + [1] for i in range(H)] #提出用
is_visited = edge + center + edge

edge = [[0 for _ in range(W+2)]]
center = [[0] + [0 for _ in range(W+2)] + [0] for i in range(H)] #提出用
cell_group_dict = edge + center + edge

for i in range(1,H+1):
    for j in range(1,W+1):
        #print(i,j,A_array[i][j])
        if is_visited[i][j] == 0:
            is_visited[i][j] = 1
            
            if A_array[i][j] == ".":
                #function 幅優先探索(v)
                search_target_deque = deque() #    Q ← 空のキュー
                search_target_deque.append((i,j)) #    v を Q に追加
                grouped_cells = set()
                grouped_cells.add((i,j))

                while len(search_target_deque) != 0: #    while Q が空ではない do
                    m,n = search_target_deque.popleft() #        v ← Q から取り出す
                    #        v を処理する
                    cell_group_dict[m][n] = group_no
                    neighbor_nodes = [(m+1,n),(m-1,n),(m,n+1),(m,n-1)]
                    for s,t in neighbor_nodes: #        for each v に接続している頂点 i do
                        if is_visited[s][t] == 0: # if i が未訪問 then
                            is_visited[s][t] = 1 #                iに訪問済みの印を付ける
                            if A_array[s][t] == ".":
                                search_target_deque.append((s,t)) #                i を Q に追加
                                grouped_cells.add((s,t))

                cells_grouped[group_no] = grouped_cells
                group_no += 1

                
#print("cells_grouped")
#print(cells_grouped)

#print("cell_group_dict")
#print(cell_group_dict)
                
#各グループから行けるグループを得る
warpable_group = {i:set() for i in range(group_no)}
for i in range(1,group_no):
    for cell in cells_grouped[i]:
        y = cell[0]
        x = cell[1]
        for m in range(y-2,y+3,1):
            if 1<=m<=H:
                for n in range(x-2,x+3,1):
                    if 1<=n<=W and cell_group_dict[m][n]!=0 and cell_group_dict[m][n]!=group_no:
                        warpable_group[i].add(cell_group_dict[m][n])

#print("warpable_group")
#print(warpable_group)

#function 幅優先探索(v)
distance_from_start = ["?" for i in range(group_no)] #startからの距離
is_visited = [0 for i in range(group_no)] #訪問フラグ

v = cell_group_dict[Ch][Cw]

search_target_deque = deque() #    Q ← 空のキュー
is_visited[v] = 1 #    v に訪問済みの印を付ける
search_target_deque.append(v) #    v を Q に追加
distance_from_start[v] = 0

while len(search_target_deque) != 0: #    while Q が空ではない do
    node = search_target_deque.popleft() #        v ← Q から取り出す
    #        v を処理する
    if node == cell_group_dict[Dh][Dw]:
        print(distance_from_start[node])
        break
    
    near_nodes = warpable_group[node]
    
    for near_node in near_nodes: #        for each v に接続している頂点 i do

        if is_visited[near_node] == 0: #            if i が未訪問 then
            is_visited[near_node] = 1 #                i に訪問済みの印を付ける
            search_target_deque.append(near_node) #                i を Q に追加
            distance_from_start[near_node] = distance_from_start[node] + 1
else:
    print(-1)

Submission status: Accepted

Solution code:
from collections import deque
from collections import defaultdict
# input = sys.stdin.buffer.readline
H, W = map(int, input().split())
ch, cw = map(int, input().split())
ch, cw = ch - 1, cw - 1  # 0-indexed
dh, dw = map(int, input().split())
dh, dw = dh - 1, dw - 1  # 0-indexed
# print(f'{ch=}, {cw=}')
S = []
for _ in range(H):
    S.append(list(input()))
# S = np.array(S)
# print(f'{S=}')

# G = np.full_like(S, -1, dtype='int')
G = []
for _ in range(H):
    G.append([-1] * W)
# print(f'{G=}')

current_G = 0
group_dic = defaultdict(list)
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        if G[h][w] != -1:
            continue
        G[h][w] = current_G
        group_dic[current_G].append((h, w))
        q = deque([(h, w)])
        while q:
            # print(f'{q=}')
            _h, _w = q.popleft()
            # print(f'{_h=}, {_w=}')
            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nx = _w + dx
                ny = _h + dy
                # print(f'{nx=}, {ny=}')
                if nx < 0 or ny < 0 or nx >= W or ny >= H:
                    # print(f'fuga {nx=}, {ny=}')
                    continue
                if S[ny][nx] == '#':
                    continue
                if G[ny][nx] != -1:
                    # print(f'hoge')
                    continue
                G[ny][nx] = current_G
                q.append((ny, nx))
                group_dic[current_G].append((ny, nx))
        current_G += 1
#         print(f'')
# print(f'{G=}')
# print(f'{current_G=}')
# print(f'{group_dic=}')

if current_G == 1:
    print(0)
    exit()

# print(f'start group = {G[ch][cw]=}')
start_group = G[ch][cw]

P = [-1] * (current_G)
P[start_group] = 0
# print(f'{P=}')

g = start_group
GG = deque([start_group])
while GG:
    g = GG.popleft()
    for h, w in group_dic[g]:
        for dx, dy 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)):
            nx = w + dx
            ny = h + dy
            if nx < 0 or ny < 0 or nx >= W or ny >= H:
                continue
            if S[ny][nx] == '#':
                continue
            _g = G[ny][nx]
            if P[_g] != -1:
                continue
            P[_g] = P[g] + 1
            GG.append(_g)

# print(f'{P=}')
# print(f'goal group = {G[dh][dw]=}')
ans = P[G[dh][dw]]
print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import deque
    H, W = (int(i) for i in input().split())
    Ch, Cw = (int(i)-1 for i in input().split())
    Dh, Dw = (int(i)-1 for i in input().split())
    A = [input() for i in range(H)]
    V = [[-1]*W for i in range(H)]  # 頂点i
    d = ((1, 0), (0, 1), (-1, 0), (0, -1))

    def bfs_2d(sy, sx, v):
        que = deque()
        V[sy][sx] = v
        que.append(sy * (H*W) + sx)
        while que:
            uh = que.popleft()
            uw = uh % (H*W)
            uh //= (H*W)
            for dy, dx in d:
                next_h = uh + dy
                next_w = uw + dx
                if not(0 <= next_h < H and 0 <= next_w < W):
                    continue
                if V[next_h][next_w] != -1:
                    continue
                if A[next_h][next_w] == '#':
                    continue
                V[next_h][next_w] = v
                que.append(next_h * (H*W) + next_w)

    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" or V[h][w] != -1:
                continue
            bfs_2d(h, w, vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            for dh in range(-2, 3):
                for dw in range(-2, 3):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))

    # for h in range(H):
    #     print(V[h])

    # for i in range(vertex):
    #     print(G[i])

    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)

    print(dist[g])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

S=list(map(int,input().split()))
G=list(map(int,input().split()))
S[0]+=1
S[1]+=1
G[0]+=1
G[1]+=1

L=[]
l=[-1 for i in range(W+4)]
L.append(l)
L.append(l)
for i in range(H):
    s=list(input())
    for j in range(W):
        if s[j]=="#":
            s[j]=-1
        else:
            s[j]=10**12
    L.append([-1,-1]+s+[-1,-1])
L.append(l)
L.append(l)
#L[S[0]][S[1]]=0
#(L)
X=[1,-1,0,0]
Y=[0,0,1,-1]
F=0
Q=[[S[0],S[1]]]

for x in range(10**6):
    if len(Q)==0:
        break
    for i in range(10**7):
        if i==len(Q):
            break
        H,W=Q[i]
        #print(H,W)
        if L[H][W]==10**12:
            L[H][W]=x
            for xy in range(4):
                if L[H+X[xy]][W+Y[xy]]==10**12:
                    Q.append([H+X[xy],W+Y[xy]])
    q={}
    for i in range(len(Q)):
        H,W=Q[i]
        for h in range(-2,3):
            for w in range(-2,3):
                if L[H+h][W+w]==10**12:
                    q[(H+h,W+w)]=1
    #print(q)
    Q=list(q.keys())
    #print(Q)
if L[G[0]][G[1]]==10**12:
    print(-1)
else:
    print(L[G[0]][G[1]])

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy

input = sys.stdin.readline

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [input() for _ in range(h)]

v = [[-1] * w for _ in range(h)]
d = [(0,1), (0,-1), (1,0), (-1,0)]
d2 = [(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)]

v[ch-1][cw-1] = 0

q = deque([(ch-1, cw-1)])
q2 = [(ch-1, cw-1)]
tmp = 0

while True:
    while q:
        i,j = q.popleft()
        for ii,jj in d:
            if 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))

    cnt = 0
    for k in range(len(q2)):
        i,j = q2[k][0], q2[k][1]
        for ii,jj in d2:
            if v[i][j] == tmp and 0 <= i + ii < h and 0 <= j + jj < w:
                if v[i+ii][j+jj] == -1 and s[i+ii][j+jj] == '.':
                    v[i+ii][j+jj] = tmp+1
                    q.append((i+ii,j+jj))
                    q2.append((i+ii,j+jj))
                    cnt += 1
    if not q:
        break
    tmp += 1
    q2 = q2[-cnt:]
print(v[dh-1][dw-1])