Pythonで指定されたポイントを介して、現在の位置からポイントに到達できることを確認するプログラム

2D空間で、座標（px、py）を持つ点pにポインターが配置されているとします。ここで、ポインタは座標（qx、qy）を持つ別の点qに移動する必要があります。ポインタは自由に動くことができず、間にいくつかの点がある場合はqに移動できます。さまざまな座標点を含む点「パス」の配列が与えられます。ポインターは、ポインターの現在の位置から（x + 1、y）または（x、y + 1）または（x-1、y）または（x、y-1）にある場合、その点に移動できます。 。配列の「パス」内の指定されたポイントは、順番に処理する必要があります。つまり、移動できない場合でも、配列内の各ポイントを合計パスに加算する必要があります。したがって、開始点と目的地を指定して、ポインターが指定された点から目的地に到達できるかどうかを確認する必要があります。可能であれば、目的地に到達するために通過したポイントの総数を印刷します。印刷できない場合は-1を出力します。

したがって、入力がpx =1、py =1、qx =2、qy =3の場合、パス=[[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。

目的地は現在のポインタ位置から（x + 1、y）の位置にあるため、通過したポイントの総数は4です。

これを解決するには、次の手順に従います-

• 関数helper（）を定義します。これにはk
  かかります
  • 頂点：=ペア（px、py）と（qx、qy）を含む新しいセット
  • 位置kまでのパスのx、yごとに、
    • ペア（x、y）を頂点に追加します
  • trav：=ペア（px、py）を含む新しい両端キュー
  • travが空でない間は、
    • pair（x、y）：=travから左端のアイテムをポップ
    • （x、y）が（qx、qy）と同じ場合、
      • Trueを返す
    • 各kxについて、ky in（（x --1、y）、（x + 1、y）、（x、y – 1）、（x、y + 1））、do
      • ペア（kx、ky）が頂点に存在する場合、
        • travの最後にペア（kx、ky）を挿入します
        • 頂点からペア（kx、ky）を削除します
    • Falseを返す
• ll：=-1
• ul：=パスのサイズ+ 1
• ll + 1
• k：=ll +（（ul --ll）/ 2）のフロア値
• helper（k）がTrueの場合、
  • ul：=k
• それ以外の場合、
  • ll：=k

例

理解を深めるために、次の実装を見てみましょう-

from collections import deque
def solve(px, py, qx, qy, paths):
   def helper(k):
      vertices = {(px, py), (qx, qy)}
      for x, y in paths[:k]:
         vertices.add((x, y))
      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