# 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. `1 <= grid.length == grid[0].length <= 30`
2. `grid[i][j]` is either `'/'``'\'`, or `' '`.

``````class Solution {
public:
int regionsBySlashes(vector<string>& grid) {
int n = grid.size(), res = 0;
vector<vector<int>> nums(3 * n, vector<int>(3 * n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == '/') {
nums[i * 3][j * 3 + 2] = 1;
nums[i * 3 + 1][j * 3 + 1] = 1;
nums[i * 3 + 2][j * 3] = 1;
} else if (grid[i][j] == '\\') {
nums[i * 3][j * 3] = 1;
nums[i * 3 + 1][j * 3 + 1] = 1;
nums[i * 3 + 2][j * 3 + 2] = 1;
}
}
}
for (int i = 0; i < nums.size(); ++i) {
for (int j = 0; j < nums.size(); ++j) {
if (nums[i][j] == 0) {
helper(nums, i, j);
++res;
}
}
}
return res;
}
void helper(vector<vector<int>>& nums, int i, int j) {
if (i >= 0 && j >= 0 && i < nums.size() && j < nums.size() && nums[i][j] == 0) {
nums[i][j] = 1;
helper(nums, i - 1, j);
helper(nums, i, j + 1);
helper(nums, i + 1, j);
helper(nums, i, j - 1);
}
}
};
``````

Number of Islands

Github 同步地址:

https://github.com/grandyang/leetcode/issues/959

https://leetcode.com/problems/regions-cut-by-slashes/

https://leetcode.com/problems/regions-cut-by-slashes/discuss/205674/C%2B%2B-with-picture-DFS-on-upscaled-grid

https://leetcode.com/problems/regions-cut-by-slashes/discuss/205680/JavaC%2B%2BPython-Split-4-parts-and-Union-Find

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation