1628.Driving problem

There is a road with a lengthLand a widthW. There are some circular obstacles in the road. The radius is 1, there is a circular car with a radius of 2. Ask if the car can pass this road. You can think of the road as a rectangle on two-dimensional coordinates. The four points are(0,0), (0,W), (L,0), (L,W). Now you need to start fromx=0Tox=L, contact with obstacles is not allowed, and all parts of the car are betweeny=0andy=W, contact is not allowed.

Example

GivenL=8,W=8, the obstacle coordinates are[[1,1],[6,6]]. Returnyes.

The center of the car can go from (0,5) to (2,5) to (5,2) to (8,2), so return yes.

你是怎麼想到的？

。題目假設

1. The radius of each obstacle is 1.
2. The radius of the car is 2.
3. The car cannot go across the road.
4. No contact is allowed between the car and any obstacle.

。重要問題

車子和障礙物不能有任何接觸，而且座標可以是 float

而且路徑不一定是要一點一點的，只要滿足車子不碰到障礙物即可

。直覺

直覺是要先確定各個障礙物的座標，然後從 x = 0 開始走

。解決方法可行性

如果用矩陣那會太複雜，用座標也是，而且還可以是 float 型態，是要判斷到什麼時候？

於是就直接看答案了，原來是要用 union find，用了 union find 會瞬間簡單很多，剛好也藉此學習了"並查集"

。解決方案

我們可以想到，如果車子可以通過兩個障礙物，表示圓心之間的距離是夠大的

所以我們將兩個障礙物計算圓心距離，如果不夠大，歸為同一組，然後每個障礙物也看一下是不是自己的上方也無法通過，如果無法通過就將這個障礙物與某一個數(這邊叫做n)聯集，下方無法通過則是跟 n+1 聯集

最後，我們從並查集裡去找 n 和 n+1 是不是在同一集合裡，如果在同一集合，

表示某個上方無法通過的障礙物和下方無法通過的障礙物在集合裡，又剛剛在這集合裡的都是兩兩無法讓車子通過的，所以 n 和 n+1 在同一集合裡表示車子過不去

。資料結構

UnionFind

。複雜度

掃描兩兩的關係，所以是 O(n^2)

class UnionFind {
    int[] father;

    //這邊 father的 index 表示元素，father[i]表示這個元素的 father
    UnionFind(int n) {
        father = new int[n];
        for (int i=0; i<n; i++) {
            father[i] = i;
        }
    }

    int find_and_compress(int x) {
        int parent = x;
        //找出自己是自己的parent的那個點，就是x的parent
        while (parent != father[parent]) {
            parent = father[parent];
        }

        //compress path，把剛剛路徑上的點的 parent 更新
        int temp;
        while (x != father[x]) {
            temp = father[x];
            father[x] = parent;
            x = temp;
        }
        return parent;
    }

    private static final String YES = "yes";
    private static final String NO = "no";
    public String drivingProblem(int L, int W, double[][] p) {
        int n = p.length;
        //+2 because we use n and n+1 as an element
        UnionFind uf = new UnionFind(n+2);
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
                double dx = (p[i][0] - p[j][0])*(p[i][0] - p[j][0]);
                double dy = (p[i][1] - p[j][1])*(p[i][1] - p[j][1]);
                //because the coordinate is float type, for convenience, 
                //we don't calculate sqrt
                //36d because the minimal distance for a car to pass is 6d
                if (dx + dy <= 36d) {
                    uf.union(i, j);
                }
            }
            //表示這個點的y座標＋半徑會碰到車子->上方沒有路
            if (p[i][1]+1 >= W-4)
                uf.union(i, n);

            //表示這個點的y座標＋半徑會碰到車子->下方沒有路
            if (p[i][1]-1 <= 4)
                uf.union(i, n+1);
        }
        if (uf.find_and_compress(n) == uf.find_and_compress(n+1))
            return NO;
        return YES;
    }
}