मैनहट्टन दूरी के बराबर दूरी वाले पथों की गणना

समस्या विवरण

हमें दो बिंदु (x1, y1) और (x2, y2) दिए गए हैं। लक्ष्य उन सभी पथों की गणना करना है जिनकी दूरी इन बिंदुओं के बीच मैनहट्टन दूरी के बराबर हो।

मैनहट्टन दूरी

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

मान लें A = |x1 - x2|, B = |y1 - y2|।

मैनहट्टन दूरी वाले सभी पथों में A क्षैतिज और B लंबवत किनारे होंगे। संभावित संयोजन = (A+B)C(B) = (A+B)! / (A! * B!)।

उदाहरण

इनपुट: x1=6, y1=8, x2=2, y2=10

आउटपुट: 15

व्याख्या: A=4, B=2, 6C2 = 15

दृष्टिकोण

द्विपद गुणांक C(A+B, B) की गणना करें। ओवरफ्लो से बचने के लिए पुनरावृत्त तरीके से गणना करें।

एल्गोरिदम

A = abs(x1-x2), B = abs(y1-y2)
यदि B > A-B तो B = A-B
result = 1
i=0 से B-1 तक:
- result = result * (A - i) / (i + 1)
result लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

long long bio_coeff(int A, int B) {
    long long result = 1;
    if (B > A - B) B = A - B;
    for (int i = 0; i < B; i++) {
        result = result * (A - i);
        result = result / (i + 1);
    }
    return result;
}

long long 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: " << Manhattan_distance(x1, y1, x2, y2);
    return 0;
}

आउटपुट

Count: 15

मैनहट्टन दूरी के बराबर दूरी वाले पथों की गणना - C++

समस्या विवरण