All problems

Hose Network

Medium · minimum spanning tree

A community garden has taps and plots laid out on a flat map. You are given points, where points[i] = [x, y] is the position of item i, and kinds, where kinds[i] is 0 if item i is a tap and 1 if it is a plot.

A hose joins one tap to one plot, never two taps or two plots. Hoses run along the garden paths, so a hose between [x1, y1] and [x2, y2] is |x1 - x2| + |y1 - y2| long, and it costs one per unit of length.

You want everything in one water system: every tap and every plot must be reachable from every other, directly or through other items along hoses. You may lay as many or as few hoses as you like.

Return the smallest total length of hose that does this. If there is only one item, nothing needs to be laid and the answer is 0. If it cannot be done, return -1.

Two items may stand at the same position, and a hose between them has length 0.

Examples

Example 1

Input: points = [[0, 0], [4, 0], [0, 3], [4, 3]], kinds = [0, 1, 1, 0]

Output: 10

Taps are at (0, 0) and (4, 3); plots are at (4, 0) and (0, 3). Lay (0, 0)-(0, 3) = 3, (4, 3)-(4, 0) = 3 and (0, 0)-(4, 0) = 4, which joins all four: 3 + 3 + 4 = 10.

Example 2

Input: points = [[1, 1], [5, 5]], kinds = [0, 0]

Output: -1

Both items are taps, and a hose can only join a tap to a plot.

Example 3

Input: points = [[0, 0], [1, 0], [2, 0]], kinds = [0, 1, 0]

Output: 2

Both taps are one unit from the plot between them: 1 + 1 = 2.

Constraints