C ++中2D二进制数组的最佳集合点
在这个问题中，我们得到一个二维二进制数组，即它的值为0或1，其中1被标记为该组人的住所。一群人想见面。因此，他们需要最小化他们在一个共同点开会所需的总距离。有效的集合点可以在任何地方，但不能在任何人家里。
为了找到最小距离，将创建一个公式，该公式被称为曼哈顿距离，其中距离-
(p1,p2)=|p2.x|+|p2.y-p1.y|。
让我们举例说明一下
示例
Input:
{10001}
{00000}
{00100}
Output: 6说明-此处的最佳会合点是(0,2)，使行进的距离等于6（2+2+2）。
现在，让我们为这个问题创建一个解决方案。在这里，我们必须从数组中标记为1的所有点中找到一个中间点。我们将通过分别找到水平和垂直中心（中间点）来实现。我正在寻找该点与所有1标记点的距离。
算法
Step 1 : Create two structures with the values of horizontal and vertical positions of the points Marked one. Step 2 : In both this structures, find the mid positions and treat (midx, midy) it as the meeting point. Step 3 : Calculate the distance of each point it to the mid. Step 4 : return the sum of all distances.
示例
让我们基于该算法创建一个算法-
#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 5
int minMeetingDistance(int grid[][COL]) {
if (ROW == 0 || COL == 0)
return 0;
vector<int> vertical;
vector<int> horizontal;
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
if (grid[i][j] == 1) {
vertical.push_back(i);
horizontal.push_back(j);
}
}
}
sort(vertical.begin(),vertical.end());
sort(horizontal.begin(),horizontal.end());
int size = vertical.size()/2;
int midx = vertical[size];
int midy = horizontal[size];
int distance = 0;
for (int i = 0; i < ROW; i++)
for (int j = 0; j < COL; j++)
if (grid[i][j] == 1)
distance += abs(midx - i) + abs(midy - j);
return distance;
}
int main() {
int distance[ROW][COL] =
{{1, 0, 1, 0, 1},
{0, 0, 0, 1, 0},
{0, 1, 1, 0, 0}};
cout<<"The minimum distance travelled to meet is "<<minMeetingDistance(distance);
return 0;
}输出结果
The minimum distance travelled to meet is 11