数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社科
时尚研究
法律研究2D 二进制数组最佳会议地点（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
更新于: 22-11-2019
140 次浏览
广告