LeetCode Q296: Best Meeting Point (hard)

 A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

For example, given three people living at (0,0), (0,4), and (2,2):

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

The point (0,2) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.

Solution:

	class Solution {
	public:
	int minTotalDistance(vector<vector<int>>& grid) {
	if(grid.size()==0)
	return 0;
	int rows = grid.size();
	int cols = grid[0].size();
	vector<int> X(cols);
	vector<int> Y(rows);
	for(int i=0; i<rows; i++){
	for(int j=0; j<cols; j++){
	if(grid[i][j]==0)
	continue;
	int x = j;
	int y= i;
	for(int k=0; k<cols; k++)
	X[k]=X[k]+abs(x--);
	for(int k=0; k<rows; k++)
	Y[k]=Y[k]+abs(y--);
	}
	}
	int minv = INT_MAX;
	for(int i=0; i<rows; i++)
	for(int j=0; j<cols; j++)
	minv = min(minv, X[j]+Y[i]);
	return minv;
	}
	};

view raw Q296.cpp hosted with ❤ by GitHub