C++で最高のミーティングポイント

2人以上のグループがあり、彼らが会って総移動距離を最小化したいとします。値0または1の2Dグリッドがあり、各1はグループ内の誰かの家を示します。距離はマンハッタン距離の式を使用して計算されるため、distance（p1、p2）=| p2.x --p1.x | + | p2.y--p1.y|。

したがって、入力が次のような場合

この場合、マトリックスから出力は6になります。これは、（0,0）、（0,4）、および（2,2）に住む3人の人々が理解できるためです。ポイント（0,2 ）は、2 + 2 + 2 =6の合計移動距離が最小であるため、理想的な待ち合わせ場所です。

これを解決するには、次の手順に従います-

• 関数get（）を定義します。これは配列vを取ります

• 配列を並べ替えるv

• i：=0

• j：=vのサイズ

• ret：=0

• i

  • ret：=ret + v [j]-v [i]

  • （iを1増やします）

  • （jを1つ減らします）

• retを返す

• メインの方法から、次のようにします-

• 配列行を定義する

• 配列列を定義する

• 初期化i：=0の場合、i <グリッドのサイズの場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j <グリッド[0]のサイズの場合、更新（jを1増やします）、実行-

    • grid [i、j]がゼロ以外の場合、-

      • 行の最後にiを挿入します

      • 列の最後にjを挿入します

• get（row）+ get（col）

  を返します

例

理解を深めるために、次の実装を見てみましょう-

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

入力

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

出力

6