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 ' '.
Solution:
class Solution {
public int regionsBySlashes(String[] grid) {
int n = grid.length;
boolean[][] graph = new boolean[n * 3][n * 3];
for(int i = 0; i < 3 * n; i++) {
Arrays.fill(graph[i], true);
}
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++) {
if (grid[i].charAt(j) == '/') {
graph[3 * i][3 * j + 2] = graph[3 * i + 1][3 * j + 1] = graph[3 * i + 2][3 * j] = false;
}
if (grid[i].charAt(j) == '\\') {
graph[3 * i][3 * j] = graph[3 * i + 1][3 * j + 1] = graph[3 * i + 2][3 * j + 2] = false;
}
}
}
int count = 0;
for (int i = 0; i < n * 3; i ++) {
for (int j = 0; j < n * 3; j ++) {
if (graph[i][j]) {
count ++;
dfs(graph, i, j);
}
}
}
return count;
}
private void dfs(boolean[][] graph, int i, int j) {
if (i < 0 || i >= graph.length || j < 0 || j >= graph.length || !graph[i][j]) {
return;
}
graph[i][j] = false;
dfs(graph, i + 1, j);
dfs(graph, i - 1, j);
dfs(graph, i, j + 1);
dfs(graph, i, j - 1);
}
}
