আমাদের দুটি বিন্দু (x1, y1) এবং (x2, y2) দেওয়া আছে। লক্ষ্য হল ম্যানহ্যাটান দূরত্বের সমান দূরত্বով পথের সংখ্যা বের করা।
ম্যানহ্যাটান দূরত্ব
MD = |x1 - x2| + |y1 - y2|
মনে করুন A = |x1 - x2| এবং B = |y1 - y2|। ম্যানহ্যাটান দূরত্বের সমান পথগুলোর এজ সংখ্যা = A + B। এদের মধ্যে Aটি হরিজন্টাল এবং Bটি ভার্টিক্যাল এজ। সম্ভাব্য পথ সংখ্যা = C(A+B, B) = (A+B)! / (A! * B!)।
উদাহরণ
ইনপুট: x1=6, y1=8, x2=2, y2=10
আউটপুট: ১৫
C++ বাস্তবায়ন
#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);
return bio_coeff(A + B, B);
}
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
