Pythonで中継点を経由して現在位置から目的地に到達できるか判定するプログラム

問題の概要

2次元平面上に、座標 (px, py) の地点 p に置かれたポインタがあるとします。このポインタを、別の地点 q(座標 qx, qy)まで移動させたいのですが、ポインタは自由に動けるわけではありません。途中に配置された点をたどることでしか、目的地へは到達できません。

ここで、複数の座標点を格納した配列 paths が与えられます。ポインタは、現在位置から上下左右に1マス離れた点、すなわち (x+1, y)、(x, y+1)、(x−1, y)、(x, y−1) のいずれかに該当する点であれば、そこへ移動できます。

さらに重要なルールとして、paths に含まれる点は必ず配列の先頭から順番に処理しなければなりません。仮にその時点で移動が行えない点であっても、処理はスキップされず、通過カウントに含まれます。

開始地点と目的地が与えられたとき、ポインタが目的地に到達できるかどうかを判定してください。到達できる場合は通過した点の総数を出力し、到達できない場合は −1 を出力します。

入力例と実行結果

たとえば、px = 1、py = 1、qx = 2、qy = 3、paths = [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]] という入力に対しては、出力は 4 になります。

点を順番に処理していくと、次のような流れになります。

• 点 (1, 2):移動が成立し、現在位置は (1, 2) になります。通過点数:1
• 点 (0, 1):移動は成立せず、現在位置は (1, 2) のままです。通過点数:2
• 点 (0, 2):移動は成立せず、現在位置は (1, 2) のままです。通過点数:3
• 点 (1, 3):移動が成立し、現在位置は (1, 3) になります。通過点数:4

この時点で、目的地 (2, 3) は現在位置 (1, 3) から見て (x+1, y) の関係にあるため、通過した点の総数は 4 となります。

解法のアプローチ

この問題は「幅優先探索(BFS)+ 二分探索」を組み合わせることで効率的に解けます。考え方の核は次のとおりです。

• 使用できる点の数 k が増えるほど到達範囲は単調に広がる(一度到達できれば、点を追加しても到達可能なまま)ため、二分探索で「目的地に到達できる最小の k」を絞り込めます。
• 各判定では、BFS を用いて開始地点から目的地へたどり着けるかを確認します。

手順の詳細

1. helper(k) 関数を定義します。引数 k は、paths の先頭から何個の点を使うかを表します。
   • vertices := 始点 (px, py) と終点 (qx, qy) を含む新しい集合(set)
   • paths の先頭から k 番目までの各点 (x, y) を vertices に追加する
   • trav := 始点 (px, py) を格納した新しい deque(両端キュー)
   • trav が空になるまで次を繰り返す:
     • trav の左端から要素を取り出し、(x, y) とする
     • (x, y) が (qx, qy) と一致したら True を返す
     • 4方向の隣接点 (kx, ky)、すなわち (x−1, y)、(x+1, y)、(x, y−1)、(x, y+1) のそれぞれについて、(kx, ky) が vertices に存在すれば、trav の末尾に追加し、vertices から削除する(再訪防止)
   • キューが空になっても目的地に届かなければ False を返す
2. 二分探索で最小の k を求めます。
   • ll := −1、ul := len(paths) + 1 と初期化する
   • ll + 1 < ul の間、次を繰り返す:
     • k := ll + (ul − ll) // 2(中央値)
     • helper(k) が True なら ul := k、そうでなければ ll := k
   • ul が len(paths) 以下なら ul を返し、それ以外は −1 を返す

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

from collections import deque

def solve(px, py, qx, qy, paths):
    def helper(k):
        # 始点・終点と、先頭k個の中継点を候補頂点として登録
        vertices = {(px, py), (qx, qy)}
        for x, y in paths[:k]:
            vertices.add((x, y))
        # 幅優先探索(BFS)で目的地への到達可否を判定
        trav = deque([(px, py)])
        while trav:
            x, y = trav.popleft()
            if (x, y) == (qx, qy):
                return True
            for kx, ky in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                if (kx, ky) in vertices:
                    trav.append((kx, ky))
                    vertices.remove((kx, ky))
        return False

    # 二分探索で「到達可能となる最小の点数」を求める
    ll, ul = -1, len(paths) + 1
    while ll + 1 < ul:
        k = ll + (ul - ll) // 2
        if helper(k):
            ul = k
        else:
            ll = k
    return ul if ul <= len(paths) else -1

print(solve(1, 1, 2, 3, [[1, 2], [0, 1], [0, 2], [1, 3], [3, 3]]))

入力

1, 1, 2, 3, [[1, 2],[0, 1],[0, 2],[1, 3],[3, 3]]

出力

4

まとめ

本記事では、2次元平面上のポインタが中継点を経由して目的地に到達できるかを判定する問題を扱いました。BFSで到達可能性を判定し、二分探索で必要な中継点の最小数を絞り込むことで、計算量を O(N log N)(N は点の数)程度に抑えられます。到達可能性が点の追加に対して単調であることを利用するのが、この手法のポイントです。