Điểm gặp gỡ tốt nhất trong mảng nhị phân 2D trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng nhị phân 2D, tức là nó có các giá trị là 0 hoặc 1, trong đó 1 được đánh dấu là nhà của một người trong nhóm. Và những người trong nhóm muốn gặp gỡ. Vì vậy, họ cần phải giảm thiểu tổng quãng đường di chuyển của họ để có thể gặp nhau tại một điểm chung. Điểm gặp hợp lệ có thể ở bất kỳ đâu nhưng không phải ở nhà của bất kỳ ai.

Để tìm khoảng cách tối thiểu, một công thức được tạo, công thức này được đặt tên là khoảng cách manhattan, trong đó khoảng cách -

(p1, p2) =| p2.x | + | p2.y - p1.y |.

Hãy lấy một ví dụ để làm rõ khái niệm này

Ví dụ

Input:
   {10001}
   {00000}
   {00100}
Output: 6

Giải thích - Ở đây điểm gặp gỡ tốt nhất là (0,2) làm cho quãng đường đi được bằng 6 (2 + 2 + 2).

Bây giờ, chúng ta hãy tạo ra một giải pháp cho vấn đề này. Ở đây, chúng ta phải tìm một điểm giữa từ tất cả các điểm được đánh dấu là 1 trong mảng. chúng ta sẽ làm điều này bằng cách tìm các tâm ngang và dọc (điểm giữa) riêng biệt. và tôi đang tìm khoảng cách của điểm từ tất cả 1 điểm đã đánh dấu.

THUẬT TOÁN

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.

Ví dụ

Hãy tạo một thuật toán dựa trên thuật toán này -

#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;
}

Đầu ra

The minimum distance travelled to meet is 11