Show problems as
Classic problem #296HardArrayMathSortingMatrix

Best Meeting Point

Real-world version: Where to Set the Muster Point
Tracked in this browser only
Read Best Meeting Point on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A yard is given as the grid grid, where 1 marks a cell holding a worker and 0 marks an empty cell.

A worker walks one cell at a time to a cell sharing an edge with the current one, so walking between two cells costs the rows between them plus the columns between them.

Choose one cell as the muster point and add up how far every worker walks to reach it. Return the smallest total any choice of cell gives. The muster point may be any cell of the yard, whether a worker stands on it or not.

Examples

Example 1

Input
grid = [[1, 0, 0], [0, 0, 0], [0, 0, 1]]
Output
4

The two workers stand in opposite corners. Every cell lying on a shortest walk between them costs the same, so the centre serves as well as either corner, and the total is the four steps that separate the two workers.

Example 2

Input
grid = [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
Output
8

Four workers at the corners of the yard. The two rows apart pair up for two steps, and so do the two columns, twice over, so any cell inside the square they mark costs eight steps altogether.

Example 3

Input
grid = [[1, 1, 1]]
Output
2

All three workers share a row, so only columns matter. Mustering on the middle worker's cell costs one step from each side and nothing from the middle.

Constraints

  • 1 <= grid.length <= 200
  • 1 <= grid[i].length <= 200
  • 0 <= grid[i][j] <= 1
  • At least two cells hold a worker.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_total_distance(grid: list[list[int]]) -> int:
Java
public int minTotalDistance(int[][] grid)

More on the same topics