ABC246 E - Bishop 2

atcoder.jp

基本的にはゴリゴリ探索し、枝狩り（というのか？）する。何法っていうのかよくわからない。
ただし、本番中には枝狩り不足で通せず。ソース整理してコメントも残したので、置いておきます。

def resolve():
    N = int(input())
    Ax, Ay = map(int, input().split())
    Bx, By = map(int, input().split())
    S = []
    for i in range(N):
        S.append(list(input()))
 
    if Ax == Bx and Ay == By:
        print(0)
        return
 
    # i手目で到達可能なマスの集合。0手目を(Ax,Ay)として更新していく
    cand = [set() for i in range(N ** 2)]
    cand[0].add((Ax - 1, Ay - 1))
    # 既に探索済の集合も管理していく(重複の防止)
    seen = set()
    seen.add((Ax - 1, Ay - 1))
 
    dx = [1, 1, -1, -1]
    dy = [1, -1, -1, 1]
 
    for i in range(1, N ** 2):
        # i-1で到達可能マスそれぞれから、4方向に進めるだけ進んで、i手目の一覧を作る
        for Cx, Cy in cand[i - 1]:
            for j in range(4):
                diffx = dx[j]
                diffy = dy[j]
                while True:
                    # 範囲外もしくはポーンにぶつかったら打ち切り
                    if not (
                        0 <= Cx + diffx < N
                        and 0 <= Cy + diffy < N
                        and S[Cx + diffx][Cy + diffy] == "."
                    ):
                        break
                    # 探索済のマスは追加しない。
                    # ただし、その先は要探索かもしれないので、打ち切らない。
                    # 既に通った経路と直行してるだけかもしれない。
                    if not (Cx + diffx, Cy + diffy) in seen:
                        cand[i].add((Cx + diffx, Cy + diffy))
                        seen.add((Cx + diffx, Cy + diffy))
                        # 新規の移動(到達可能マス扱い)時に、ゴールと一致したら、手数を出力
                        if Cx + diffx == Bx - 1 and Cy + diffy == By - 1:
                            print(i)
                            return
                    # i-1手の到達済に今差し掛かるということは、その到達済マスを起点として、
                    # i手目の他経路にて、探索済or探索する予定なので、打ち切ってよい。
                    if (Cx + diffx, Cy + diffy) in cand[i - 1]:
                        break
                    diffx += dx[j]
                    diffy += dy[j]
 
    print(-1)