dustfree's blog
0%

Regions Cut By Slashes

Posted on In ,

Question

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, , or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as “\“.)

Return the number of regions.
Example 1:

Input:
[“ /“,”/ “]
Output: 2

Solution

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
/*
@param: String[] grid
@return int
Algorithm: 将正方形分成4个三角形，上下左右分别为 1，3，0，2，然后union。
    1
0   2
    3
*/
int count, l;      
int[] f;
public int regionsBySlashes(String[] grid) {
    l = grid.length;
    if (l == 0 || grid[0].length() == 0) return 0;
    
    f = new int[l*l*4];
    count = l*l*4;
    
    for (int i = 0; i < l*l*4; i++) {
        f[i] = i;
    }
    
    for (int i = 0; i < l; i++) {
        for (int j = 0; j < l; j++) {
            if (i > 0) union(index(i-1,j,3), index(i,j,1));
            if (j > 0) union(index(i,j-1,2), index(i,j,0));
            
            if (grid[i].charAt(j) != '\\') {
                union(index(i,j,0), index(i,j,1));
                union(index(i,j,2), index(i,j,3));
            }
            if (grid[i].charAt(j) != '/') {
                union(index(i,j,0), index(i,j,3));
                union(index(i,j,1), index(i,j,2));                    
            }
        }
    }
    return count;
}
public int find(int x) {
    if (x != f[x]) {
        f[x] = find(f[x]);
    }
    return f[x];
}
public void union(int x, int y) {
    x = find(x); y = find(y);
    if (x != y) {
        f[x] = y;
        count--;
    }
}

public int index(int i, int j, int k) {
    return (i*l+j)*4 + k;
}