เราได้รับตัวแปร x1, x2, y1, y2 แทนจุดสองจุดบนระบบพิกัด 2 มิติเป็น (x1, y1) และ (x2, y2) เป้าหมายคือการหาเส้นทางทั้งหมดที่มีระยะทางเท่ากับระยะทางแมนฮัตตันระหว่างจุดทั้งสองนี้
ระยะทางแมนฮัตตัน
แมนฮัตตัน ระยะห่างระหว่างจุดสองจุด (x1, y1) และ (x2, y2) คือ −
MD=|x1 – x2| + |y1 – y2|
เอา A=|x1 – x2| และ B=|y1 – y2|
เส้นทางทั้งหมดที่มีระยะทางแมนฮัตตันเท่ากับ MD จะนับเป็น (A+B) ขอบแนวนอนและขอบแนวตั้ง 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; เคลื่อนที่ ={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. แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในแนวทางนี้ เราจะสร้างเวกเตอร์ที่แสดงขั้นตอนเป็นคู่
หากต้องการเคลื่อนที่ไปในทิศทางใดทิศทางหนึ่ง หากตำแหน่ง cur x ( หรือ y ) คือ> n (หรือ m) จำนวนการเคลื่อนที่ที่จะไปถึง n (หรือ m) คือ ( ตำแหน่ง n - cur )/x หากน้อยกว่านั้นจำนวนการเคลื่อนไหวที่จะไปถึง 1 คือ ( ตำแหน่ง cur - 1 )/x.
-
ใช้อาร์เรย์ arr[] ที่มี 0 และ 1
-
ฟังก์ชัน count_cars(int arr[], int size) ใช้อาร์เรย์และความยาวเป็นอินพุตและคืนค่าจำนวนรถที่ผ่าน
-
นับเริ่มต้นเป็น 0
-
อาร์เรย์การเคลื่อนที่จากดัชนี i=0 ถึง i
-
ถ้า arr[i] เป็น 0 ให้ข้ามอาร์เรย์อีกครั้งจากดัชนี j=i+1 ถึง j
-
สำหรับแต่ละ arr[j] เพิ่มขึ้น 1 ครั้ง นับเป็นคู่ (arr[i],arr[j]) คือ (0,1) และ i
-
ในที่สุดเราก็จะได้ยอดรวม
-
ผลตอบแทนนับเป็นผลลัพธ์
ตัวอย่าง
#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
