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
#処理は72行目から開始。

#変数一覧
# 入力
#   H : 縦サイズ,  W : 横サイズ
#   (hs, ws) : 始点座標,  (hg, wg) : 終点座標
#   S : グラフ("#" or ".")
# 処理
#   task : タスクとなる点のリスト(deque)。後述のように、その点から行ける新しい点を探すタスクを行う）
#   visited : 処理中に訪れた点の集合 (taskに組み入れたタイミングで「訪れた」とみなす)


# 幅優先探索 
# 1, taskに入っているいずれかの点から、歩きで行ける点を列挙 
# 2, 見つかった点について、そこからワープで行ける新たな点を列挙

# 処理1のやり方
#  ① 初期点をtaskに格納
#  ② taskに格納した点から、直接行ける(新たな)点を見つける
#  ③ 見つかった点をtaskに格納
#  ④ taskが空になるまで、②と③を繰り返す
#  ※ 言葉の約束
#   点sを「訪れた(visited)」= 点sをtaskに格納した
#   (taskから取り出すことではないので注意)

def BFS(task, ct):
  D = [(1,0), (0,1), (-1,0), (0,-1)] #歩きによる動き
  semi_visited = set() #この処理中に訪れた点をメモしておく（あとでワープ先を調べるため）
  task_n = deque([]) #ワープ後に行ける点の集合を、新たなtaskとして導入
  
  for s in task: #最初にtaskに入っているものは、この処理中で訪れた点としてカウントする
    semi_visited.add(s)
    
  while task: # taskが空でないうちは続ける
    s = task.popleft() # 点を取り出し
    if s == (hg, wg): # ゴールに着いていたら終了する
      print(ct)
      sys.exit()
    x = s[0]
    y = s[1]
    for d in D:
      s_n = (x+d[0], y+d[1]) # 点sから歩いて行ける点
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1:
        if (s_n not in semi_visited) and S[s_n[0]][s_n[1]] == ".": 
          # 点s_nが、まだ訪れたことのない道マスのとき
          task.append(s_n) # taskに追加
          semi_visited.add(s_n) # 処理中に訪れた点をメモしておく
          visited.add(s_n)  # 訪れた点をメモしておく
          
  for s in semi_visited: # この処理中に訪れた全ての点sについて
    warp(s, task_n) # 点sからワープ可能な点の列挙を行い、task_nへ格納する
  
  return (ct+1, task_n) #更新したコストと、新たなタスクのリストを返す

# 点p=(x,y)の周りでワープできる点を探す。
# それが訪れたことのない点なら、task_nに格納する。
def warp(p, task_n): 
  x = p[0]
  y = p[1]
  for dh in range(-2,3):   #周囲2マス
    for dw in range(-2,3):
      s_n = (x+dh, y+dw)
      if 0 <= s_n[0] <= H-1 and 0 <= s_n[1] <= W-1:
        if s_n not in visited and S[s_n[0]][s_n[1]] == ".": 
          #まだ訪れたことのない点であるとき
          task_n.append(s_n) # taskに組み入れる
          visited.add(s_n)   # taskに組み入れた点は、「訪れた」とみなす 

#処理始め
H, W = map(int, input().split())
hs, ws = map(int, input().split())
hs -= 1
ws -= 1
hg, wg = map(int, input().split())
hg -= 1
wg -= 1

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

task = deque([(hs, ws)]) # taskに初期点を追加
visited = {(hs, ws)} # taskに入れた点は訪れたものとみなす
ct = 0

while task: # taskが空でない限り続ける
  ct, task = BFS(task, ct) 
  # 幅優先探索（1,歩いて行ける点の列挙 → 2,ワープで行ける点の列挙）

print(-1) # taskが空になってもゴールに着かないなら、ゴールにたどり着くことは不可能

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
from heapq import heappop, heappush


def solve(h, w, s, t, field):
    WARP = (-(w * 2 + 10), -(w * 2 + 9), -(w * 2 + 8), -(w * 2 + 7), -(w * 2 + 6),
            -(w + 6), -(w + 5), -(w + 3), -(w + 2),
            -2, 2,
            w + 2, w + 3, w + 5, w + 6,
            w * 2 + 6, w * 2 + 7, w * 2 + 8, w * 2 + 9, w * 2 + 10)
    WALK = (-(w + 4), -1, 1, w + 4)

    qc = np.zeros(2000000, dtype=np.int32)
    qv = np.zeros(2000000, dtype=np.int32)
    qv[0] = s
    l, r = 0, 1
    visited = np.zeros((h + 4) * (w + 4), np.int8)
    queued = np.zeros((h + 4) * (w + 4), np.int8)
    queued[s] = 1
    while l < r:
        cost = qc[l]
        v = qv[l]
        l += 1
        if v == t:
            return cost
        if visited[v]:
            continue
        visited[v] = 1
        for d in WALK:
            u = v + d
            if field[u] or visited[u] or queued[u]:
                continue
            queued[u] = 1
            l -= 1
            qc[l] = cost
            qv[l] = u
        for d in WARP:
            u = v + d
            if field[u] or visited[u] or queued[u]:
                continue
            qc[r] = cost + 1
            qv[r] = u
            r += 1

    return -1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8,i8,i1[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8,i8,i8,i8,i1[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

h, w = map(int, sys.stdin.readline().split())
ch, cw = map(int, sys.stdin.readline().split())
dh, dw = map(int, sys.stdin.readline().split())
field = np.ones((h + 4) * (w + 4), dtype=np.int8)
for i in range(h):
    line = sys.stdin.readline().strip()
    field[(i + 2) * (w + 4) + 2:(i + 2) * (w + 4) + w + 2] = list(map('.#'.index, line))
s = (ch + 1) * (w + 4) + cw + 1
t = (dh + 1) * (w + 4) + dw + 1
ans = solve(h, w, s, t, field)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np
from heapq import heappop, heappush


def solve(h, w, s, t, field):
    WARP = (-(w * 2 + 10), -(w * 2 + 9), -(w * 2 + 8), -(w * 2 + 7), -(w * 2 + 6),
            -(w + 6), -(w + 5), -(w + 3), -(w + 2),
            -2, 2,
            w + 2, w + 3, w + 5, w + 6,
            w * 2 + 6, w * 2 + 7, w * 2 + 8, w * 2 + 9, w * 2 + 10)
    WALK = (-(w + 4), -1, 1, w + 4)

    q = [(0, s)]
    visited = np.zeros((h + 4) * (w + 4), np.int8)
    queued = np.zeros((h + 4) * (w + 4), np.int8)
    queued[s] = 1
    while q:
        cost, v = heappop(q)
        if v == t:
            return cost
        if visited[v]:
            continue
        visited[v] = 1
        for d in WALK:
            u = v + d
            if field[u] or visited[u] or queued[u]:
                continue
            queued[u] = 1
            heappush(q, (cost, u))
        for d in WARP:
            u = v + d
            if field[u] or visited[u] or queued[u]:
                continue
            heappush(q, (cost + 1, u))

    return -1


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8,i8,i8,i8,i1[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8,i8,i8,i8,i1[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

h, w = map(int, sys.stdin.readline().split())
ch, cw = map(int, sys.stdin.readline().split())
dh, dw = map(int, sys.stdin.readline().split())
field = np.ones((h + 4) * (w + 4), dtype=np.int8)
for i in range(h):
    line = sys.stdin.readline().strip()
    field[(i + 2) * (w + 4) + 2:(i + 2) * (w + 4) + w + 2] = list(map('.#'.index, line))
s = (ch + 1) * (w + 4) + cw + 1
t = (dh + 1) * (w + 4) + dw + 1
ans = solve(h, w, s, t, field)
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
dh,dw=nii()
s=[list(input()) for i in range(h)]

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

ans=[[-1]*w for i in range(h)]
ans[ch][cw]=0

que=deque()
que.append((ch,cw))

while que:
  y,x=que.popleft()

  if y==dh and x==dw:
    print(ans[y][x])
    exit()

  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    ny=y+dy
    nx=x+dx
    if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
      que.appendleft((ny,nx))
      s[ny][nx]='#'
      ans[ny][nx]=ans[y][x]

  for i in range(-2,3):
    for j in range(-2,3):
      ny=y+i
      nx=x+j
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and ans[ny][nx]==-1:
        que.append((ny,nx))
        ans[ny][nx]=ans[y][x]+1

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
dh,dw=nii()
s=[list(input()) for i in range(h)]

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

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

que=deque()
que.append((ch,cw))

def BFS():
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]

    for i in range(-2,3):
      for j in range(-2,3):
        ny=y+i
        nx=x+j
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
          que.append((ny,nx))
          dist[ny][nx]=dist[y][x]+1

BFS()

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
dh,dw=nii()
s=[list(input()) for i in range(h)]

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

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

que=deque()
que.append((ch,cw))

def BFS(que):
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]

    for i in range(-2,3):
      for j in range(-2,3):
        ny=y+i
        nx=x+j
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
          que.append((ny,nx))
          dist[ny][nx]=dist[y][x]+1

BFS(que)

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
dh,dw=nii()
s=[list(input()) for i in range(h)]

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

ans=[[-1]*w for i in range(h)]
ans[ch][cw]=0

que=deque()
que.append((ch,cw))

def BFS():
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(ans[y][x])
      exit()

    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        ans[ny][nx]=ans[y][x]

      for i in range(-2,3):
        for j in range(-2,3):
          ny=y+i
          nx=x+j
          if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and ans[ny][nx]==-1:
            que.append((ny,nx))
            ans[ny][nx]=ans[y][x]+1

BFS()

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
dh,dw=nii()
s=[list(input()) for i in range(h)]

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

ans=[[-1 for i in range(w)] for i in range(h)]
ans[ch][cw]=0

que=deque()
que.append((ch,cw))

def BFS():
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(ans[y][x])
      exit()

    for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        ans[ny][nx]=ans[y][x]

      for i in range(-2,3):
        for j in range(-2,3):
          ny=y+i
          nx=x+j
          if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and ans[ny][nx]==-1:
            que.append((ny,nx))
            ans[ny][nx]=ans[y][x]+1

BFS()

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
ch-=1
cw-=1
dh,dw=nii()
dh-=1
dw-=1
s=[list(input()) for i in range(h)]

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

def BFS(que):
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]

    for i in range(-2,3):
      for j in range(-2,3):
        ny=y+i
        nx=x+j
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
          que.append((ny,nx))
          dist[ny][nx]=dist[y][x]+1

dist[ch][cw]=0

que=deque()
que.append((ch,cw))

BFS(que)

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
ch-=1
cw-=1
dh,dw=nii()
dh-=1
dw-=1
s=[list(input()) for i in range(h)]

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

def BFS(que):
  while que:
    y,x=que.popleft()

    if y==dh and x==dw:
      print(dist[y][x])
      exit()

    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
        que.appendleft((ny,nx))
        s[ny][nx]='#'
        dist[ny][nx]=dist[y][x]
    for dy,dx 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]]:
      ny=y+dy
      nx=x+dx
      if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and dist[ny][nx]==-1:
        que.append((ny,nx))
        dist[ny][nx]=dist[y][x]+1

dist[ch][cw]=0

que=deque()
que.append((ch,cw))

BFS(que)

print(-1)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import deque

h,w=nii()
ch,cw=nii()
dh,dw=nii()
s=[list(input()) for i in range(h)]

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

ans=[[-1 for i in range(w)] for i in range(h)]
ans[ch][cw]=0

que=deque()
que.append((ch,cw))

while que:
  y,x=que.popleft()

  if y==dh and x==dw:
    print(ans[y][x])
    exit()

  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    ny=y+dy
    nx=x+dx
    if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#':
      que.appendleft((ny,nx))
      s[ny][nx]='#'
      ans[ny][nx]=ans[y][x]

    for i in range(-2,3):
      for j in range(-2,3):
        ny=y+i
        nx=x+j
        if 0<=ny<h and 0<=nx<w and s[ny][nx]!='#' and ans[ny][nx]==-1:
          que.append((ny,nx))
          ans[ny][nx]=ans[y][x]+1

print(-1)

Submission status: Accepted

Solution code:
def d_wizard_in_maze():
    from collections import deque
    H, W = [int(i) for i in input().split()]
    Start_row, Start_col = [int(i) - 1 for i in input().split()]
    Goal_row, Goal_col = [int(i) - 1 for i in input().split()]
    Grid = [input() for _ in range(H)]

    warp_count = [[-1] * W for i in range(H)]
    neighbor_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    neighbor_25 = [(i, j) for i in range(-2, 3) for j in range(-2, 3)]
    queue = deque([(Start_row, Start_col, 0)])  # コスト 0 の移動は左詰めする

    while(queue):
        row, col, count = queue.popleft()
        if warp_count[row][col] != -1:
            continue
        warp_count[row][col] = count

        for dr, dc in neighbor_4:
            nr, nc = row + dr, col + dc
            if 0 <= nr < H and 0 <= nc < W and Grid[nr][nc] == '.':
                if warp_count[nr][nc] == -1:
                    queue.appendleft((nr, nc, count))

        for dr, dc in neighbor_25:
            nr, nc = row + dr, col + dc
            if 0 <= nr < H and 0 <= nc < W and Grid[nr][nc] == '.':
                queue.append((nr, nc, count + 1))

    return warp_count[Goal_row][Goal_col]

print(d_wizard_in_maze())

Submission status: Accepted

Solution code:
from collections import deque

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

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

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

print(maze[Dh][Dw])

Submission status: Accepted

Solution code:
from collections import deque
def main():
    h,w=map(int,input().split())
    sx,sy=map(int,input().split())
    sx-=1
    sy-=1
    gx,gy=map(int,input().split())
    gx-=1
    gy-=1
    g=[tuple(input()) for _ in range(h)]
    v=[[0 for j in range(w)] for i in range(h)]
    q=deque([[sx,sy]])
    v[sx][sy]=1
    ans=0
    k=[[0,1],[0,-1],[1,0],[-1,0]]
    while True:
        l=[]
        while q:
            x,y=q.popleft()
            l.append([x,y])
            if x==gx and y==gy:
                print(ans)
                exit()
            for a,b in k:
                nx=x+a
                ny=y+b
                if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                    q.append([nx,ny])
                    v[nx][ny]=1
        if len(l)==0:
            break
        for x,y in l:              
            for a in range(-2,3):
                for b in range(-2,3):
                    if a*b==0 and abs(a+b)<=1:
                        continue
                    nx=x+a
                    ny=y+b
                    if 0<=nx<h and 0<=ny<w and g[nx][ny]=='.' and v[nx][ny]==0:
                        q.append([nx,ny])
                        v[nx][ny]=1
        ans+=1 
    print(-1)
if __name__=='__main__':
    main()

Submission status: Accepted

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


from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "#":
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline()


from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "#":
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if (fro_h, fro_w)==(DH,DW):
        print d[(fro_h, fro_w)]
        quit()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

print -1

Submission status: Accepted

Solution code:
# import sys
# def input(): return sys.stdin.readline().rstrip()


from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "#":
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


from collections import deque
h, w = map(int, input().split())
a, b = map(int, input().split())
c, d = map(int, input().split())
a -= 1
b -= 1
c -= 1
d -= 1
s = [list(input()) for i in range(h)]
now = 0
dd = [(-1, 0), (1, 0), (0, 1), (0, -1)]

for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            de = deque([(i, j)])
            s[i][j] = now
            while de:
                x, y = de.popleft()
                for p, q in dd:
                    if 0 <= x + p < h and 0 <= y + q < w and s[x + p][y + q] == ".":
                        s[x + p][y + q] = now
                        de.append((x + p, y + q))
            now += 1
st = s[a][b]
en = s[c][d]
es = [set() for i in range(now)]
for i in range(h):
    for j in range(w):
        if s[i][j] != "#":
            for p in range(-2, 3):
                for q in range(-2, 3):
                    if 0 <= i + p < h and 0 <= j + q < w and s[i + p][j + q] != "#":
                        es[s[i][j]].add(s[i + p][j + q])
                        es[s[i + p][j + q]].add(s[i][j])
from heapq import heappush, heapify, heappop


def dijkstra(s):
    INF = 1 << 32
    d = [INF] * now  # 頂点sからの最短距離
    v = -1
    que = [(0, s)]
    heapify(que)
    d[s] = 0
    while que:
        p = heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for e in es[v]:
            if d[e] > d[v] + 1:
                d[e] = d[v] + 1
                heappush(que, (d[e], e))
    return d[en] if d[en] < INF else -1


print(dijkstra(st))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    if (fro_h, fro_w)==(DH,DW):
        print d[(fro_h, fro_w)]
        quit()
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)]:
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

print -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())
M=[input() for i in range(h)]
V=[[10**9]*w for i in range(h)]

q=deque([[0,c_h-1,c_w-1]])

while q:
    warp,x,y=q.popleft()

    if V[x][y]!=10**9:
        continue
    V[x][y]=warp

    if x==d_h-1 and y==d_w-1:
        break

    for px in range(-2,3):
        for py in range(-2,3):
            if 0<=x+px<h and 0<=y+py<w:
                if px == 0 and py == 0:
                    continue
                if M[x + px][y + py] == '#':
                    continue
                if abs(px)+abs(py)<=1:
                    q.appendleft([warp,x+px,y+py])
                else:
                    q.append([warp+1,x+px,y+py])


if V[d_h-1][d_w-1]==10**9:
    print(-1)
else:
    print(V[d_h-1][d_w-1])