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 heapq
class Dijkstra:
    INF = 10**13
    threshold = 10**6+1

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

def main():
    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    eh, ew = map(int, input().split())

    sh -= 1
    sw -= 1
    eh -= 1
    ew -= 1

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

    di = Dijkstra(h*w)
    for x in range(h):
        for y in range(w):
            if S[x][y] == '#': continue
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + i
                    Y = y + j
                    if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                    D = abs(i) + abs(j)

                    if D == 1: di.insert(x * w + y, X * w + Y, 0)
                    if D >= 2: di.insert(x * w + y, X * w + Y, 1)

    di.dijkstra(sh * w + sw)
    ans = di.dist[eh * w + ew]
    if ans == 10**13: print(-1)
    else: print(ans)

main()

Submission status: Accepted

Solution code:
import heapq
class Dijkstra:
    INF = 10**18
    threshold = 10**9

    def __init__(self, N):
        self.MAX_V = N + 1
        self.dist = [self.INF] * self.MAX_V
        self.G = [[] for _ in range(self.MAX_V)]

    def insert(self, X, Y, cost): self.G[X].append(cost * self.threshold + Y)

    def dijkstra(self, st):
        q = []
        heapq.heappush(q, st)
        self.dist[st] = 0

        while len(q):
            p = heapq.heappop(q)
            cost = p // self.threshold
            node = p - cost * self.threshold
            if cost > self.dist[node]: continue
            for to in self.G[node]:
                to_cost = to // self.threshold
                to_node = to - to_cost * self.threshold
                to_cost += self.dist[node]
                if self.dist[to_node] > to_cost:
                    self.dist[to_node] = to_cost
                    heapq.heappush(q, to_cost * self.threshold + to_node)

def main():
    h, w = map(int, input().split())
    sh, sw = map(int, input().split())
    eh, ew = map(int, input().split())

    sh -= 1
    sw -= 1
    eh -= 1
    ew -= 1

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

    di = Dijkstra(h*w)
    for x in range(h):
        for y in range(w):
            if S[x][y] == '#': continue
            for i in range(-2, 3):
                for j in range(-2, 3):
                    X = x + i
                    Y = y + j
                    if X < 0 or Y < 0 or X >= h or Y >= w or S[X][Y] == '#': continue
                    D = abs(i) + abs(j)

                    if D == 1: di.insert(x * w + y, X * w + Y, 0)
                    if D >= 2: di.insert(x * w + y, X * w + Y, 1)

    di.dijkstra(sh * w + sw)
    ans = di.dist[eh * w + ew]
    if ans == 10**18: print(-1)
    else: print(ans)

main()

Submission status: Accepted

Solution code:
from collections import deque
# (sx, sy) から (gx, gy) への最短距離を求める
# 辿り着けないと INF
def bfs():
    # すべての点を INF で初期化
    d = [[float("inf")] * m for i in range(n)]
    # 移動4方向のベクトル
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    sx = c[0]
    sy = c[1]
    gx = g[0]
    gy = g[1]

    # 周辺25マス移動
    dd = []
    for i in range(-2,3):
        for j in range(-2,3):
            dd.append([i,j])

    # スタート地点をキューに入れ、その点の距離を0にする
    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0
    # キューが空になるまでループ
    while que:
        # キューの先頭を取り出す
        p = que.popleft()
        # 取り出してきた状態がゴールなら探索をやめる
        if p[0] == gx and p[1] == gy:
            break
        # 移動4方向をループ
        for i in range(4):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] > d[p[0]][p[1]]:
                # 移動できるならキューに入れ、その点の距離を p からの距離 +1 で確定する
                que.appendleft((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]
        for i in range(25):
            # 移動した後の点を (nx, ny) とする
            nx = p[0] + dd[i][0]
            ny = p[1] + dd[i][1]
            # 移動が可能かの判定とすでに訪れたことがあるかの判定
            # d[nx][ny] != INF なら訪れたことがある
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == "." and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]]+1

    return d[gx][gy]

n, m = map(int, input().split())
c = list(map(lambda x:int(x)-1,input().split()))
g = list(map(lambda x:int(x)-1,input().split()))
maze = [list(input()) for i in range(n)]

ans = bfs()
if ans == float("inf"):
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque

H,W=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
S=[input() for _ in range(H)]
visited=[[-1]*W for _ in range(H)]
visited[ch-1][cw-1]=0
h=deque([(ch-1,cw-1)])
c=0
while 1:
  done=[]
  while h:
    cx,cy=h.popleft()
    done.append((cx,cy))
    for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
      nx,ny = cx+dx,cy+dy
      if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
        h.append((nx,ny))
        visited[nx][ny]=c
  for cx,cy in done:
    for dx in range(-2,3):
      for dy in range(-2,3):
        nx,ny = cx+dx,cy+dy
        if 0<=nx<H and 0<=ny<W and S[nx][ny]=='.' and visited[nx][ny]==-1:
          h.append((nx,ny))
          visited[nx][ny]=c+1
  if not h or visited[dh-1][dw-1]!=-1:
    break
  c+=1
print(visited[dh-1][dw-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())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
t = [list(input()) for _ in range(h)]
d = deque([(Ch, Cw)])
d2 = deque()
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]
b = range(-2, 3)

while True:
  # 移動A
  while len(d) != 0:
    Th, Tw = d.popleft()
    d2.append((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  while len(d2) != 0:
    Th, Tw = d2.popleft()
    for i in b :
      for j in b :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[_h][_w] = 1
  if len(d) == 0:
    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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[_h][_w] = 1
  if len(d) == 0:
    print('-1')
    exit()

Submission status: Accepted

Solution code:
from collections import deque

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

S = []
dist = []

for _ in range(H):
    S.append([a for a in input()])
    dist.append([-1 for _ in range(len(S[-1]))])

dist[Ch][Cw] = 0
q = deque()
q.append((Ch, Cw))
cost = 0

def p_dist():
    print('---')
    for row in dist:
        print(row)

while q:
    jump_list = []
    while q:
        v = q.popleft()
        jump_list.append(v)
        # print('n', v)
        for i in [v[0]-1, v[0]+1]:
            j = v[1]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))
        for j in [v[1]-1, v[1]+1]:
            i = v[0]
            if i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                dist[i][j] = cost
                q.append((i, j))

    cost += 1
    for v in jump_list:
        # print('j', v)
        for i in range(v[0]-2, v[0]+3):
            for j in range(v[1]-2, v[1]+3):
                if ((i == v[0] + 1) or (i == v[0] -1)) and j == v[1]:
                    pass
                elif ((j == v[1] + 1) or (j == v[1] -1)) and i == v[0]:
                    pass
                elif i == v[0] and j == v[1]:
                    pass
                elif i >= 0 and j >= 0 and i < H and j < W and S[i][j]=='.' and dist[i][j] == -1:
                    # print(i, j, dist[i][j])
                    dist[i][j] = cost
                    q.append((i, j))

# p_dist()
print(dist[Dh][Dw])

Submission status: Accepted

Solution code:
from collections import deque


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

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = []
for i in range(-2, 3):
    for j in range(-2, 3):
        if (i, j) != (0, 0) and (i, j) not in walk:
            warp.append((i, j))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))
    for dx, dy in warp:
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
          visited[Th][Tw] = 1
  if len(d) == 0:
    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
t = [[i for i in range(w)] for j in range(h)]
visited = [[0 for i in range(w)] for j in range(h)] # いったところ
ans = 0
for i in range(h):
  temp = input()
  for j in range(w):
    t[i][j] = temp[j]

d = deque([(Ch, Cw)])
ans = 0
a = [(1,0),(-1,0),(0,1),(0,-1)]

while True:
  # 移動A
  stemp = set()
  while len(d) != 0:
    Th, Tw = d.popleft()
    # s.add((Th, Tw))
    visited[Th][Tw] = 1
    stemp.add((Th, Tw))
    if (Th,Tw) == (Dh, Dw):
      print(ans)
      exit()
    for i, j in a:
      _h,_w = Th + i, Tw + j
      _p = (_h, _w)
      if 0 <= _h < h and 0 <= _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
        d.append(_p)
        visited[_h][_w] = 1
  # 移動B
  ans += 1
  for Th,Tw in stemp:
    for i in range(-2, 3) :
      for j in range(-2, 3) :
        _h,_w = Th + i, Tw + j
        _p = (_h, _w)
        if 0 <= _h < h and 0 <=  _w < w and t[_h][_w] == '.' and visited[_h][_w] == 0:
          d.append(_p)
  if len(d) == 0:
    print('-1')
    exit()

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

S=["*"*(W+4)]*(H+4)

for x in range(H):
    S[x+2]="**"+input()+"**"

V=[]
for a in range(-2,3):
    for b in range(-2,3):
        if not(a==b==0):
            if abs(a)+abs(b)<=1:
                V.append(((a,b),0))
            else:
                V.append(((a,b),1))

inf=float("inf")
Dist=[[inf]*(W+1) for _ in range(H+1)]

Q=deque([C])
Dist[C[0]][C[1]]=0

while Q:
    (x,y)=Q.popleft()
    for ((a,b),c) in V:
        try:
            if S[x+a+1][y+b+1]=="." and Dist[x][y]+c<Dist[x+a][y+b]:
                Dist[x+a][y+b]=Dist[x][y]+c
                if c==0:
                    Q.appendleft((x+a,y+b))
                else:
                    Q.append((x+a,y+b))
        except:
            pass

if Dist[D[0]][D[1]]<inf:
    print(Dist[D[0]][D[1]])
else:
    print(-1)

Submission status: Accepted

Solution code:
# 01-BFS

from collections import deque

H, W = map(int, input().split())
CH, CW = map(int, input().split())
DH, DW = map(int, input().split())
# list(文字列)で1文字ごと分解される
S = [list(input()) for _ in range(H)]

q = deque([(CH - 1, CW - 1, 0)])

while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        # 既に訪れたマスにはc(魔法を使う回数)を代入する
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0 <= h + i < H and 0 <= w + j < W and S[h + i][w + j] == '.':

                    # (i,j) = (0,0)の場合
                    if abs(i) + abs(j) == 0:
                        continue

                    # (i,j) = (1,0), (0,1), (-1,0), (0,-1)の場合
                    elif abs(i) + abs(j) == 1:
                        q.appendleft((h + i, w + j, c))

                    # それ以外の20通りの場合
                    elif abs(i) + abs(j) >= 2:
                        q.append((h + i, w + j, c + 1))

# 更新されていない場合
if S[DH - 1][DW - 1] == '.':
    print(-1)
# 更新されている場合
else:
    print(S[DH - 1][DW - 1])

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
genzai=deque()
wapu=deque()
genzai.append([c_h-1,c_w-1])
wapu.append([c_h-1,c_w-1])
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append([gyou,retu])
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append([gyou+i,retu])
                wapu.append([gyou+i,retu])
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append([gyou,retu+i])
                wapu.append([gyou,retu+i])

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append([gyou+i,retu+j])

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.popleft()
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.popleft()
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])

Submission status: Accepted

Solution code:
from collections import deque

h,w=map(int, input().split())
c_h,c_w=map(int, input().split())
d_h,d_w=map(int, input().split())
map=[[-1]*w for i in range(h)]
 
for gyou in range(h):
    tmp=input()
    for retu in range(w):
        if tmp[retu]=="#":map[gyou][retu]=-2
 
genzai=deque()
wapu=deque()
genzai.append((c_h-1,c_w-1))
wapu.append((c_h-1,c_w-1))
 
map[c_h-1][c_w-1]=0
 
def idou(gyou,retu,kaisuu):
    wapu.append((gyou,retu))
    for i in (-1,1):
        if 0<=gyou+i and gyou+i<h:
            if map[gyou+i][retu]==-1:
                map[gyou+i][retu]=kaisuu
                genzai.append((gyou+i,retu))
                wapu.append((gyou+i,retu))
                
        if 0<=retu+i and retu+i<w:
            if map[gyou][retu+i]==-1:
                map[gyou][retu+i]=kaisuu
                genzai.append((gyou,retu+i))
                wapu.append((gyou,retu+i))

def idou_wapu(gyou,retu,kaisuu):
    for i in range(-2,3):
        for j in range(-2,3):
            if 0<=gyou+i and gyou+i<h and 0<=retu+j and retu+j<w:
                if map[gyou+i][retu+j]==-1:
                    map[gyou+i][retu+j]=kaisuu+1
                    genzai.append((gyou+i,retu+j))

wapu_kaisuu=0

while len(genzai)!=0:
 
    while len(genzai)>0:
        idou(genzai[0][0],genzai[0][1],wapu_kaisuu)
        genzai.popleft()
    
    while len(wapu)>0:
        idou_wapu(wapu[0][0],wapu[0][1],wapu_kaisuu)
        wapu.popleft()
    
    wapu_kaisuu+=1

    if map[d_h-1][d_w-1]!=-1:
        print(map[d_h-1][d_w-1])
        exit()


print(map[d_h-1][d_w-1])

Submission status: Accepted

Solution code:
def resolve():
  H, W = map(int, input().split(" "))
  Ch, Cw = map(int, input().split(" "))
  wiz_pos = [Ch-1, Cw-1]
  Dh, Dw = map(int, input().split(" "))
  goal_pos = [Dh-1, Dw-1]

  cell_or_wall = []
  count = 0
  for _ in range(H):
    cell_or_wall.append([x == "." for x in list(input())])

  cost_of_cells = [[None] * W for i in range(H)]
  next_cells = set([tuple(wiz_pos)])
  cells_of_wall_side = []

  cost = 0
  
  while len(next_cells) != 0:
    temp_next_cells = set()
    for target_cell in next_cells:
      cost_of_cells[target_cell[0]][target_cell[1]] = cost
      # 周辺の壁じゃないセルを確認する。
      adjacents = [
        [target_cell[0] - 1, target_cell[1]],
        [target_cell[0] + 1, target_cell[1]],
        [target_cell[0], target_cell[1] - 1],
        [target_cell[0], target_cell[1] + 1]
      ]

      for adjacent in adjacents:
        h = adjacent[0]
        w = adjacent[1]
        if h < 0 or h >= H:
          continue
        if w < 0 or w >= W:
          continue

        # print("[h, w] : {}".format([h, w]), "cell_or_wall[h][w] : {}".format(cell_or_wall[h][w]))
        if not cell_or_wall[h][w]:
          # 壁際だった場合は壁際セルリストに追加する。
          if len(cells_of_wall_side) == 0:
            cells_of_wall_side.append(target_cell)
          elif cells_of_wall_side[-1][0] != target_cell[0] or cells_of_wall_side[-1][1] != target_cell[1]:
            cells_of_wall_side.append(target_cell)
          # else: 
          #   print("cells_of_wall_side : {}".format(cells_of_wall_side), "target_cell : {}".format(target_cell))
        elif cost_of_cells[h][w] is None:
          temp_next_cells.add((h, w))
    # print(target_cell)
    # print(temp_next_cells)
    next_cells = temp_next_cells

    if len(next_cells) != 0:
      continue

    # 壁際のセルを確認して、ワープで飛べないか確認する。
    # print(cells_of_wall_side)
    for target_cell in cells_of_wall_side:
      # 飛べるなら next_cells に追加する
      for h in range(target_cell[0] - 2, target_cell[0] + 3):
        if h < 0 or h >= H:
          continue
        for w in range(target_cell[1] - 2, target_cell[1] + 3):
          if w < 0 or w >= W:
            continue
          if cell_or_wall[h][w] and cost_of_cells[h][w] is None:
            next_cells.add((h, w))
    cells_of_wall_side = []
    cost += 1
  
  # for cost_line in cost_of_cells:
  #   print("")
  #   for cell in cost_line:
  #     if cell is None:
  #       print("*", end="")
  #     else:
  #       print(cell, end="")
  # print("")

  if cost_of_cells[goal_pos[0]][goal_pos[1]] is None:
    print(-1)
  else:
    print(cost_of_cells[goal_pos[0]][goal_pos[1]])

if __name__ == "__main__":
  resolve()

Submission status: Accepted

Solution code:
from collections import deque

H,W = map(int,input().split())
sy,sx = map(int,input().split())
gy,gx = map(int,input().split())

S = [None]*W
S = [list(input()) for i in range(H)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

wx = [-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2]
wy = [-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,0,1,2]

def distance(i,j):
    not_visited = [[-1]*W for i in range(H)]
    not_visited[i][j] = 0
    stack = deque()
    stack.append((i,j))

    stack2 = deque()
    stack2.append((i,j))

    while stack2 != deque([]):

        while stack != deque([]):
            y,x = stack.popleft()
            for i in range(4):
                if 0<= x+dx[i] <W and 0<= y+dy[i] <H and S[y+dy[i]][x+dx[i]] != "#" and not_visited[y+dy[i]][x+dx[i]] == -1:
                    not_visited[y+dy[i]][x+dx[i]] =  not_visited[y][x]
                    stack.append((y+dy[i],x+dx[i]))
                    stack2.append((y+dy[i],x+dx[i]))

        y,x = stack2.popleft()
        for i in range(25):
            if 0<= x+wx[i] <W and 0<= y+wy[i] <H and S[y+wy[i]][x+wx[i]] != "#" and not_visited[y+wy[i]][x+wx[i]] == -1:
                not_visited[y+wy[i]][x+wx[i]] =  not_visited[y][x] + 1
                stack.append((y+wy[i],x+wx[i]))
                stack2.append((y+wy[i],x+wx[i]))
        
        """
        for i in range(H):
            print(not_visited[i])
        print()
        """
    return not_visited[gy-1][gx-1]
    
print(distance(sy-1,sx-1))

Submission status: Accepted

Solution code:
def main():
    from collections import deque

    h, w = map(int, input().split())
    ch, cw = map(lambda x: int(x) - 1, input().split())
    dh, dw = map(lambda x: int(x) - 1, input().split())

    m = [list(input()) for _ in range(h)]
    vis = [[False for _ in range(w + 2)] for _ in range(h + 2)]

    def walk(i, j):
        q = deque()
        q.append((i, j))
        edge = []
        while q:
            y, x = q.popleft()
            if vis[y][x]:
                continue
            vis[y][x] = True
            for s, t in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                    if m[y + s][x + t] == '#':
                        edge.append((y, x))
                        continue
                    q.appendleft((y + s, x + t))
        return edge

    def jump(i, j, c):
        q = walk(i, j)
        if vis[dh][dw]:
            return c
        nx = []
        c += 1
        while q:
            y, x = q.pop()
            for s in range(-2, 3):
                for t in range(-2, 3):
                    if vis[y + s][x + t]:
                        continue
                    if 0 <= y + s <= h - 1 and 0 <= x + t <= w - 1:
                        if m[y + s][x + t] == '#':
                            continue
                        nx += walk(y + s, x + t)
                        if vis[dh][dw]:
                            return c
            if len(q) == 0:
                c += 1
                q = nx
                nx = []

    ans = jump(ch, cw, 0)
    print(ans if ans is not None else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from itertools import product
import heapq


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-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)
    ]
    S[CH-1][CW-1] = 0
    q = deque()
    q.appendleft((CH-1, CW-1))
    while q:
        # キューの先頭から候補を取り出す
        y0, x0 = q.popleft()
        d0 = S[y0][x0]
        # 距離0で到達可能な場所をキューの先頭に入れる
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0):
                q.appendleft((ny, nx))
                S[ny][nx] = d0
        # 距離1で到達可能な場所をキューの末尾に入れる
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and (S[ny][nx] == -1 or S[ny][nx] > d0+1):
                q.append((ny, nx))
                S[ny][nx] = d0+1
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

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)]
q = deque([(CH-1, CW-1, 0)])
while q:
    h, w, c = q.popleft()
    if S[h][w] == '.':
        S[h][w] = c
        for i in range(-2, 3):
            for j in range(-2, 3):
                if 0<=h+i<H and 0<=w+j<W and S[h+i][w+j] == '.':
                    if abs(i)+abs(j) == 1:
                        q.appendleft((h+i, w+j, c))
                    elif abs(i)+abs(j) >= 2:
                        q.append((h+i, w+j, c+1))
if S[DH-1][DW-1] == '.':
    print(-1)
else:
    print(S[DH-1][DW-1])

Submission status: Accepted

Solution code:
import zlib,base64
exec(zlib.decompress(base64.b85decode("c-oy(%Wi`(5WMphE>(q%O(Z9$L~-tXgM}&zCUFGDyh`}{E(F}F>Zu2Im+^RJY`JLb3U$MWZR<>R9nzJp+dlN#!C>s$$xa8K`B4VN_ludF)n%!&Uf1TE9gAZa9zA?xBVo8>J=B6-iBO+uiGwP&Seu?{V}~A-U1v)Tov<K05U&z)T`1}ny(4W<o0_Y_H<Ea{kTOof5&f~&h+H*;!V-58XFYtJB*YtUx>Tq+c?eDH!7|b8Y;8+bfCFH<K)IX}`AE+3DXUGd&7c5ZL6N~cn`w3jJ3N8x1C9ey5r1~NbUNd+$s&2X=u5=U_w#s;g~+8&<UM&2)iwmL!KvA$)+&=PQ84JUjF8`Md+^!M`pd+(Y3tM>^vU9m&mEsT9^ZHyYx}2eA9edE|9Q5R=kidOhpu_3%R`@e{&gGcO@I*bYzxl>=dy@+BCk;1Vz7jlN5~fd{l8Q")))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
from itertools import product
import heapq


def read():
    H, W = map(int, input().strip().split())
    CH, CW = map(int, input().strip().split())
    DH, DW = map(int, input().strip().split())
    S = [[0 for j in range(W)] for i in range(H)]
    for i in range(H):
        s = list(input().strip())
        for j in range(W):
            if s[j] == "#":
                S[i][j] = -2
            else:
                S[i][j] = -1
    return H, W, CH, CW, DH, DW, S


def solve(H, W, CH, CW, DH, DW, S):
    DIR0 = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    DIR1 = [
        (-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)
    ]
    q = deque()
    q.appendleft((CH-1, CW-1, 0))
    while q:
        # キューの先頭から候補を取り出す
        y0, x0, d0 = q.popleft()
        if 0 <= S[y0][x0] < d0:
            continue
        S[y0][x0] = d0
        # 距離0で到達可能な場所をキューの先頭に入れる
        for dy, dx in DIR0:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.appendleft((ny, nx, d0))
        # 距離1で到達可能な場所をキューの末尾に入れる
        for dy, dx in DIR1:
            ny, nx = y0 + dy, x0 + dx
            if 0 <= ny < H and 0 <= nx < W and S[ny][nx] == -1:
                q.append((ny, nx, d0+1))
    return S[DH-1][DW-1]


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))