959. Regions Cut By Slashes

An 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:

1
2
3
4
5
6
7
Input:
[
  " /",
  "/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

ex1

Example 2:

1
2
3
4
5
6
7
Input:
[
  " /",
  "  "
]
Output: 1
Explanation: The 2x2 grid is as follows:

ex2

Example 3:

1
2
3
4
5
6
7
Input:
[
  "\\/",
  "/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)

The 2x2 grid is as follows:

ex3

Example 4:

1
2
3
4
5
6
7
8
Input:
[
  "/\\",
  "\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

ex4

Example 5:

1
2
3
4
5
6
7
Input:
[
  "//",
  "/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

ex5

Note:

1 <= grid.length == grid[0].length <= 30
grid[i][j] is either ‘/’, ‘', or ’ ‘.

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
class Solution {
    public int regionsBySlashes(String[] input) {
        int N = input.length;
        int[][] matrix = new int[3 * N][3 * N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (input[i].charAt(j) == '/') {
                    fillForwardSlash(matrix, i, j);
                } else if (input[i].charAt(j) == ' ') {

                } else {
                    fillBackwardSlash(matrix, i, j);
                }
            }
        }
        int count = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (matrix[i][j] == 0) {
                    count++;
                    fill(matrix, i, j);
                }
            }
        }
        return count;
    }

    int[][] dirs = new int[][] {{1,0}, {0, 1}, {-1, 0}, {0, -1}};

    void fill(int[][] matrix, int i, int j) {
        if (i < 0 || i == matrix.length || j < 0 || j == matrix.length || matrix[i][j] == 1) return;

        matrix[i][j] = 1;

        for(var dir : dirs) {
            fill(matrix, i + dir[0], j + dir[1]);
        }
    }

    void fillForwardSlash(int[][] m, int row, int col) {
        m[3 * row + 2][3 * col] = 1;
        m[3 * row + 1][3 * col + 1] = 1;
        m[3 * row][3 * col + 2] = 1;
    }

    void fillBackwardSlash(int[][] m, int row, int col) {
        m[3 * row][3 * col] = 1;
        m[3 * row + 1][3 * col + 1] = 1;
        m[3 * row + 2][3 * col + 2] = 1;
    }
}

Solution 2022-01-13

 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
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int m = grid[0].length();
        
        int n3 = n * 3;
        int m3 = m * 3;
        
        int[][] G = new int[n3][m3];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                char c = grid[i].charAt(j);
                if (c == '/') {
                    fillForward(i * 3, j * 3, G);         
                } else if (c == '\\') {
                    fillBackward(i * 3, j * 3, G);
                }
            }
        }
                           
        int count = 0;
        for (int i = 0; i < n3; i++) {
            for (int j = 0; j < m3; j++) {
                if (G[i][j] == 0) {
                    dfs(i, j, G);
                    count++;
                }
            }
        }
        return count;
    }
                
    int[][] DIRS = new int[][] {
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    };             
    void dfs(int i, int j, int[][] g) {
       if (i < 0 || i >= g.length || j < 0 || j >= g[0].length) {
           return;
       }
        
       if (g[i][j] == 1) {
           return;
       } 
        
       g[i][j] = 1;
        
        for (int[] dir: DIRS) {
            dfs(i + dir[0], j + dir[1], g);
        }
    }
                           
    void fillForward(int i, int j, int[][] g) {

        
        g[i][j + 2] = 1;
        g[i + 1][j + 1] = 1;
        g[i + 2][j] = 1;
    }
                           
    void fillBackward(int i, int j, int[][] g) {
        g[i][j] = 1;
        g[i + 1][j + 1] = 1;
        g[i + 2][j + 2] = 1;
    }
}

Solution 2023-02-18 - UnionFind

  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
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid[0].length();
        int[][] array = new int[3 * n][3 * n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                char c = grid[i].charAt(j);

                if (c == '/') {
                    fillForward(array, 3*i, 3*j);
                } else if (c == '\\') {
                    fillBackward(array, 3*i, 3*j);
                }
            }
        }

        // print(array);

        UF uf = new UF(9 * n * n);

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                  
                  if (array[i][j] == 0) {
                    // right
                    if (j < array.length - 1 && array[i][j + 1] == 0) {
                        uf.union(array.length * i + j, array.length * i + j + 1);
                    }
                    // down
                    if (i < array.length - 1 && array[i+1][j] == 0) {
                        uf.union(array.length * i + j, array.length * (i+1) + j);
                    }
                  }       
            }
        }

        Set<Integer> provinces = new HashSet<>();

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length; j++) {
                int index = array.length * i + j;
                int pid = uf.parent(index);
                if (index != uf.parent(index)) {
                    provinces.add(pid);
                }
            }
        }

        return provinces.size();
    }


    class UF {
        int[] a;
        int[] sizes;

        UF(int n) {
            this.a = new int[n];
            this.sizes = new int[n];
            for (int i = 0; i < a.length; i++) {
                a[i] = i;
            }
        }

        void union(int p, int q) {

            int pid = parent(p);
            int qid = parent(q);

            if (pid == qid) return;

            if (sizes[pid] < sizes[qid]) {
                a[qid] = a[pid];
            } else {
                a[pid] = a[qid];    
            }
        }

        int parent(int p) {
            while (a[p] != p) {
                p = a[p];
            }
            return p;
        }
    }

    void print(int[][] a) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.printf("%d ", a[i][j]);
            }
            System.out.println();
        } 
    }

    void fillForward(int[][] a, int i, int j) {
        a[i][j] = 0;
        a[i][j+1] = 0;
        a[i][j+2] = 1;

        a[i+1][j] = 0;
        a[i+1][j+1] = 1;
        a[i+1][j+2] = 0;

        a[i+2][j] = 1;
        a[i+2][j+1] = 0;
        a[i+2][j+2] = 0;
 
    }

     void fillBackward(int[][] a, int i, int j) {
        a[i][j] = 1;
        a[i][j+1] = 0;
        a[i][j+2] = 0;

        a[i+1][j] = 0;
        a[i+1][j+1] = 1;
        a[i+1][j+2] = 0;

        a[i+2][j] = 0;
        a[i+2][j+1] = 0;
        a[i+2][j+2] = 1;
 
    }
}

Solution 2022-01-13#

Solution 2023-02-18 - UnionFind#

Solution 2022-01-13

Solution 2023-02-18 - UnionFind