นับเส้นทางที่มีระยะทางเท่ากับระยะทางแมนฮัตตันใน C++

เราได้รับตัวแปร x1, x2, y1, y2 แทนจุดสองจุดบนระนาบพิกัด 2D เป็น (x1, y1) และ (x2, y2) เป้าหมายคือหาเส้นทางทั้งหมดที่จะมีระยะทางเท่ากับระยะทางแมนฮัตตันระหว่างจุดสองจุดนี้

ระยะทางแมนฮัตตัน

ระยะทางแมนฮัตตันระหว่างจุดสองจุด (x1, y1) และ (x2, y2) คือ −

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

สมมติ A = |x1 – x2| และ B = |y1 – y2|

เส้นทางทั้งหมดที่มีระยะทางแมนฮัตตันเท่ากับ MD จะมีจำนวนขอบเป็น (A+B) ขอบแนวนอน A ขอบแนวตั้ง B ดังนั้นการจัดเรียงที่เป็นไปได้ของ (A+B) ขอบแบ่งเป็น 2 กลุ่มจะเป็น (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; moves = {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<int,int> เริ่มเดินทางจากจุด x,y เลือกขั้นตอนจากเวกเตอร์และเลือกค่าต่ำสุดของค่าที่ใช้ในทั้งสองทิศทาง (แกน x และแกน y) ค่าต่ำสุดที่เลือกจะทำให้เคลื่อนที่ได้มากขึ้น

เพื่อเคลื่อนที่ในทิศทางเฉพาะ หากตำแหน่งปัจจุบัน x (หรือ y) > n (หรือ m) จำนวนขั้นตอนเพื่อไปถึง n (หรือ m) คือ (n - cur position)/x หากน้อยกว่า จำนวนขั้นตอนเพื่อไปถึง 1 คือ (cur position - 1)/x

• รับอาเรย์ arr[] ที่มี 0 และ 1
• ฟังก์ชัน count_cars(int arr[], int size) รับอาเรย์และความยาว คืนจำนวนรถที่ผ่านกัน
• กำหนด count เริ่มต้น 0
• เดินทางอาเรย์จากดัชนี i=0 ถึง i<length-1
• ถ้า arr[i] เป็น 0 เดินทางอาเรย์อีกครั้งจากดัชนี j=i+1 ถึง j<length
• สำหรับแต่ละ arr[j] เป็น 1 เพิ่ม count เพราะคู่ (arr[i],arr[j]) เป็น (0,1) และ i<j
• ท้ายสุดเราจะได้จำนวนรวม
• คืน count

ตัวอย่างโค้ด 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);
    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