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 <= 30grid[i][j]is either'/','\', or' '.
Solution 1: Split grid into 4 triangles and Union Find Faces
Divide each grid into 4 triangles and union them if not split.
Time complexity: O(n^2*alphn(n^2))
Space complexity: O(n^2)
C++
|
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 43 44 45 46 47 48 49 50 51 52 53 54 |
class Solution { public: int regionsBySlashes(vector<string>& grid) { int n = grid.size(); DSU dsu(4 * n * n); for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) { int index = 4 * (r * n + c); switch (grid[r][c]) { case '/': dsu.merge(index + 0, index + 3); dsu.merge(index + 1, index + 2); break; case '\\': dsu.merge(index + 0, index + 1); dsu.merge(index + 2, index + 3); break; case ' ': dsu.merge(index + 0, index + 1); dsu.merge(index + 1, index + 2); dsu.merge(index + 2, index + 3); break; default: break; } if (r + 1 < n) dsu.merge(index + 2, index + 4 * n + 0); if (c + 1 < n) dsu.merge(index + 1, index + 4 + 3); } int ans = 0; for (int i = 0; i < 4 * n * n; ++i) if (dsu.find(i) == i) ++ans; return ans; } private: class DSU { public: DSU(int n): parent_(n) { for (int i = 0; i < n; ++i) parent_[i] = i; } int find(int x) { if (parent_[x] != x) parent_[x] = find(parent_[x]); return parent_[x]; } void merge(int x, int y) { parent_[find(x)] = find(y); } private: vector<int> parent_; }; }; |
Solution 2: Euler’s Formula / Union-Find vertices
C++
|
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 43 |
class Solution { public: int regionsBySlashes(vector<string>& grid) { int n = grid.size(); p_ = vector<int>((n + 1) * (n + 1)); // All vertices on the boundaries are merged into root(0). for (int r = 0; r < n + 1; ++r) for (int c = 0; c < n + 1; ++c) p_[getIndex(n, r, c)] = (r == 0 || r == n || c == 0 || c == n) ? 0 : getIndex(n, r, c); int f = 1; for (int r = 0; r < n; ++r) for (int c = 0; c < n; ++c) { if (grid[r][c] == ' ') continue; // A new face will created if two vertices are already in the same group. if (grid[r][c] == '/') { f += merge(getIndex(n, r, c + 1), getIndex(n, r + 1, c)); } else { f += merge(getIndex(n, r, c), getIndex(n, r + 1, c + 1)); } } return f; } private: vector<int> p_; int getIndex(int n, int r, int c) { return r * (n + 1) + c; } int find(int x) { if (p_[x] != x) p_[x] = find(p_[x]); return p_[x]; } int merge(int x, int y) { int rx = find(x); int ry = find(y); if (rx == ry) return 1; p_[ry] = rx; return 0; } }; |
Solution 3: Pixelation (Upscale 3 times)
Time complexity: O(n^2)
Space complexity: O(n^2)
C++
|
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 |
// Author: Huahua, running time: 20 ms class Solution { public: int regionsBySlashes(vector<string>& grid) { const 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 + 0][j * 3 + 2] = 1; g[i * 3 + 1][j * 3 + 1] = 1; g[i * 3 + 2][j * 3 + 0] = 1; } else if (grid[i][j] == '\\') { g[i * 3 + 0][j * 3 + 0] = 1; g[i * 3 + 1][j * 3 + 1] = 1; g[i * 3 + 2][j * 3 + 2] = 1; } } int ans = 0; for (int i = 0; i < 3 * n; ++i) for (int j = 0; j < 3 * n; ++j) { if (g[i][j]) continue; visit(g, j, i, n * 3); ++ans; } return ans; } private: void visit(vector<vector<int>>& g, int x, int y, int n) { if (x < 0 || x >= n || y < 0 || y >= n) return; if (g[y][x]) return; g[y][x] = 1; visit(g, x + 1, y, n); visit(g, x, y + 1, n); visit(g, x - 1, y, n); visit(g, x, y - 1, n); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment