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

def func(s, array, i, x, y):
  if x < 0 or y < 0 or x >= len(array) or y >= len(array[x]):
    return
  
  if s[x][y] == '#' or array[x][y] != 0:
    return
  
  array[x][y] = i
  func(s, array, index, x+1, y)
  func(s, array, index, x, y+1)
  func(s, array, index, x-1, y)
  func(s, array, index, x, y-1)
  

h,w = map(int,input().split())
c1,c2 = map(int,input().split())
d1,d2 = map(int,input().split())

s = []

for i in range(h):
  s.append(input())
  
array = [[0 for i in range(w)] for i in range(h)]
index = 1
for i in range(len(array)):
  for j in range(len(array[i])):
    if s[i][j] == '.' and array[i][j] == 0:
      func(s, array, index, i, j)
      index += 1

setArray = [set() for i in range(index)]
for i in range(len(array)):
  for j in range(len(array[i])):
    for k in range(max(i-2, 0), min(i+3, len(array))):
      for l in range(max(j-2, 0), min(j+3, len(array[0]))):
        if array[k][l] != 0:
          setArray[array[i][j]].add(array[k][l])

start = array[c1-1][c2-1]
end = array[d1-1][d2-1]

if start == end:
  print(0)
  sys.exit()

deq = deque()
array2 = [True] * index
for v in setArray[start]:
  if array2[v]:
    deq.append((1, v))
    array2[v] = False

while len(deq) != 0:
  tap = deq.popleft()
  if tap[1] == end:
    print(tap[0])
    sys.exit()
    
  for v in setArray[tap[1]]:
    if array2[v]:
      deq.append((tap[0]+1, v))
      array2[v] = False
      
print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return list(map(int, readline().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, readline().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, readline().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


class UnionFind:
    def __init__(self, N):
        self.N = N  # ノード数
        self.n_groups = N  # グループ数
        # 親ノードをしめす。負は自身が親ということ。
        self.parent = [-1] * N  # idxが各ノードに対応。

    def root(self, A):
        # print(A)
        # ノード番号を受け取って一番上の親ノードの番号を帰す
        if (self.parent[A] < 0):
            return A
        self.parent[A] = self.root(self.parent[A])  # 経由したノードすべての親を上書き
        return self.parent[A]

    def size(self, A):
        # ノード番号を受け取って、そのノードが含まれている集合のサイズを返す。
        return -self.parent[self.root(A)]

    def unite(self, A, B):
        # ノード番号を2つ受け取って、そのノード同士をつなげる処理を行う。
        # 引数のノードを直接つなぐ代わりに、親同士を連結する処理にする。
        A = self.root(A)
        B = self.root(B)

        # すでにくっついている場合
        if (A == B):
            return False

        # 大きい方に小さい方をくっつけたほうが処理が軽いので大小比較
        if (self.size(A) < self.size(B)):
            A, B = B, A

        # くっつける
        self.parent[A] += self.parent[B]  # sizeの更新
        self.parent[B] = A  # self.rootが呼び出されればBにくっついてるノードもすべて親がAだと上書きされる
        self.n_groups -= 1

        return True

    def is_in_same(self, A, B):
        return self.root(A) == self.root(B)


def read_map_as(H, replace={'#': 1, '.': 0}, pad=None):
    '''
    文字列のmapを置換して読み込み。デフォでは#→1,.→0
    '''
    if pad is None:
        ret = []
        for _ in range(H):
            ret.append([replace[s] for s in read()[:-1]])
            # 内包表記はpypyでは若干遅いことに注意
            # #numpy使うだろうからこれを残しておくけど
    else:  # paddingする
        ret = [[pad] * (W + 2)]  # Wはどっかで定義しておくことに注意
        for _ in range(H):
            ret.append([pad] + [replace[s] for s in read()[:-1]] + [pad])
        ret.append([pad] * (W + 2))

    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b

# ufで連結成分に分ける
# 5*5 でノードをつなげていく
# si,sjの属するノードからti,tjの属するノードまでの最短距離が答え


H, W = ints()
si, sj = mina(*ints())
ti, tj = mina(*ints())
S = read_map_as(H)
uf = UnionFind(H * W)


def to_node(i, j): return i * W + j


def to_idx(node): return node // W, node % W


for i, j in product(range(H), range(W)):
    ij = i * W + j
    if S[i][j] == 1:
        continue
    for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
        ni, nj = i + di, j + dj
        if not (0 <= ni < H and 0 <= nj < W) or S[ni][nj] == 1:
            continue
        uf.unite(ij, ni * W + nj)

# 5*5でノードをつなげる
graph = defaultdict(lambda: set())
for i, j in product(range(H), range(W)):
    if S[i][j] == 1:
        continue
    thisnode = to_node(i, j)
    for di, dj in product([-2, -1, 0, 1, 2], repeat=2):
        ni = i + di
        nj = j + dj
        if di == dj == 0 or not(0 <= ni < H and 0 <= nj < W) or S[ni][nj] == 1:
            continue
        adj_node = to_node(ni, nj)
        if uf.is_in_same(thisnode, adj_node):
            continue
        a = uf.root(adj_node)
        b = uf.root(thisnode)
        graph[a].add(b)
        graph[b].add(a)


# あとはグラフの問題！
s_node = uf.root(to_node(si, sj))
t_node = uf.root(to_node(ti, tj))

que = deque([(s_node, 0)])
is_visited = [False] * len(uf.parent)

while que:
    u, c = que.popleft()
    if u == t_node:
        exit(c)
    for nx in graph[u]:
        if is_visited[nx]:
            continue
        que.append((nx, c + 1))
        is_visited[nx] = True
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

def solve():
    readline = sys.stdin.readline

    H, W = map(int, readline().split())
    a, b = map(int, readline().split())
    c, d = map(int, readline().split())
    S = [readline().rstrip() for i in range(H)]

    a,b,c,d = (v - 1 for v in (a,b,c,d))

    INF = 10 ** 10

    groups = []

    visited = [[False] * W for i in range(H)]

    dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    def dfs(x, y, group):
        if not (0 <= x < H and 0 <= y < W):
            return
        
        if visited[x][y]:
            return
        
        if S[x][y] == '#':
            return
        
        group.append((x,y))
        visited[x][y] = True

        for dx, dy in dirs:
            dfs(x + dx, y + dy, group)

    for i in range(H):
        for j in range(W):
            if S[i][j] == '.' and not visited[i][j]:
                group = []
                dfs(i, j, group)
                groups.append(group)
    
    
    p2g = [[-1] * W for i in range(H)]
    for i,group in enumerate(groups):
        for x,y in group:
            p2g[x][y] = i
    
    G = len(groups)
    g_adj = [set() for i in range(G)]
    for i in range(H):
        for j in range(W):
            src = p2g[i][j]
            if src == -1:
                continue
            for x in range(max(0, i - 2), min(H - 1, i + 2) + 1):
                for y in range(max(0, j - 2), min(W - 1, j + 2) + 1):
                    if x == i and y == j:
                        continue
                    if p2g[x][y] == -1:
                        continue
                    g_adj[src].add(p2g[x][y])
    
    
    src_g = p2g[a][b]
    dst_g = p2g[c][d]

    visited = [False] * G
    q = deque()
    q.append((src_g, 0))

    while q:
        node, depth = q.popleft()

        if node == dst_g:
            print(depth)
            return

        for adj in g_adj[node]:
            if not visited[adj]:
                visited[adj] = True
                q.append((adj, depth + 1))
    
    print(-1)

solve()

Submission status: Accepted

Solution code:
h,w = map(int, input().split())
ch,hw = map(int, input().split())
dh,dw = map(int, input().split())

sy,sx=ch-1,hw-1
gx,gy=dw-1,dh-1

l = [None]*h
for i in range(h):
    l[i] = list(input())

dist = [[-1]*w for i in range(h)]
dist[sy][sx] = 0

from collections import deque
def walk(warped,cnt):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque(warped)
    walked=warped
    changed=False
    while Q:
        p = Q.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]

            if 0 <= nx < w and 0 <= ny < h:
                if l[ny][nx]=="." and dist[ny][nx]==-1:
                    changed=True
                    Q.append([nx, ny])
                    walked.append([nx,ny])
                    dist[ny][nx] = cnt
                    if nx==gx and ny==gy:
                        print(cnt)
                        exit()
    return walked,changed
def warp(walked,cnt):
    warped=[]
    changed=False

    for x,y in walked:
        for dx in [-2,-1,0,1,2]:
            for dy in [-2,-1,0,1,2]:
                if abs(dx)+abs(dy)<=1:
                    continue

                nx=x+dx
                ny=y+dy
                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]=="." and dist[ny][nx]==-1:
                        changed=True
                        warped.append([nx,ny])
                        dist[ny][nx] = cnt
                        if nx==gx and ny==gy:
                            print(cnt)
                            exit()
    return warped,changed

cnt=0

warped=[[sx,sy]]

while True:
    walked,walkchange= walk(warped,cnt)
    cnt+=1
    warped,warpchange=warp(walked,cnt)
    if not walkchange and not warpchange:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
from collections import deque

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

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

s = []
for _ in range(h):
    s.append(input())

mtx = [[10 ** 9]*w for _ in range(h)]

cnt = -1
now = deque()
nxt = deque()
nxt.append((ch, cw))
mtx[ch][cw] = 0

while True:
    flag = False
    if not now:
        now = nxt
        cnt += 1
        nxt = deque()
        if not now:
            break
    h_ptr, w_ptr = now.pop()
    if h_ptr != 0:
        if s[h_ptr-1][w_ptr] == '.':
            if cnt < mtx[h_ptr-1][w_ptr]:
                mtx[h_ptr-1][w_ptr] = cnt
                now.append((h_ptr-1, w_ptr))
    if w_ptr != 0:
        if s[h_ptr][w_ptr-1] == '.':
            if cnt < mtx[h_ptr][w_ptr-1]:
                mtx[h_ptr][w_ptr-1] = cnt
                now.append((h_ptr, w_ptr-1))
    if h_ptr != h-1:
        if s[h_ptr+1][w_ptr] == '.':
            if cnt < mtx[h_ptr+1][w_ptr]:
                mtx[h_ptr+1][w_ptr] = cnt
                now.append((h_ptr+1, w_ptr))
    if w_ptr != w-1:
        if s[h_ptr][w_ptr+1] == '.':
            if cnt < mtx[h_ptr][w_ptr+1]:
                mtx[h_ptr][w_ptr+1] = cnt
                now.append((h_ptr, w_ptr+1))
    for i in range(h_ptr-2, h_ptr+3):
        for j in range(w_ptr-2, w_ptr+3):
            if 0 <= i < h and 0 <= j < w and s[i][j] == '.':
                if cnt + 1 < mtx[i][j]:
                    mtx[i][j] = cnt + 1
                    nxt.append((i, j))

ret = mtx[dh][dw]

if ret == 10 ** 9:
    print(-1)
else:
    print(ret)

Submission status: Accepted

Solution code:
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 = [list(input()) for _ in range(h)]

def bfs(sy, sx):
    que = deque([])
    que.append([sy, sx])

    while que:
        y, x = que.popleft()
        dx = [0,1,0,-1]
        dy = [1,0,-1,0]
        for i in range(4):
            ny = y+dy[i]
            nx = x+dx[i]
            if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
            if s[ny][nx] == '#': continue
            if seen[ny][nx] != -1: continue
            
            seen[ny][nx] = cnt[0]
            que.append([ny, nx])
            wp.append([ny, nx])

dq = deque([])
dq.append([ch, cw])
seen = [[-1]*w for _ in range(h)]
seen[ch][cw] = 0
cnt = [0]
wp = deque([])
ok = False

while dq:
    while dq:
        y, x = dq.popleft()
        bfs(y, x)
        wp.append([y, x])    

    ok = False
    while wp:
        y, x = wp.popleft()
        for dy in range(-2, 3):
            for dx in range(-2, 3):
                if dy == 0 and dx == 0: continue
                ny = y+dy
                nx = x+dx
                if ny < 0 or ny >= h or nx < 0 or nx >= w: continue
                if s[ny][nx] == '#': continue
                if seen[ny][nx] == -1:
                    ok = True
                    seen[ny][nx] = (cnt[0]+1)
                    dq.append([ny, nx])
    if ok:
        cnt[0] += 1

if seen[dh][dw] >= 0:
    print(seen[dh][dw])
else:
    print(-1)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  H,W=LI()
  Ch,Cw=LI()
  Dh,Dw=LI()
  Ch-=1
  Cw-=1
  Dh-=1
  Dw-=1
  field=[S() for _ in range(H)]

  q=collections.deque()
  q2=collections.deque()
  q.append((Ch,Cw,0))
  ans=[[inf]*W for _ in range(H)]
  while True:
    if not q:
      if not q2:
        break
      else:
        q=q2
        q2=collections.deque()
    # for x in ans:
    #   print(x)
    # print()
    y,x,cnt=q.popleft()
    if ans[y][x]<=cnt:
      continue
    ans[y][x]=cnt
    if y==Dh and x==Dw:
      continue

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny<H and 0<=nx<W:
        if field[ny][nx]=='.':
          q.append((ny,nx,cnt))
        else:
          if dy==1 and dx==0:
            for i in range(0,2):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))
          elif dy==0 and dx==1:
            for i in range(-2,3):
              for j in range(0,2):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))
          elif dy==-1 and dx==0:
            for i in range(-1,1):
              for j in range(-2,3):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))
          elif dy==0 and dx==-1:
            for i in range(-2,3):
              for j in range(-1,1):
                nny=ny+i
                nnx=nx+j
                if 0<=nny<H and 0<=nnx<W:
                  if field[nny][nnx]=='.':
                    if ans[nny][nnx]>cnt+1:
                      q2.append((nny,nnx,cnt+1))

  x=ans[Dh][Dw]
  if x==inf:
    return -1
  return x

# main()
print(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 i in range(H)]
visited = [[-1] * W for j in range(H)]

d = deque([[Ch - 1, Cw - 1]])
wq = deque([[Ch - 1, Cw - 1]])

visited[Ch - 1][Cw - 1] = 0
move = [[0, 1], [1, 0], [0, -1], [-1, 0]]
warp_move = [[-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]
             ]
warp = 0

while len(d) > 0 or len(wq) > 0:
    while len(d) > 0:
        y, x = d.popleft()
        wq.append([y, x])
        for i, j in move:
            nexty, nextx = y + i, x + j
            if nexty == Dh - 1 and nextx == Dw - 1:
                print(warp)
                exit()
            if nextx >= 0 and nextx < W and nexty >= 0 and nexty < H:
                if S[nexty][nextx] == "." and visited[nexty][nextx] == -1:
                    visited[nexty][nextx] = warp
                    d.append([nexty, nextx])

    warp += 1
    while len(wq) > 0:
        y, x = wq.popleft()
        for i, j in warp_move:
            warp_y, warp_x = y + i, x + j
            if warp_y == Dh - 1 and warp_x == Dw - 1:
                print(warp)
                exit()
            if warp_x >= 0 and warp_x < W and warp_y >= 0 and warp_y < H:
                if S[warp_y][warp_x] == "." and visited[warp_y][warp_x] == -1:
                    visited[warp_y][warp_x] = warp
                    d.append([warp_y, warp_x])
print(-1)

Submission status: Accepted

Solution code:
from collections import deque
H, W = map(int, input().split())
start = list(map(int, input().split()))
goal = list(map(int, input().split()))
L = [list(input()) for _ in range(H)]
result = {}
def part(x, y, i, mem):
  if not (0<=x<H) or not (0<=y<W) or L[x][y]!=".":
    return
  L[x][y]=i
  mem.append((x,y))
  part(x-1, y, i, mem)
  part(x+1, y, i, mem)
  part(x, y-1, i, mem)
  part(x, y+1, i, mem)
mark = 0
for h in range(H):
  for w in range(W):
    if L[h][w]==".":
      mem = []
      part(h, w, mark, mem)
      result[mark]=mem
      mark += 1
dic = {i:-1 for i in range(mark)}
s = L[start[0]-1][start[1]-1]
dic[0]=0
g = L[goal[0]-1][goal[1]-1]
queue = deque([s])
while queue:
    now = queue.popleft()
    if now==g:
        print(dic[now])
        exit()
    for (x,y) in result[now]:
        for i in range(max(x-2, 0), min(x+3, H)):
            for j in range(max(y-2, 0), min(y+3, W)):
              key = L[i][j]
              if str(key)=="#":
                continue
              if dic[key] == -1:
                dic[key]= dic[now]+1
                queue.append(key)             
print("-1")

Submission status: Accepted

Solution code:
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "#")):
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[-1] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     # 動ける場所の候補
        self.move2 = dict()
        self.move2 = [(-2, 0), (2, 1), (1, -2), (1, -1), (1, 2), (-2, 1), (-1, 1), (-2, -1), (-2, -2), (-1, -1), (-1, -2), (2, 2), (1, 1), (2, -1), (-1, 2), (-2, 2), (2, -2), (2, 0), (0, -2), (0, 2)]

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[-1] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = -2
        next_set = deque([(p, t)])
        broken_set = deque([])
        while next_set:
            while next_set:
                p, t = next_set.popleft()
                h, w = p
                for dh, dw in self.move:
                    q = (h + dh, w + dw)
                    if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                        continue
                    if parent[q[0]][q[1]] != -1:
                        continue
                    if q == goal:
                        return t
                    parent[q[0]][q[1]] = p
                    if self.grid[q[0]][q[1]] == self.wall:         # 壁があったら進まない
                        for dh2, dw2 in self.move2:
                            r = (h + dh2, w + dw2)
                            broken_set.append((r, t))
                        continue
                    #### (debug code) ######
                    # self.debug(start, goal, q, t)
                    ########################
                    next_set.append((q, t))
            while broken_set:
                q, t = broken_set.popleft()
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if parent[q[0]][q[1]] != -1:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:  # 壁があったら進まない
                    continue
                if q == goal:
                    return t + 1
                #### (debug code) ######
                # self.debug(start, goal, q, t)
                ########################
                next_set.append((q, t+1))
        return -1

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))


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

from collections import deque
import sys
input = sys.stdin.readline

road, wall = ".", "#"                         # (進行可能を意味する記号, 進行不可を意味する記号)

H, W = map(int,input().split())                # 左上は(h,w)=(0,0)、右下は(h,w)=(H-1,W-1)
x, y = map(int, input().split())
start = (x-1,y-1)
x, y = map(int, input().split())
goal = (x-1,y-1)
grid = []
for h in range(H):
    grid.append(input().rstrip())

g = Grid(H, W, grid, (road, wall))
res = g.bfs(start=start, goal=goal)
print(res)

"""
5 6
5 6
1 1
.###.#
######
#..##.
######
#####.
"""

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
h,w = list(map(int,input().split()))
s1,s2 = list(map(int,input().split()))
f1,f2 = list(map(int,input().split()))
 
s1,s2 = s1-1,s2-1
f1,f2 = f1-1,f2-1
 
Q = [(s1,s2)]
V = [[0]*w for _ in range(h)]
G = []
ALL = [(s1,s2)]
V[s1][s2] = 1
 
for _ in range(h):
  tmp = list(input().rstrip())
  G.append(tmp)
 
count = 0
best = 0
 
while True:
  while Q:
    new_Q = []
    for node in Q:
      i,j = node[0], node[1]
      if V[i][j]==0:
        ALL.append((i,j))
        V[i][j] = 1

      if i-1>0:
        if V[i-1][j]==0 and G[i-1][j]=='.':
          V[i-1][j]=1
          new_Q.append((i-1,j))
          ALL.append((i-1,j))
 
      if j-1>0:
        if V[i][j-1]==0 and G[i][j-1]=='.':
          V[i][j-1]=1
          new_Q.append((i,j-1))
          ALL.append((i,j-1))
 
      if i+1<h:
        if V[i+1][j]==0 and G[i+1][j]=='.':
          V[i+1][j]=1
          new_Q.append((i+1,j))
          ALL.append((i+1,j))
 
      if j+1<w:
        if V[i][j+1]==0 and G[i][j+1]=='.':
          V[i][j+1]=1
          new_Q.append((i,j+1))
          ALL.append((i,j+1))
 
    Q = new_Q
 
  if V[f1][f2]==1:
    print(count)
    break
  else:
    count += 1
    part= []
    
    ALL = list(set(ALL))
 
    for node in ALL:
      i,j = node[0], node[1]
      
      for x in range(i-2,i+3):
        for y in range(j-2,j+3):
          if x>-1 and y>-1 and x<h and y<w and G[x][y] == '.' and V[x][y]==0:
            part.append((x,y))         	
       
    ALL = list(set(part))
    #print(ALL)
    Q = list(ALL)
    
    if (f1,f2) in ALL:
      print(count)
      break
 
    if len(ALL)==0:
      print(-1)
      break
      
    ALL = []

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
from collections import deque, defaultdict
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np    # cumsum
# from bisect import bisect_left, bisect_right
from copy import deepcopy

def grid_wall(grid, h, w, wall='#'):
    G = [[wall]*(w+2) for _ in range(h+2)]
    for hi in range(h):
        G[hi+1][1:w+1] = grid[hi]
    return G

def solve():
    H, W = MI()
    ch, cw = MI()
    dh, dw = MI()
    G = LLS(H)
    GW = grid_wall(G, H, W)
    GW[dh][dw] = 'G'
    # print(GW)

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

    used = deepcopy(GW)
    used[ch][cw] = '#'
    d = deque([(0, ch, cw, used)])

# for _ in range(5):
    while d:
        # print(d)
        tmp2 = []
        while d:
            m, h, w, u = d.popleft()

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

                    if (dh, dw) in move:
                        # print(nh, nw)
                        if u[nh][nw] == '#':
                            continue
                        elif u[nh][nw] == 'G':
                            print(m)
                            return
                        d.append((m, nh, nw, u))
                        u[nh][nw] = '#'
                        continue

                    if u[nh][nw] == '#':
                        continue
                    # elif u[nh][nw] == 'G':
                    #     print(mp)
                    #     return
                    tmp2.append((m+1, nh, nw))

        # print(tmp2)
        # mp = mp + 1
        for mm, nh, nw in tmp2:
            if u[nh][nw] == '#':
                continue
            elif u[nh][nw] == 'G':
                print(mm)
                return
            u[nh][nw] = '#'
            d.append((mm, nh, nw, u))

    print(-1)

if __name__ == '__main__':
    solve()

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(map(str,input())) for _ in range(H)]


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

pathB =[]
for n in range(5):
    for m in range(5):
        pathB.append((n-2,m-2))

visited  =[[-1]*W for _ in range(H)]

queue =deque([])
queue.append((ch-1,cw-1,0))
while queue:
    h,w,d =queue.popleft()
    if visited[h][w] ==-1:
        visited[h][w] =d
        
        for h1,w1 in pathA:
            newh = h1+h
            neww = w1+w
            if newh>=0 and newh<H and neww >=0 and neww <W and S[newh][neww]==".":
                queue.appendleft((newh,neww,d))
        
        for h1,w1 in pathB:
            newh = h1+h
            neww = w1+w
            if newh>=0 and newh<H and neww >=0 and neww <W and S[newh][neww]==".":
                queue.append((newh,neww,d+1))
                
    
print(visited[dh-1][dw-1])