C++에서 맨해튼 거리와 동일한 거리로 경로 계산

<시간/>

2D 좌표계의 두 점을 (x1, y1) 및 (x2, y2)로 나타내는 변수 x1, x2, y1, 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!)

C++에서 맨해튼 거리와 동일한 거리로 경로 계산

예를 들어 이해하자

입력

출력 − 그리드에서 주어진 방향으로 가능한 이동 수는 − 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.

아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.

이 접근 방식에서는 단계를 pair로 나타내는 벡터를 생성합니다. x,y 지점에서 횡단을 시작합니다. 벡터에서 한 단계를 선택하고 양방향(x축 및 y축)에서 취한 값의 최소값을 선택합니다. 선택한 최소값은 더 많은 이동을 허용합니다.

특정 방향으로 이동하기 위해 현재 위치 x(또는 y)가> n(또는 m)이면 n(또는 m)에 도달하기 위한 이동 횟수는 ( n - 현재 위치 )/x입니다. 이보다 작으면 1에 도달하기 위한 이동 수는 ( 현재 위치 - 1 )/x입니다.

0과 1을 포함하는 배열 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