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
Explanation: The 2x2 grid is as follows:
Example 2:
Input:
[
" /",
" "
]
Output: 1
Explanation: The 2x2 grid is as follows:
Example 3:
Input:
[
"\\/",
"/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:
Example 4:
Input:
[
"/\\",
"\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:
Example 5:
Input:
[
"//",
"/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:
Note:
1 <= grid.length == grid[0].length <= 30
grid[i][j] is either '/', '\', or ' '.
/*
// A grid can be split into 4 small cells as belowed
// \0/
// 3X1
// /2\
*/
// Union-Find Method
int getIdx(int i, int j, int k, int n) {
return (i * n + j) * 4 + k;
}
int find(vector<int>& roots, int i) {
return roots[i] == i ? i : roots[i] = find(roots, roots[i]);
}
void uni(int x, int y, vector<int>& roots, vector<int>& size, int& count) {
x = find(roots, x);
y = find(roots, y);
if (x == y) return;
if (size[x] > size[y]) {
roots[y] = x;
size[x] += size[y];
} else {
roots[x] = y;
size[y] += size[x];
}
--count;
}
int regionsBySlashes(vector<string>& grid) {
int n = grid.size(), count = n * n * 4;
vector<int> roots(count), size(count, 1);
for (int i = 0; i < count; ++i) roots[i] = i;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i > 0) uni(getIdx(i, j, 0, n), getIdx(i - 1, j, 2, n), roots, size, count);
if (j > 0) uni(getIdx(i, j, 3, n), getIdx(i, j - 1, 1, n), roots, size, count);
if (grid[i][j] != '/') {
uni(getIdx(i, j, 0, n), getIdx(i, j, 1, n), roots, size, count);
uni(getIdx(i, j, 2, n), getIdx(i, j, 3, n), roots, size, count);
}
if (grid[i][j] != '\\') {
uni(getIdx(i, j, 0, n), getIdx(i, j, 3, n), roots, size, count);
uni(getIdx(i, j, 1, n), getIdx(i, j, 2, n), roots, size, count);
}
}
}
return count;
}
/*
Upscale the input grid to g[3 * n][3 * n] to draw lines to represent '\\' or '/'
Use DFS to connect each 0 and count the result
*/
// DFS Recursion
void dfs(vector<vector<int> >& g, int i, int j) {
if (i < 0 || i >= g.size() || j < 0 || j >= g[0].size() || g[i][j] != 0) return;
g[i][j] = 1; // mark 0 not to be re-calculated
dfs(g, i + 1, j);
dfs(g, i - 1, j);
dfs(g, i, j + 1);
dfs(g, i, j - 1);
}
int regionsBySlashes(vector<string>& grid) {
int n = grid.size(), res = 0;
vector<vector<int> > g(3 * n, vector<int>(3 * n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '/') g[3 * i][3 * j + 2] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j] = 1;
if (grid[i][j] == '\\') g[3 * i][3 * j] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j + 2] = 1;
}
}
for (int i = 0; i < 3 * n; ++i) {
for (int j = 0; j < 3 * n; ++j) {
if (g[i][j] == 0) {
dfs(g, i, j);
++res;
}
}
}
return res;
}