Friday, March 15, 2019

Lintcode 434. Number of Islands II

Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.

Example

Example 1:
Input: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
Output: [1,1,2,2]
Explanation:
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011
Example 2:
Input: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]
Output: [1,1,2,2]

Notice

0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Code (Java):
?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class Solution {
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int numCC = 0;
 
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> ans = new ArrayList<>();
         
        if (operators == null || operators.length == 0) {
            return ans;
        }
 
        int[] parents = new int[n * m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                parents[i * m + j] = i * m + j;
            }
        }
 
        Set<Integer> islands = new HashSet<>();
 
        for (Point point : operators) {
            if (!islands.contains(point.x * m + point.y)) {
                islands.add(point.x * m + point.y);
                numCC++;
                for (int i = 0; i < 4; i++) {
                    connect(point.x, point.y, point.x + dirs[i][0], point.y + dirs[i][1], n, m, islands, parents);
                }
            }
            ans.add(numCC);
        }
        return ans;
    }
 
    private void connect(int ax, int ay, int bx, int by, int n, int m, Set<Integer>islands, int[] parents) {
        if (bx < 0 || bx >= n || by < 0 || by >= m) {
            return;
        }
 
        if (!islands.contains(bx * m + by)) {
            return;
        }
 
        int rootA = find(ax, ay, n, m, parents);
        int rootB = find(bx, by, n, m, parents);
 
        if (rootA != rootB) {
            parents[rootB] = rootA;
            numCC--;
        }
    }
 
    private int find(int x, int y, int n, int m, int[] parents) {
        int p = x * m + y;
        int root = p;
 
        while (root != parents[root]) {
            root = parents[root];
        }
 
        // path compression
        //
        while (root != p) {
            int temp = parents[p];
            parents[p] = root;
            p = temp;
        }
 
        return root;
    }
}

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
 
public class Solution {
    /**
     * @param n: An integer
     * @param m: An integer
     * @param operators: an array of point
     * @return: an integer array
     */
    private int[] parents;
    private int numIslands = 0;
     
    private int find(int x) {
        int root = x;
        while (parents[root] != root) {
            root = parents[root];
        }
         
        // path compression
        while (root != x) {
            int temp = parents[x];
            parents[x] = root;
            x = temp;
        }
         
        return x;
    }
     
    private void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
         
        if (parents[parentX] != parentY) {
            parents[parentX] = parentY;
            numIslands--;
        }
    }
      
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (n <= 0 || m <= 0 || operators == null || operators.length == 0) {
            return ans;
        }
         
        parents = new int[n * m];
         
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                parents[i * m + j] = i * m + j;
            }
        }
         
        int[][] islands = new int[n][m];
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
         
        for (Point opeartor : operators) {
            int x = opeartor.x;
            int y = opeartor.y;
             
            if (islands[x][y] == 1) {
                ans.add(numIslands);
                continue;
            }
             
            numIslands += 1;
            islands[x][y] = 1;
             
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                 
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && islands[nx][ny] == 1) {
                    union(x * m + y, nx * m + ny);
                }
            }
             
            ans.add(numIslands);
        }
         
        return ans;
    }
}
Posted by at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)