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
from io import StringIO
import unittest
import os
from collections import deque

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# TODO 迷路クラスを作成してみた。これは、共通化しておく必要がある。
# 迷路(2次元)を扱うクラス
# ※3次元の迷路を扱いたい場合、このクラスのインスタンスを複数生成すれば良いはず。
class youk_maze:
    __maze = []
    __wall_str = ""
    __road_str = ""
    __road_s = []  # 座標の一覧(道)
    __wall_s = []  # 座標の一覧(壁)
    __arrived_s = []  # 到達情報(初期値-1；未到達)
    __not_arrived_val = -1  # 到達情報_未到達の初期値

    def __init__(self, maze: [], can_move_out: bool = False, wall_str: str = "#", road_str: str = "."):
        """
        コンストラクタ
        :maze 迷路の情報を保持する2次元配列
        :can_move_out 迷路の外側に出れるか(True:出れる、False:出れない)
        """

        if len(maze) == 0:
            raise ValueError("迷路の情報が設定されていない = len()が0")

        # -----------------
        # 道と壁を表す文字の設定
        # -----------------
        self.__wall_str = wall_str
        self.__road_str = road_str

        # -----------------
        # 迷路の作成(迷路を道or陰で囲む)
        # 目的1:　Atcoderでは座標が「1」始まりで与えられるため、迷路も開始添え字を1にして処理を明瞭にする。
        # 目的2: 迷路の外に出れるパターンの場合、迷路を道で囲む。
        # -----------------
        frame = road_str if can_move_out else wall_str
        # 1行目
        self.__maze = [[frame] + [frame for _ in range(len(list(maze[0])))] + [frame]]
        # 2~最終行手前
        for line in maze:
            self.__maze.append([frame] + line + [frame])
        # 最終行
        self.__maze.append([frame] + [frame for _ in range(len(maze[0]))] + [frame])

        # -----------------
        # 道と壁の一覧をリストにまとめておく
        # -----------------
        self.__road_s = []
        self.__wall_s = []
        for i in range(len(self.__maze)):
            for j in range(len(self.__maze[0])):
                # 自分が壁なら対象外
                if self.__maze[i][j] == self.__wall_str:
                    self.__wall_s.append([i, j])
                elif self.__maze[i][j] == self.__road_str:
                    self.__road_s.append([i, j])

        # -----------------
        # 経路情報を作成する
        # -----------------
        self.reset_arrived()

    def get_road_list(self):
        """
        座標の一覧を取得(道)
        """
        return self.__road_s

    def get_wall_list(self):
        """
        座標の一覧を取得(壁)
        """
        return self.__wall_s

    def get_maze(self):
        """
        迷路情報を返す
        """
        return self.__maze

    def get_arrived_val(self, cell: []):
        return self.__arrived_s[cell[0]][cell[1]]

    def is_arrived(self, cell: []) -> bool:
        """
        指定された座標が到達済みかを返す。(-1：未到達)
        """
        if self.__arrived_s[cell[0]][cell[1]] == self.__not_arrived_val:
            return False
        else:
            return True

    def can_moved(self, cell: [], do_arrive_check: bool = True) -> bool:
        """
        指定された経路に移動できるかを返す。(True:移動可能、False:移動不可)
        """
        # 範囲外には移動できない
        if not 0 <= cell[0] < len(self.__maze) or not 0 <= cell[1] < len(self.__maze[0]):
            return False

        # 壁なら何もしない
        if self.__maze[cell[0]][cell[1]] == self.__wall_str:
            return False

        if not do_arrive_check:
            return True

        # 処理済みなら何もしない(移動したければ編集するといい)
        if self.__arrived_s[cell[0]][cell[1]] != self.__not_arrived_val:
            return False

        return True

    def set_arrived_val(self, cell: [], val):
        """
        指定された経路に到達情報を設定する。
        """
        self.__arrived_s[cell[0]][cell[1]] = val

    def reset_arrived(self):
        """
        経路の到達情報を初期化する。(おそらく、コンストラクタ以外で使うことは無い・・)
        """
        self.__arrived_s = [[self.__not_arrived_val for i in range(len(self.__maze[0]))] for j in
                            range(len(self.__maze))]

    def get1dpoint(self, cell) -> int:
        """
        座標情報を1次元に変換したものを返す。対象を1次元で管理する処理との連携に使用する。(例：UnionFind)
        """
        # 縦座標×縦幅 + 横座標 等式で、座標を一次元配列の添え字に変換する。
        return cell[0] * len(self.__maze[0]) + cell[1]

    def getcellcount(self) -> int:
        """
        座標数を返す(囲み枠を考慮した座標数を返す)
        """
        # 縦座標×縦幅 + 横座標 等式で、座標を一次元配列の添え字に変換する。
        return len(self.__maze) * len(self.__maze[0])

    def debugmazemap(self, custom_list: [] = []) -> str:
        """
        ※デバック用変数※
        迷路の情報と到達リストをテキスト形式で返す(タブ区切り)
        custom_list:
         任意の一次元配列。渡した場合、座標ごとに情報を紐づけしたものを返す。
         ※到達リスト以外のリストを作って何かを管理している場合、渡すと良い。
        """
        ans = ""
        # 迷路の情報
        for i in range(len(self.__maze)):
            ans += "\t".join(self.__maze[i]) + "\n"

        ans += "\n"
        # 到達リスト
        for i in range(len(self.__maze)):
            ans += "\t".join(map(str, self.__arrived_s[i])) + "\n"
        return ans

        # 引数なしなら上記を返して終了。
        if len(custom_list) == 0:
            return

        # 引数として一次元配列を受け取った場合、迷路の各座標と受け取った一次元配列の情報を紐づけして返す。
        ans += "\n"
        for i in range(len(self.__maze)):
            line = ""
            for j in range(len(self.__maze[0])):
                point = self.get1dpoint([i, j])
                line += str(custom_list[point]) + "\t"
            ans += line + "\n"
        return ans


# 実装を行う関数
def resolve(test_def_name=""):
    h, w = map(int, input().split())

    start = list(map(int, input().split()))
    gorl = list(map(int, input().split()))

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

    # スタート地点の候補を(=道の座標全て)を取得
    start_list = maze.get_road_list()
    que = deque()
    que.extend(start_list)

    # BFS開始
    # 距離でなく、グループ分けを行う
    group_num = 0
    while len(que) is not 0:
        now = que.popleft()

        # 自分が未処理なら、グループ番号を採番し自信をグループに所属させる。
        if not maze.is_arrived(now):
            group_num += 1
            maze.set_arrived_val(now, group_num)

        # 各方向に移動(徒歩)
        for move_h, move_w in [(1, 0), (0, 1), (0, -1), (-1, 0)]:
            target = [now[0] + move_h, now[1] + move_w]
            if not maze.can_moved(target):
                continue

            # 移動可能な場合、自分と同じエリアと判定
            maze.set_arrived_val(target, group_num)
            # キューを追加
            que.appendleft(target)

    move_target_list = [set() for a in range(group_num + 1)]
    # 再度BFS開始
    que.extend(start_list)
    while len(que) is not 0:
        now = que.popleft()

        # 各方向にワープを試してみる
        for i, j 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)]:
            # 処理対象の座標
            target = [now[0] + i, now[1] + j]
            if not maze.can_moved(target, do_arrive_check=False):
                continue

            # ワープ前後の座標のエリアが異なる場合のみ、リストに追加。
            if maze.get_arrived_val(now) != maze.get_arrived_val(target):
                move_target_list[maze.get_arrived_val(now)].add(maze.get_arrived_val(target))

    # スタート地点のエリアからBFSを実施。
    start_erea = maze.get_arrived_val(start)

    # 初期値：自分のエリアにはワープ回数0回で移動できる
    area_list = [-1 for a in range(group_num + 1)]
    area_list[start_erea] = 0

    que.appendleft(start_erea)
    while len(que) is not 0:
        now = que.popleft()

        # 移動できる対象単位でループ(例；エリア1から、2,3に移動できる、等)
        for move_target in move_target_list[now]:

            # 距離が設定済みなら何もしない
            if not area_list[move_target] == -1:
                continue

            # キューに追加
            que.append(move_target)

            # 距離を設定
            area_list[move_target] = area_list[now] + 1

    gorl_area = maze.get_arrived_val(gorl)
    print(area_list[gorl_area])

    # テストクラス


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4 4
1 1
4 4
..#.
..#.
.#..
.#.."""
        output = """1"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4 4
1 4
4 1
.##.
####
####
.##."""
        output = """-1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4 4
2 2
3 3
....
....
....
...."""
        output = """0"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """4 5
1 2
2 5
#.###
####.
#..##
#..##"""
        output = """2"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original(self):
        test_input = """4 4
2 2
3 3
....
..#.
.#..
...."""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina2(self):
        test_input = """4 4
2 2
3 3
....
..##
.#..
...."""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina3(self):
        test_input = """4 4
2 2
3 3
....
..##
##..
...."""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina4(self):
        test_input = """4 4
1 1
3 3
.#..
..##
##..
...."""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina5(self):
        test_input = """4 4
1 1
4 4
.#..
#.##
##..
...."""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina6(self):
        test_input = """4 4
1 1
4 4
.#..
#.##
####
...."""
        output = """2"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina7(self):
        test_input = """1 4
1 1
1 4
...."""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina8(self):
        test_input = """1 4
1 1
1 4
.#.."""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina9(self):
        test_input = """1 4
1 4
1 1
..#."""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina10(self):
        test_input = """4 1
4 1
1 1
.
.
#
.
"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_origina11(self):
        test_input = """4 1
1 1
4 1
.
.
#
.
"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original12(self):
        test_input = """6 6
1 1
6 6
......
......
......
......
......
......"""
        output = """0"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original13(self):
        test_input = """6 6
1 1
6 6
......
######
......
......
......
......"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original14(self):
        test_input = """6 6
1 1
6 6
......
######
######
......
......
......"""
        output = """-1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original15(self):
        test_input = """6 6
1 1
6 6
......
######
.####.
.#....
#.....
......"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original16(self):
        test_input = """6 6
1 1
6 1
......
######
.####.
.#.#.#
#..#..
....##"""
        output = """2"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original17(self):
        test_input = """6 6
3 3
6 1
......
######
.#.##.
.#.#.#
####..
....##"""
        output = """1"""
        self.assertIO(test_input, output)

    # 自作テストパターン
    def test_original17(self):
        test_input = """6 6
1 1
4 4
.#.#.#
.#.#.#
.#.#.#
.#...#
.#.#.#
.#.#.#"""
        output = """1"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil,pi,factorial,sqrt
    from operator import itemgetter
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    def LI2(): return [int(input()) for i in range(n)]
    def MXI(): return [[LI()]for i in range(n)]
    def SI(): return input().rstrip()
    def printns(x): print('\n'.join(x))
    def printni(x): print('\n'.join(list(map(str,x))))
    inf = 10**17
    mod = 10**9 + 7
#main code here!
    h,w=MI()
    sx,sy=MI()
    gx,gy=MI()
    sy-=1
    sx-=1
    gy-=1
    gx-=1
    mp=[[0]*h for i in range(w)]
    Q=deque([[sy,sx]])
    for i in range(h):
        s=SI()
        for j in range(w):
            if s[j]=="#":
                mp[j][i]=1
    #print(mp)
    turn=[[inf]*h for i in range(w)]
    turn[sy][sx]=0
    #print(turn)
    step=[[-1,0],[1,0],[0,1],[0,-1]]
    
    while Q:
        y,x=Q.popleft()
        z=turn[y][x]
        if y==gy and x==gx:
            print(turn[y][x])
            sys.exit()
        for j,i in step:
            if not (0<=y+j<w and 0<=x+i<h):
                continue
            elif mp[y+j][x+i]==1:
                continue
            else:
                if z<turn[y+j][x+i]:
                    turn[y+j][x+i]=z
                    Q.appendleft([y+j,x+i])
        #print(turn)
        for i in range(-2,3):
            for j in range(-2,3):
                if not (0<=y+j<w and 0<=x+i<h):
                    continue
                elif mp[y+j][x+i]==1:
                    continue
                else:
                    if z+1<turn[y+j][x+i]:
                        turn[y+j][x+i]=z+1
                        Q.append([y+j,x+i])
        #print(turn)
    #print(turn)
    print(-1)
        
                
                
        
        
        
        
            
            
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from collections import deque
H,W=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
Ch-=1
Cw-=1
Dh-=1
Dw-=1

S=[]
for i in range(H):
  s=list(input())
  S.append([10**10 if i =="." else -1 for i in s])
visit=[[False for i in range(W)] for j in range(H)]

dq = deque()
dq.append((Ch,Cw,0))
S[Ch][Cw]=0
counter=0

while dq:
  a=dq.popleft()
  if visit[a[0]][a[1]]==True:
    continue
  elif S[a[0]][a[1]]==counter:
    visit[a[0]][a[1]]=True
  elif a[2]==counter+1:
    visit[a[0]][a[1]]=True
    counter+=1
  for i in range(5):
    for j in range(5):
      if a[0]-2+i>=0 and a[0]-2+i<H and a[1]-2+j>=0 and a[1]-2+j<W:
        if abs(i-2)+abs(j-2)==1 and S[a[0]][a[1]]<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter
          dq.appendleft((a[0]-2+i,a[1]-2+j,counter))
        elif S[a[0]][a[1]]+1<S[a[0]-2+i][a[1]-2+j] and visit[a[0]-2+i][a[1]-2+j]==False:
          S[a[0]-2+i][a[1]-2+j]=counter+1
          dq.append((a[0]-2+i,a[1]-2+j,counter+1))
  #print(visit,counter,a,dq,"\n")
if S[Dh][Dw]==10**10:
  print(-1)
else:
  print(S[Dh][Dw])

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    h,w = LI()
    cy,cx = LI()
    gy,gx = LI()
    s = [input() for _ in range(h)]
    cy -= 1
    cx -= 1
    gy -= 1
    gx -= 1
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    bfs = [[float("inf")]*w for i in range(h)]#コスト
    bfs[cy][cx] = 0
    q = deque([(cy,cx)])
    while q:
        y,x = q.popleft()
        b = bfs[y][x]
        if (y,x) == (gy,gx):
            print(b)
            return
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "#" and b < bfs[ny][nx]:
                bfs[ny][nx] = b
                q.appendleft((ny,nx))
        nb = b+1
        for dy in range(-2,3):
            for dx in range(-2,3):
                ny,nx = y+dy,x+dx
                if 0 <= ny < h and 0 <= nx < w and s[ny][nx] != "#" and nb < bfs[ny][nx]:
                    bfs[ny][nx] = nb
                    q.append((ny,nx))
    print(-1)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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())
S = [input().rstrip() for _ in range(H)]
visited = [[False] * W for _ in range(H)]
dq = deque([(0, Ch, Cw)])
while dq:
    d, i, j = dq.popleft()
    if (i, j) == (Dh, Dw):
        print(d)
        exit()
    if visited[i][j]:
        continue
    visited[i][j] = True
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.':
            dq.appendleft((d, ni, nj))
    for di in range(-2, 3):
        for dj in range(-2, 3):
            if di == dj == 0:
                continue
            ni, nj = i + di, j + dj
            if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '.' and not visited[ni][nj]:
                dq.append((d + 1, ni, nj))
print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

dxdy4 = ((-1, 0), (0, -1), (0, 1), (1, 0))


def main():
    H, W = map(int, readline().split())
    Ch, Cw = map(int, readline().split())
    Dh, Dw = map(int, readline().split())
    S = [readline().strip() for _ in range(H)]

    Ch -= 1
    Cw -= 1
    Dh -= 1
    Dw -= 1

    dist = [[INF] * W for _ in range(H)]
    dist[Ch][Cw] = 0
    seen = [[False] * W for _ in range(H)]
    queue = deque([(Ch, Cw)])
    while queue:
        x, y = queue.popleft()
        if seen[x][y]:
            continue
        seen[x][y] = True
        for dx, dy in dxdy4:
            nx, ny = x + dx, y + dy
            if (
                0 <= nx < H
                and 0 <= ny < W
                and not seen[nx][ny]
                and (dist[nx][ny] == -1 or dist[nx][ny] > dist[x][y])
                and S[nx][ny] == '.'
            ):
                dist[nx][ny] = dist[x][y]
                queue.appendleft((nx, ny))
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if (
                    0 <= nx < H
                    and 0 <= ny < W
                    and not seen[nx][ny]
                    and dist[nx][ny] > dist[x][y] + 1
                    and S[nx][ny] == '.'
                ):
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))

    if dist[Dh][Dw] == INF:
        print(-1)
    else:
        print(dist[Dh][Dw])

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

Y, X = map(int,input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
s = [["#"]*(X+4) for _ in range(Y+4)]
for y in range(Y):
    s[y+2] = *list("##"+input()+"##"), 
inf = Y*X
c = [[inf]*X for _ in range(Y)]
c[sy-1][sx-1] = 0
drs = [[-1,0],[1,0],[0,0],[0,-1],[0,1]]
dr2s = [[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],
        [2,-2],[2,-1],[2,0],[2,1],[2,2],
        [-1,-2],[0,-2],[1,-2],
        [-1,2],[0,2],[1,2],
        [-1,-1],[-1,1],[1,-1],[1,1]
       ]

q = deque([(sy-1, sx-1)])

while q:
    y,x = q.popleft()
    cost = c[y][x]
    for dx,dy in drs:
        x2 = x+dx
        y2 = y+dy
        if s[y2+2][x2+2] == "." and c[y2][x2] > cost:
            c[y2][x2] = cost
            q.appendleft((y2,x2))
    for dy, dx in dr2s:
        x2 = x+dx
        y2 = y+dy
        if s[y2+2][x2+2] == "." and c[y2][x2] > cost+1:
            c[y2][x2] = cost+1
            q.append((y2,x2))
    
if c[gy-1][gx-1] == inf:
    print("-1")
else:
    print(c[gy-1][gx-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())

L=[]
for h in range(H):
    s=list(input())
    L.append(s)

def isOK(h,w):
    if 0<=h<H and 0<=w<W:
        if L[h][w]==".":
            return True
    return False

que=deque([(ch-1,cw-1,0)])
DX=[0,1,0,-1]
DY=[1,0,-1,0]

cost=[[-1]*W for _ in range(H)]
cost[ch-1][cw-1]=0
count=0
while que:
    lis=[]
    while que:
        
        t=que.popleft()
        x,y,now=t
        lis.append((x,y))
        for i in range(4):
            dx=DX[i]
            dy=DY[i]
            nx=x+dx
            ny=y+dy
            if isOK(nx,ny):
                if cost[nx][ny]==-1:
                    cost[nx][ny]=now
                    que.append((nx,ny,now))
                    lis.append((nx,ny))
    for t in lis:
        x,y=t
        for dx in range(-2,3):
            for dy in range(-2,3):
                if abs(dx)+abs(dy)<=1:
                    continue
                nx=x+dx
                ny=y+dy
                if isOK(nx,ny):
                    if cost[nx][ny]==-1 or cost[nx][ny]>count+1:
                        cost[nx][ny]=count+1
                        que.append((nx,ny,count+1))
    count+=1


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

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

visit=defaultdict(lambda: 0) #0:未訪問、1:訪問済み
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==DH and fro_w==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:
# -*- 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))

visit=defaultdict(lambda: 0) #0:未訪問、1:訪問済み
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==DH and fro_w==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)] and visit[(to_h, to_w)]==0:
            visit[(to_h, to_w)]==1
            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)] and visit[(to_h, to_w)]==0:
            visit[(to_h, to_w)]==1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

print -1

Submission status: Accepted

Solution code:

import sys
from collections import deque
def main():
    movey = (0, -1, 0, 1)
    movex = (1, 0, -1, 0)
    warpy = (-2, -2, -2, -2, -2, -1, -1, -1, -1,  0, 0,  1,  1, 1, 1, 2, 2, 2, 2, 2)
    warpx = (-2, -1,  0,  1,  2, -2, -1,  1,  2, -2, 2, -2, -1, 1, 2, -2, -1, 0, 1, 2)

    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
    dummy = tuple(['#'] * (w + 4))
    maze = {e: [] for e in range(h + 4)}
    maze[0] = dummy
    maze[1] = dummy
    for i in range(h):
        row = ['#'] + ['#'] + list(input()) + ['#'] + ['#']
        maze[i+2] = row
    maze[h+2] = dummy
    maze[h+3] = dummy
    maze[ch][cw] = 0
    maze[dh][dw] = 'g'

    nodes = deque()
    nodes.append((ch, cw))
    res = []
    while nodes:
        (n_y, n_x) = nodes.popleft()
        cur_masu = maze[n_y][n_x]
        flag = False
        for j1 in range(4):
            ny = n_y + movey[j1]
            nx = n_x + movex[j1]
            next_masu = maze[ny][nx]
            if next_masu == 'g':
                res.append(cur_masu)
            elif next_masu == '.':
                maze[ny][nx] = cur_masu
                nodes.appendleft((ny, nx))
            elif next_masu == '#':
                flag = True
            elif next_masu > cur_masu:
                maze[ny][nx] = cur_masu
                nodes.appendleft((ny, nx))
        if flag:
            for j1 in range(20):
                ny = n_y + warpy[j1]
                nx = n_x + warpx[j1]
                next_masu = maze[ny][nx]
                if next_masu == 'g':
                    res.append(cur_masu+1)
                elif next_masu == '.':
                    maze[ny][nx] = cur_masu + 1
                    nodes.append((ny, nx))
                elif next_masu == '#':
                    pass
                elif next_masu > cur_masu + 1:
                    maze[ny][nx] = cur_masu + 1
                    nodes.append((ny, nx))

    if res:
        print(min(res))
    else:
        print(-1)

if __name__ == '__main__':
    main()

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())) # ゴール
D_y = D[0] -1 # 0スタート
D_x = D[1] -1 # 0スタート
S = [list(input()) for _ in range(H)]
visited = [[-1] * W for _ in range(H)]
visited[C[0]-1][C[1]-1] = 0 # 初期値
moves = [(1, 0), (0, 1), (-1, 0), (0, -1)] # 普通の移動
main_q = deque()
magic_q = deque() # マジック用のキュー
main_q.append((C[0]-1, C[1]-1))
#---------------------------------[BFS]---------------------------------#
while main_q:
    y, x = main_q.popleft()
    magic_q.append((y, x))
    for move in moves:
        dy, dx = move
        moved_y = y + dy
        moved_x = x + dx

        if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
            continue
        if S[moved_y][moved_x] == '#':
            continue
        if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
            main_q.append((moved_y, moved_x))
            visited[moved_y][moved_x] = visited[y][x]
    #---------------------------------[マジック用のBFS]---------------------------------#
    if not main_q: # main_qが空になった場合は探索済みからマジックを使う
        while magic_q:
            y, x = magic_q.popleft()
            for dy in range(-2, 3):
                for dx in range(-2, 3):
                    moved_y = y + dy
                    moved_x = x + dx

                    if moved_y < 0 or H -1 < moved_y or moved_x < 0 or W -1 < moved_x:
                        continue
                    if S[moved_y][moved_x] == '#':
                        continue
                    if S[moved_y][moved_x] == '.' and visited[moved_y][moved_x] == -1:
                        main_q.append((moved_y, moved_x))
                        visited[moved_y][moved_x] = visited[y][x] + 1
#---------------------------------[回答表示]---------------------------------#
answer = visited[D_y][D_x]
print(answer)