हमें चर x1, x2, y1, y2 दिए गए हैं जो 2D निर्देशांक प्रणाली पर दो बिंदुओं का प्रतिनिधित्व करते हैं (x1, y1) और (x2, y2)। लक्ष्य उन सभी रास्तों को खोजना है जिनकी दूरी इन दो बिंदुओं के बीच मैनहट्टन की दूरी के बराबर होगी।
मैनहट्टन दूरी
मैनहट्टन दो बिंदुओं (x1, y1) और (x2, y2) के बीच की दूरी है -
एमडी =|x1 - x2| + |y1 - y2|
आइए A=|x1 - x2| . लें और बी=|y1 - y2|
एमडी के बराबर मैनहट्टन दूरी वाले सभी पथों के किनारों की गणना (ए + बी) के रूप में की जाएगी। एक क्षैतिज किनारा और बी लंबवत किनारों। तो (ए+बी) किनारों का 2 समूहों में विभाजित संभावित संयोजन (ए + बी) सीबी =(ए + बी) होगा! / (ए!)(बी!)
आइए उदाहरणों के साथ समझते हैं
इनपुट
आउटपुट - ग्रिड में दी गई दिशा में संभावित चालों की संख्या है - 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. इनपुट - ए =4, बी =4, एक्स =2, वाई =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. नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
इस दृष्टिकोण में, हम जोड़ी के रूप में चरणों का प्रतिनिधित्व करने वाला एक वेक्टर बनाएंगे
किसी विशेष दिशा में जाने के लिए, यदि वक्र स्थिति 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<लंबाई-1.
. तक अनुप्रस्थ सरणी -
अगर arr[i] 0 है, तो अनुक्रमणिका j=i+1 से 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