C++でマンハッタン距離に等しい距離のパスをカウントします

2D座標系上の2つの点を（x1、y1）および（x2、y2）として表す変数x1、x2、y1、y2が与えられます。目標は、これら2つのポイント間のマンハッタン距離に等しい距離を持つすべてのパスを見つけることです。

マンハッタン距離

マンハッタン2点（x1、y1）と（x2、y2）の間の距離は-

MD =| x1 – x2 | + | y1 – y2 |

A =| x1 –x2|を取りましょうおよびB=| y1 – y2 |

マンハッタン距離がMDに等しいすべてのパスでは、エッジが（A + B）としてカウントされます。水平エッジとB垂直エッジ。したがって、2つのグループに分割された（A + B）エッジの可能な組み合わせは、（A + B）CB =（A + B）になります。 /（A！）（B！）

例を挙げて理解しましょう

入力

出力 −グリッド内の特定の方向への可能な移動の数は− 6

説明

Choosing move {1,1} = (1,1) → (2,2) → (3,3) - 3 steps
Choosing move {0,-1} = (3,2) → (3,3) → (3,2) → (3,1) - 3 steps
Total 6 steps.

入力 − A =4、B =4、x =2、y =2;移動={2、1}、{-2、-3}

出力 −グリッド内の特定の方向への可能な移動の数は− 2

説明

Choosing move {2,1} = (2,2) → (4,3) - 2 steps
Choosing move {-2,-3} = (2,0) X out of bound
Total 2 steps.

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、ステップをpair として表すベクトルを作成します。ポイントx、yからトラバースを開始します。ベクトルからステップを選択し、両方向（x軸とy軸）で取得される値の最小値を選択します。選択した最小値により、より多くの動きが可能になります。

特定の方向に移動するには、cur位置x（またはy）が> n（またはm）の場合、n（またはm）に到達するための移動回数は（n-cur位置）/xです。それより少ない場合、1に到達するまでの移動回数は（cur position-1）/xです。

• 0と1を含む配列arr[]を取ります。

• 関数count_cars（int arr []、int size）は、配列と長さを入力として受け取り、通過する車の数を返します。

• 初期カウントを0とします。

• 配列をインデックスi=0からiまでトラバースします。

• arr [i]が0の場合、配列をインデックスj =i+1からjまで再度トラバースします。

• 1インクリメントとしての各arr[j]について、ペア（arr [i]、arr [j]）は（0,1）およびiとしてカウントされます。

• 最後に、合計数を取得します。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
long long int bio_coeff(int A, int B){
   long long int temp = 1;
   if (B > A - B){
      B = A - B;
   }
   for (int i = 0; i < B; ++i){
      temp = temp * (A - i);
      temp = temp / (i + 1);
   }
   return temp;
}
long long int Manhattan_distance(int x1, int y1, int x2, int y2){
   int A = abs(x1 - x2);
   int B = abs(y1 - y2);
   int count = bio_coeff(A + B, B);
   return count;
}
int main(){
   int x1 = 6, y1 = 8, x2 = 2, y2 = 10;
   cout<<"Count of paths with distance equal to Manhattan distance are: "<<
   Manhattan_distance(x1, y1, x2, y2);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of paths with distance equal to Manhattan distance are: 15