Last Updated: 16 Apr, 2021
Best Meeting Point
Easy
Asked in companies
Ninja, along with his family, moved to a new city, and Ninja has no friends. He started making new friends from his school. Now he has a number of friends. His friends decided to meet in the evening, but all are confused about where to meet?
Ninja is very busy doing some other works. Can you help Ninja find a place where Ninja and all his friends can meet such that the sum of distance traveled by Ninja and his friends is the minimum possible? Find the place and print the total sum of distances traveled by Ninja and his friends.
You are given the location of Ninja and his friends in the form of a matrix. In the matrix, wherever the value is 1, it means that there is a home at that point (Ninja’s home or the home of some of his friends). Ninja and his friends can meet at any possible coordinate in the matrix, not necessarily at the home of any of the friends.
Manhattan distance is used to calculate the distance between two points, i.e, distance(a, b) = |a.x - b.x| + |a.y - b.y|, (where a.x is the x coordinate of point ‘a’, a.y is the y coordinate of point ‘a’, b.x is the x coordinate of point ‘b’, b.y is the y coordinate of point ‘b’ respectively).
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line contains two space-separated integers, ‘N’ and ‘M’, which denotes the number of rows and columns in the matrix ‘MAT’.
Each of the next ‘N’ lines contains ‘M’ space-separated integers denoting the 'N' tows of the matrix 'MAT'
Output Format:
For each test case, print a single line containing a single integer denoting the minimum total distance traveled by you and your friends.
The output of each test case will be printed in a separate line.
Note:
You are not required to print the expected output, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= N <= 500
1 <= M <= 500
0 <= MAT[i][j] <= 1
Where 'T' is the number of test cases, N, M denotes the number of rows and columns in the matrix ‘MAT’, and MAT[i][j] denotes the element present at the i'th row and the j'th column of the matrix 'MAT'.
Time Limit: 1 sec.
Approaches
The idea is to iterate over all the points and find what is the total distance traveled by all the friends if the current point is being chosen as a meeting point and select the point which gives the minimum possible distance as the meeting point.
The steps are as follows:
- Initialize an integer minDistanceTravelled to 0, which stores the minimum distance traveled from the home of all the friends to the meeting point.
- Iterate from a = 0 to N-1:
- Iterate from b = 0 to M-1:
- Initialize currentDistance to 0, which stores the distance traveled by Ninjas and all his friends when (a, b) is chosen as the meeting point.
- Iterate from i = 0 to N-1:
- Iterate from j = 0 to M - 1:
- If the current element, i.e., MAT[i][j] is equal to 1, then add the distance from the meeting point to the current point in currentDistance, i.e., abs(a-i) + abs(b-j).
- Iterate from j = 0 to M - 1:
- Update minDistanceTravelled to the minimum of minDistanceTravelled and currentDistance.
- Iterate from b = 0 to M-1:
- Return minDistanceTravelled as the final answer.
The idea is to store both x coordinates and y coordinates separately in an array and then find the midpoint from them, and this will be the point in which the total distance traveled will be minimum. As we are using Manhattan distance to calculate the distance between the two points and Manhattan distance, we can treat x and y coordinates separately. If we find the middle of all the x coordinates, it will be similar to the mean of all x coordinates, i.e., all the friends will have to go to the middle point which will minimize the sum of distances traveled. Similar is the case with y coordinate.
The steps are as follows:
- Declare two arrays xCoordinates, yCoordinates, which stores the x and y coordinates of the homes of all the friends.
- Iterate from i = 0 to N-1:
- Iterate from j = 0 to M-1:
- If there is a friend at that point, ie. MAT[i][j] = 1, push the x coordinate of the point ie i to the array xCoordinates.
- Iterate from j = 0 to M-1:
- From this iteration, we will get the x coordinates of the points in sorted order. We will do another iteration to find the y coordinates in sorted order. The idea behind this step is if we push the y coordinates in this loop only, then we would have to sort the array yCoordinates, which will take O(N*M*log(N*M)) time in the worst case and using another iteration will take O(N*M) time only.
- Iterate from j = 0 to M-1:
- Iterate from i = 0 to N-1:
- If there is a friend at that point, ie. MAT[i][j] = 1, push the y coordinate of the point ie j to the array yCoordinates.
- Iterate from i = 0 to N-1:
- Initialize an integer totalPoints as the number of elements in the array xCoordinates or yCoordinates (as the size of both the arrays will be equal).
- Find the x and y coordinates of the point which is optimal for meeting, i.e., is x and y coordinates of the middle point, and store the x coordinate in a variable middlePointX, and the y coordinate in a varaible middlePointY.
- As we have found the middle point, we need to calculate the total distance traveled by all the friends.
- Initialize an integer minDistanceTravelled to 0, which stores the distance traveled from the home of all the friends to the meeting point.
- Iterate from i = 0 to N-1:
- Iterate from j = 0 to M-1:
- If there is a friend at that point, ie. MAT[i][j] = 1, add the distance of that point to minDistanceTravelled, ie. absolute difference between x and y coordinates.
- Iterate from j = 0 to M-1:
- Return minDistanceTravelled as the final answer.