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