Đếm số đường đi có khoảng cách Manhattan giữa hai điểm trong C++

Cho 4 biến x1, x2, y1, y2 đại diện cho hai điểm (x1, y1) và (x2, y2) trên mặt phẳng 2D. Tìm số đường đi có độ dài bằng khoảng cách Manhattan giữa hai điểm.

Khoảng cách Manhattan

MD = |x1 - x2| + |y1 - y2|. Gọi A = |x1-x2|, B = |y1-y2|. Mọi đường đi Manhattan có A+B cạnh: A cạnh ngang, B cạnh dọc. Số tổ hợp = C(A+B, B) = (A+B)! / (A! B!).

Ví dụ

Đầu vào − x1=6, y1=8, x2=2, y2=10

Đầu ra − 15

Phương pháp giải

Tính hệ số nhị thức C(A+B, B) bằng hàm bio_coeff (tính tổ hợp hiệu quả).

• Hàm bio_coeff(int A, int B) tính C(A,B) bằng nhân chia lần lượt.
• Hàm Manhattan_distance(int x1, int y1, int x2, int y2):
  • A = abs(x1-x2), B = abs(y1-y2).
  • Trả về bio_coeff(A+B, B).

Ví dụ code

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

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

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 of paths with distance equal to Manhattan distance are: " << Manhattan_distance(x1, y1, x2, y2);
    return 0;
}

Đầu ra

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