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() {};
      vector<Point> readAllPoints(vector<vector<int>> *grid);
      vector<Point> readLivePoints(vector<vector<int>>* grid);
      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> ManhattanDistance::readAllPoints(vector<vector<int>> *grid)
  {
      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> ManhattanDistance::readLivePoints(vector<vector<int>> *grid)
  {
      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;
      vector<Point> thePoints = m.readAllPoints(&ManhattanMap);
      vector<Point> theLivePoints = m.readLivePoints(&ManhattanMap);

      //p.printPoints(&thePoints);

      vector<int> distances = m.findDistance(&ManhattanMap, &theLivePoints);

      //m.printDistance(&distances);

      m.findMinimumDistance(&distances);
      int minDistance = m.getMinDistance();
      cout << "The minimum distance is: " << minDistance;
  }