C++の2Dバイナリ配列の最良の出会い点

この問題では、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