デカルト平面の任意の 2 点間の最小マンハッタン距離は、それぞれの X 軸と Y 軸の絶対差の合計です。同様に、2 つの点 (X,Y) と (U,V) がある場合、距離は ABS(XU) + ABS(YV) になります。さて、選択したパスで特定のポイントを訪れる必要がないように、座標軸に平行にのみ移動するポイントのいくつかのペア間の最小距離をどのように決定する必要がありますか。回避されたポイントの数は、クエリ数の同じ範囲で最大 10000 の範囲になる可能性があるため、非常に効率的なアルゴリズムが必要です。ポイントの座標は ABS(50000) より小さくなります。最初に避けるべき点のセットが与えられるので、オフラインのアルゴリズムや事前計算を使用することがあります。
例として、(0,0) と (1,1) の間のマンハッタン距離は、パス (0,0)->(1,0)->(1,1) または (0,0)- のいずれかから 2 です。 >(0,1)->(1,1)。しかし、(1,0) と (0,1) を訪問できないという条件が与えられた場合、最小距離は 6 に増加します。そのようなパスの 1 つが次のようになります: (0,0)->(0,-1) )->(1,-1)->(2,-1)->(2,0)->(2,1)->(1,1)。