#include <algorithm>
#include <iostream>
#include <vector>
// best meeting point = minimal total travel distance
// The total travel distance is the sum of the distances between
// the houses of the friends and the meeting point
// result [0,2] = from [0,0] (2) + form [0,5] (3) + from [2,2] (2) = 2 + 3 + 2 = 7
int minimalTotalTravelDistance(std::vector<std::vector<int>>& grid) {
int friends = 0;
int rows = grid.size();
int cols = grid[0].size();
std::vector<int> x_coordinates;
std::vector<int> y_coordinates;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
x_coordinates.push_back(i);
y_coordinates.push_back(j);
friends++;
}
}
}
sort(x_coordinates.begin(), x_coordinates.end());
sort(y_coordinates.begin(), y_coordinates.end());
int median_x = x_coordinates[friends / 2];
int median_y = y_coordinates[friends / 2];
int distance = 0;
for (int i = 0;i < friends; i++) {
distance += abs(x_coordinates[i] - median_x) + abs(y_coordinates[i] - median_y);
}
return distance;
}
int main()
{
std::vector<std::vector<int>> grid {
{ 1,0,0,0,0,1 },
{ 0,0,0,0,0,0 },
{ 0,0,1,0,0,0 }
};
std::cout << minimalTotalTravelDistance(grid) << std::endl;
}
/*
run:
7
*/
