Minimal Tree Distance

You are given a rectangular grid of size \(H\) rows and \(W\) columns. Each cell in the grid either contains a tree (represented by 1) or is empty (represented by 0). Your task is to choose one cell to build a house such that the total Manhattan distance from this house to all the trees is minimized.

The Manhattan distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is given by:

[ |x_1 - x_2| + |y_1 - y_2| ]

If the grid does not contain any trees, the answer is defined to be 0. You need to determine the minimal sum of Manhattan distances from the chosen cell (where the house is built) to all the cells that contain trees.

Note: The grid is provided as \(H\) lines of \(W\) space-separated integers. The first two integers in the input denote \(W\) and \(H\), respectively.

inputFormat

The first line contains two integers: \(W\) and \(H\), which indicate the number of columns and rows in the grid, respectively. Following this, there are \(H\) lines, each containing \(W\) space-separated integers. Each integer is either 0 (empty cell) or 1 (cell with a tree).

outputFormat

Print a single integer representing the minimal sum of Manhattan distances from the house (which can be built at any cell) to all the trees in the grid.

3 3
1 0 0
0 1 0
0 0 1

4