Điểm gặp gỡ tốt nhất trong C ++

Giả sử có một nhóm từ hai người trở lên và họ muốn gặp nhau và giảm thiểu tổng quãng đường di chuyển. Chúng tôi có một lưới 2D gồm các giá trị 0 hoặc 1, trong đó mỗi giá trị 1 đánh dấu nhà của một người nào đó trong nhóm. Khoảng cách được tính bằng công thức Khoảng cách Manhattan, vì vậy khoảng cách (p1, p2) =| p2.x - p1.x | + | p2.y - p1.y |.

Vì vậy, nếu đầu vào giống như

1	0	1
0	0	0
0	1	0

thì đầu ra sẽ là 6 vì từ ma trận, chúng ta có thể hiểu rằng ba người sống ở (0,0), (0,4) và (2,2):Điểm (0,2 ) là một điểm gặp gỡ lý tưởng, vì tổng quãng đường di chuyển là 2 + 2 + 2 =6 là tối thiểu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm get (), điều này sẽ lấy một mảng v,
sắp xếp mảng v
i:=0
j:=kích thước của v
ret:=0
trong khi tôi
- ret:=ret + v [j] - v [i]
- (tăng i lên 1)
- (giảm j đi 1)
trả lại ret
Từ phương thức chính, hãy làm như sau -
Xác định một hàng mảng
Xác định cột mảng
để khởi tạo i:=0, khi i
- để khởi tạo j:=0, khi j
  - nếu lưới [i, j] khác 0, thì -
    - chèn tôi vào cuối hàng
    - chèn j vào cuối col
trả về get (row) + get (col)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minTotalDistance(vector<vector<int>>& grid) {
      vector<int> row;
      vector<int> col;
      for (int i = 0; i < grid.size(); i++) {
         for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j]) {
               row.push_back(i);
               col.push_back(j);
            }
         }
      }
      return get(row) + get(col);
   }
   int get(vector <int> v){
      sort(v.begin(), v.end());
      int i = 0;
      int j = v.size() - 1;
      int ret = 0;
      while (i < j) {
         ret += v[j] - v[i];
         i++;
         j--;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}};
   cout << (ob.minTotalDistance(v));
}

Đầu vào

{{1,0,0,0,1},{0,0,0,0,0},{0,0,1,0,0}}

Đầu ra