959. Regions Cut By Slashes

Description

image-20210819223453843

image-20210819223506022

image-20210819223642291

image-20210819223649217

Solution

Two solutions both work:

  • DFS, like find connected components in a island-sea question, but we need to deal with the slashes because we can not DFS a half-block. So we can zoom up the grid into 3 * 3 array then map the slash into it.
  • Use union-find to union the plots and edges.
    • First, each plot are in its own set, four edges are in one set
    • We note that once slash connect two points from the same set, we can get 1 new region. Once points are from different set, we just union them.

Code

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
class Solution {
    vector<int> dir = {-1, 0 , 1, 0 , -1};
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        vector<vector<int>> ngrid(3*n, vector<int>(3*n));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < grid.size(); j++){
                if(grid[i][j] == '/'){
                    ngrid[3 * i][3 * j + 2] = 1;
                    ngrid[3 * i + 1][3 * j + 1] = 1;
                    ngrid[3 * i + 2][3 * j ] = 1;
                }else if(grid[i][j] == '\\'){
                    ngrid[3 * i][3 * j] = 1;
                    ngrid[3 * i + 1][3 * j + 1] = 1;
                    ngrid[3 * i + 2][3 * j + 2] = 1;
                }
            }
        }
        int res = 0;
        for(int i = 0; i < ngrid.size(); i++){
            for(int j = 0; j < ngrid.size(); j++){
                if(!ngrid[i][j]){
                    dfs(ngrid,i,j);
                    res++;
                }
            }
        }
        return res;
    }

    void dfs(vector<vector<int>>& grid, int r, int c){
        if(grid[r][c])
            return;
        grid[r][c] = 1;
        for(int i = 0; i < 4;i++){
            int x = dir[i] + r, y = dir[i+1] + c;
            if(x < 0 || x >= grid.size() || y < 0 || y >= grid.size() || grid[x][y])
                continue;
            dfs(grid,x,y);
        }
    }
};
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
class Solution:
    father = list()
    def regionsBySlashes(self, grid: List[str]) -> int:
        size = len(grid)
        father = {(i,j) : (i,j) for j in range(size+1) for i in range(size+1)}
        for i in range(size+1):
            father[i,0], father[0,i], father[size,i], father[i,size] = (0,0), (0,0), (0,0), (0,0)
        
        def find(c):
            while father[c] != c:
                c = father[c]
            return c
        def union(a,b):
            father[a] = find(b)
        
        res = 1
        for i in range(size):
            for j in range(size):
                if grid[i][j] == ' ':
                    continue
                t1, t2 = list(), list()
                if grid[i][j] == '/':
                    t1 = find((i+1, j))
                    t2 = find((i, j + 1))

                elif grid[i][j] == '\\':
                    t1 = find((i, j))
                    t2 = find((i+1, j + 1))
                
                if t1 == t2:
                    res += 1
                else:
                    union(t1,t2)
        return res