959. Regions Cut By Slashes
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' '
.
题目:在由 1 x 1 方格组成的 N x N 网格 grid 中,每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。(请注意,反斜杠字符是转义的,因此 \ 用 “\” 表示。)。返回区域的数目。
思路:参考大神votrubac的解法。将输入的string表达式所代表的网格扩大三倍,如下图(图片源自votrubac,侵删)。其中右下图为扩大后的图,黑色部分表示原始的/
或者\
。对扩大后的图进行dfs得到最终的结果。
class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
int n = grid.size();
vector<vector<int>> g(n*3, vector<int>(n*3));
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(grid[i][j] == '/')
g[i*3][j*3+2] = g[i*3+1][j*3+1] = g[i*3+2][j*3] = 1;
else if(grid[i][j] == '\\')
g[i*3][j*3] = g[i*3+1][j*3+1] = g[i*3+2][j*3+2] = 1;
}
}
int res = 0;
for(int i = 0; i < n*3; ++i){
for(int j = 0; j < n*3; ++j){
if(g[i][j] == 0){
dfs(g, i, j);
res += 1;
}
}
}
return res;
}
private:
void dfs(vector<vector<int>>& g, int i, int j){
if(i < 0 || i >= g.size() || j < 0 || j >= g.size() || g[i][j] == 1)
return;
g[i][j] = 1;
dfs(g, i+1, j);
dfs(g, i-1, j);
dfs(g, i, j+1);
dfs(g, i, j-1);
}
};