আমাদেরকে 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) হিসাবে গণনা করা হবে। একটি অনুভূমিক প্রান্ত এবং B উল্লম্ব প্রান্ত। সুতরাং 2টি গ্রুপে বিভক্ত (A+B) প্রান্তগুলির সম্ভাব্য সংমিশ্রণ হবে ( 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৷
-
0's এবং 1's সম্বলিত একটি অ্যারে arr[] নিন।
-
ফাংশন 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
