Regions Cut By Slashes Problem
Description
LeetCode Problem 959.
An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a ‘/’, ‘', or blank space ‘ ‘. These characters divide the square into contiguous regions.
Given the grid grid represented as a string array, return the number of regions.
Note that backslash characters are escaped, so a ‘' is represented as ‘\’.
Example 1:
1
2
Input: grid = [" /","/ "]
Output: 2
Example 2:
1
2
Input: grid = [" /"," "]
Output: 1
Example 3:
1
2
3
Input: grid = ["\\/","/\\"]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
Example 4:
1
2
3
Input: grid = ["/\\","\\/"]
Output: 5
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
Example 5:
1
2
Input: grid = ["//","/ "]
Output: 3
Constraints:
- n == grid.length
- n == grid[i].length
- 1 <= n <= 30
- grid[i][j] is either ‘/’, ‘', or ‘ ‘.
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
void dfs(vector<vector<int>> &grid2, int i , int j){
if (i < 0 || i >= grid2.size() || j < 0 || j >= grid2[i].size())
return;
if (grid2[i][j] != 0)
return;
grid2[i][j] = 1;
dfs(grid2, i - 1, j);
dfs(grid2, i + 1, j);
dfs(grid2, i, j - 1);
dfs(grid2, i, j + 1);
}
public:
int regionsBySlashes(vector<string>& grid) {
vector<vector<int>> grid2(grid.size() * 3, vector<int>(grid.size() * 3, 0));
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[i].size(); j++) {
if (grid[i][j] == '/') {
grid2[i * 3 + 0][j * 3 + 2] = 1;
grid2[i * 3 + 1][j * 3 + 1] = 1;
grid2[i * 3 + 2][j * 3 + 0] = 1;
} else if (grid[i][j] == '\\') {
grid2[i * 3 + 0][j * 3 + 0] = 1;
grid2[i * 3 + 1][j * 3 + 1] = 1;
grid2[i * 3 + 2][j * 3 + 2] = 1;
}
}
}
int ans = 0;
for (int i = 0; i < grid2.size(); i++) {
for (int j = 0; j < grid2[i].size(); j++) {
if (grid2[i][j] == 0) {
dfs(grid2, i, j);
ans++;
}
}
}
return ans;
}
};