leetcode-solutions/solutions/0501-1000/0959-regions-cut-by-slashes.cpp at main · Avuvos/leetcode-solutions · GitHub

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

        int ans = 0;
        for (int i = 0; i < 3 * n; i++) {
            for (int j = 0; j < 3 * n; j++) {
                if (a[i][j] == 1) {
                    ans++;
                    dfs(dfs, i, j);
                }
            }
        }
        return ans;
    }
};