710. Determining the Optimal Meeting Point for a Get-Together Party

0

Hard

Once upon a time, a group of friends decided to organize a get-together party. They all lived in a binary grid of size m x n, where each "1" represented the home of a friend.

In order to have the party, they needed to choose a meeting point that would minimize the total travel distance. The total travel distance was calculated as the sum of distances between each friend's house and the meeting point. The distance was calculated using the Manhattan Distance formula, which calculates the distance between two points (p1 and p2) as the sum of the absolute differences of their x and y coordinates, i.e.

distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|

The friends decided to use an algorithm to find the optimal meeting point. The algorithm would identify all possible meeting points in the grid and calculate the total travel distance for each meeting point. Then, it would select the meeting point with the minimum total travel distance as the optimal meeting point for the party.

The friends were eager to use the algorithm to find the best meeting point and have a fantastic party together.

Since they are busy preparing for the party, can you assist them in creating the necessary algorithm?

Input Format

The first line contains two integers, m and n, representing the number of rows and columns in the grid, respectively.
The next m lines contain n integers representing the elements of the matrix.

Output Format

Print an integer representing the total travel distance.

Example

Input

3 5 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0

Output

6

Constraints

  • m must be equal to the number of rows in the grid
  • n must be equal to the number of columns in the grid
  • 1 <= m, n <= 200
  • Each element in the grid must be either 0 or 1.
  • There must be at least two friends in the grid.
Loading...

View Submissions

Console