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