1
/*
2
Convert grid to 3*n X 3*n grid where eacah of the cell is upscalled to 3x3 grid
3
and then map the diagonal to 0 or 1 depending on '/' or '\' type in the grid.
4

5
Example:
6
["/\\","\\/"] this can be converted to following scaled grid:
7

8
1 1 0 0 1 1
9
1 0 1 1 0 1
10
0 1 1 1 1 0
11
0 1 1 1 1 0
12
1 0 1 1 0 1
13
1 1 0 0 1 1
14

15
Once this conversion is done, then its simple island count problem, run dfs from
16
each cell to visit all cells and count number of times dfs is started and return
17
it as answer.
18
*/
19

20
class Solution {
21
 public:
22
  int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
23
  void dfs(vector<vector<int>> &g, vector<vector<int>> &vis, int i, int j) {
24
    for (int d = 0; d < 4; ++d) {
25
      int x = i + dir[d][0];
26
      int y = j + dir[d][1];
27
      if (x >= 0 && y >= 0 && x < g.size() && y < g.size() && vis[x][y] == -1 && g[x][y] == 1) {
28
        vis[x][y] = 1;
29
        dfs(g, vis, x, y);
30
      }
31
    }
32
  }
33
  int regionsBySlashes(vector<string> &grid) {
34
    int n = grid.size();
35
    vector<vector<int>> g(3 * n, vector<int>(3 * n, 1));
36
    for (int i = 0; i < n; ++i) {
37
      for (int j = 0; j < n; ++j) {
38
        if (grid[i][j] == '\\') {
39
          for (int k = 0; k < 3; ++k) g[3 * i + k][3 * j + k] = 0;
40
        } else if (grid[i][j] == '/') {
41
          for (int k = 0; k < 3; ++k) g[3 * i + k][3 * j + 2 - k] = 0;
42
        }
43
      }
44
    }
45
    int count = 0;
46
    vector<vector<int>> vis(3 * n, vector<int>(3 * n, -1));
47

48
    for (int i = 0; i < 3 * n; ++i) {
49
      for (int j = 0; j < 3 * n; ++j) {
50
        if (vis[i][j] == -1 && g[i][j] == 1) { // cout<<i<<" "<<j<<endl;
51
          count++;
52
          vis[i][j] = 1;
53
          dfs(g, vis, i, j);
54
        }
55
      }
56
    }
57

58
    return count;
59
  }
60
};