Đ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, cho một mảng nhị phân 2D, tức là các giá trị là 0 hoặc 1, nơi 1 đánh dấu nhà của một người trong nhóm. Và mọi người trong nhóm muốn gặp nhau. Vì vậy, họ cần tối thiểu hóa tổng khoảng cách di chuyển để gặp tại một điểm chung. Điểm gặp hợp lệ có thể ở bất cứ đâu nhưng không ở nhà của ai.

Để tìm khoảng cách tối thiểu, một công thức được tạo ra, gọi là khoảng cách Manhattan, nơi khoảng cách:

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

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

Ví dụ

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

Giải thích − Điểm gặp tốt nhất là (0,2) làm khoảng cách di chuyển bằng 6 (2+2+2).

Bây giờ, hãy tạo giải pháp cho bài toán này. Ở đây, phải tìm điểm trung gian từ tất cả các điểm được đánh dấu 1 trong mảng. Ta sẽ làm bằng cách tìm trung tâm ngang và dọc (điểm giữa) riêng biệt. Và tìm khoảng cách của điểm đó đến tất cả các điểm đánh dấu 1.

THUẬT TOÁN

Bước 1: Tạo hai cấu trúc với giá trị vị trí ngang và dọc của các điểm đánh dấu 1.
Bước 2: Trong cả hai cấu trúc này, tìm vị trí giữa và coi (midx, midy) là điểm gặp.
Bước 3: Tính khoảng cách của mỗi điểm đến giữa.
Bước 4: Trả về tổng tất cả khoảng cách.

Ví dụ

Hãy tạo 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<<"Khoảng cách tối thiểu để gặp nhau là "<<minMeetingDistance(distance);
    return 0;
}

Kết quả

Khoảng cách tối thiểu để gặp nhau là 11