Coding

1584. Min Cost to Connect All Points

2023-09-15 2 min read
#Array#Union Find#Graph#Minimum Spanning Tree
On this page

⭐⭐⭐

題目敘述

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi].

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|, where |val| denotes the absolute value of val.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]] Output: 20 Explanation: We can connect the points as shown above to get the minimum cost of 20. Notice that there is a unique path between every pair of points.

Example 2

Input: points = [[3,12],[-2,5],[-4,1]] Output: 18

解題思路

  • 先將 points[][] 中兩兩點連線，並運算其長度(使用 manhattan distance)，將其存於 W[][] 中。
  • 從第一個節點出發，也就是 W[0] 開始，將其與其他節點的值存於 distance[] 中。
  • 接著就開始使用 MST(Minimum Spanning Trees) 演算法進行尋找最佳路徑。

Solution

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int V = points.length;
        int ans = 0;

        int[] distance = new int[V];
        int[][] W = new int[V][V];

        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (i == j) {
                    W[i][j] = 0;
                } else {
                    W[i][j] = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                }
            }
        }

        for (int i = 0; i < V; i++) {
            distance[i] = W[0][i];
        }
        
        return prim(distance, W, V);
    }

    private int prim(int[] distance, int[][] W, int V) {
        int res = 0;
        int count = 0;

        while (count < V - 1) {
            int min = Integer.MAX_VALUE;
            int vnear = 0;

            for (int i = 0; i < V; i++) {
                if (distance[i] > 0 && distance[i] < min) {
                    min = distance[i];
                    vnear = i;
                }
            }

            distance[vnear] = -1;

            for (int i = 0; i < V; i++) {
                if (W[i][vnear] < distance[i]) {
                    distance[i] = W[i][vnear];
                }
            }

            res += min;
            count++;
        }

        return res;
    }
}
單字

coordinates 座標 n.

one of a pair of numbers and/or letters that show the exact position of a point on a map or graph

  • X and y coordinates are the horizontal and vertical addresses of a point in any 2D space and help identify the exact location of a point.
← Posts
meow~