# 296 Best Meeting Point

Note: I wrote more than necessary for this assignment. I wanted to review some concepts.
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), (4,0), and(2,2):
1 - 0 - 0 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
The point (2,0) is an ideal meeting point, as the total travel distance of 2+2+2=6 is minimal. So return 6.
#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;
class Point
{
public:
Point(int px, int py, bool housed) {
x = px;
y = py;
isHoused = housed;
}
Point(int px, int py) {
x = px;
y = py;
}
Point() {};
void printAllPoints(vector<Point> *myPoints);
int x;
int y;
private:
bool isHoused;
};
void Point::printAllPoints(vector<Point> *myPoints)
{
for (int i = 0; i < (*myPoints).size(); i++)
{
cout << "x-cord: " << (*myPoints).at(i).x << endl;
cout << "y-cord: " << (*myPoints).at(i).y << endl;
cout << "Has live cell: " << boolalpha << (*myPoints).at(i).isHoused << endl << endl;
}
}
class ManhattanDistance
{
public:
ManhattanDistance() {};
void printDistance(vector<int> *distances);
vector<int> findDistance(vector<vector<int>> *grid, vector<Point> *myPoints);
int getMinDistance() { return minDistance; }
void findMinimumDistance(vector<int> *distances);
private:
int minDistance;
};
{
vector<Point> myPoints;
Point *x;
int rows = (*grid).size();
int cols = (*grid).at(0).size();
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if ((*grid).at(i).at(j) == 1)
myPoints.emplace_back(j, i, true);
else myPoints.emplace_back(j, i, false);
}
}
return myPoints;
}
{
vector<Point> myPoints;
Point *x;
int rows = (*grid).size();
int cols = (*grid).at(0).size();
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
if ((*grid).at(i).at(j) == 1)
myPoints.emplace_back(j, i);
}
}
return myPoints;
}
vector<int> ManhattanDistance::findDistance(vector<vector<int>>* grid, vector<Point>* myPoints)
{
vector<int> distances;
int rows = (*grid).size();
int cols = (*grid).at(0).size();
long int distanceSum = 0;
int currentX;
int currentY;
// method: starting for distance (0,0), we calculate the sum of the distances every live point to every other point.
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < cols; j++)
{
for (int k = 0; k < (*myPoints).size(); k++)
{
currentX = (*myPoints).at(k).x;
currentY = (*myPoints).at(k).y;
// distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|
distanceSum += abs(currentX - i) + abs(currentY - j);
}
distances.push_back(distanceSum);
distanceSum = 0;
}
}
return distances;
}
void ManhattanDistance::findMinimumDistance(vector<int>* distances)
{
int minElement = *min_element((*distances).begin(), (*distances).end());
minDistance = minElement;
}
void ManhattanDistance::printDistance(vector<int>* distances)
{
cout << "Printing distances: " << endl;
for (auto i : (*distances))
cout << i << endl;
cout << endl;
}
/* method:
* 1) Read matrix and store cordinates
* 2) Calculate the minimum distance from each live point to every other cell, and calculate their sum.
* 3) Find the minimum sum, and return this as the result
*/
int main()
{
/*
1 - 0 - 0 - 0 - 1
| | | | |
0 - 0 - 0 - 0 - 0
| | | | |
0 - 0 - 1 - 0 - 0
*/
vector<vector<int>> ManhattanMap = { {1,0,0,0,1},
{0,0,0,0,0},
{1,0,0,0,1},
{ 1,0,0,0,1 },
{ 1,0,0,0,1 },
{ 1,0,0,0,1 },
{ 1,0,0,0,1 },
};
Point p;
ManhattanDistance m;