数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 统计曼哈顿距离相等的路径数
给定变量 x1、x2、y1、y2，表示二维坐标系上的两个点 (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 - 当前位置 )/x。如果小于，则到达 1 的移动次数为 ( 当前位置 - 1 )/x。
创建一个包含 0 和 1 的数组 arr[]。
函数 count_cars(int arr[], int size) 以数组和长度作为输入，并返回通过汽车的数量。
将初始计数设置为 0。
从索引 i=0 遍历数组到 i<length-1。
如果 arr[i] 为 0，则再次从索引 j=i+1 遍历数组到 j<length。
对于每个 arr[j] 为 1，将计数增加 1，因为对 (arr[i],arr[j]) 为 (0,1) 且 i<j。
最后我们将得到总计数。
返回计数作为结果。
示例
#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
382 次浏览
