C++でマンハッタン距離と等しい距離を持つパスの数を求める方法

2次元座標系上の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| とおきます。

マンハッタン距離と等しい距離を持つすべてのパスは、合計 (A + B) 本の移動で構成されます。そのうち A 本が水平方向の移動、B 本が垂直方向の移動に対応します。したがって、(A + B) 回の移動を「水平方向のグループ」と「垂直方向のグループ」の2つに分ける組み合わせの総数は、二項係数を用いて次のように表せます。

(A + B) C B = (A + B)! / (A! × B!)

具体例で確認しましょう。

入力: x1 = 6, y1 = 8, x2 = 2, y2 = 10

出力: マンハッタン距離と等しい距離を持つパスの数: 15

説明:

A = |6 − 2| = 4、B = |8 − 10| = 2
(4 + 2) C 2 = 6! / (4! × 2!) = 720 / (24 × 2) = 15

アルゴリズムのアプローチ

この問題は、二項係数を計算することで効率的に解くことができます。手順は以下の通りです。

• 2点間の水平方向の差 A = |x1 − x2| と垂直方向の差 B = |y1 − y2| を計算します。

• 二項係数 C(A + B, B) を求める関数 bio_coeff() を用意します。

• bio_coeff() では、対称性 C(n, k) = C(n, n−k) を利用して、B と (A − B) のうち小さい方を採用することで、ループの回数を減らしています。

• ループ内では、temp に (A − i) を掛けてから (i + 1) で割ることで、中間値が極端に大きくなるのを防ぎつつ、オーバーフローを抑えながら二項係数を計算します。

• Manhattan_distance() 関数で A と B を算出し、bio_coeff(A + B, B) の結果を答えとして返します。

実装例

#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

このように、マンハッタン距離と等しい距離を持つパスの数は、組み合わせの公式を利用することで O(min(A, B)) の計算量で効率的に求められます。全経路を列挙する必要がないため、A と B が大きい場合でも高速に動作する点がこのアプローチの大きな利点です。