Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/959.html
959. Regions Cut By Slashes (Medium)
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' '.
Companies: Uber
Related Topics: Depth-first Search, Union Find, Graph
Solution 1.
For a square, if it’s split by a \ or /, the left region (the one touches the left border) is denoted as 0, the right region is denoted as 1.
// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
private:
unordered_set<int> seen;
int ans = 0, N;
int hash(int i, int j, int pos) {
return i + j * 100 + pos * 10000;
}
void insert(queue<int> &q, int h) {
if (seen.find(h) != seen.end()) return;
q.push(h);
seen.insert(h);
}
int bfs(vector<string>& grid, int i, int j, int pos) {
int h = hash(i, j, pos);
if (seen.find(h) != seen.end()) return 0;
seen.insert(h);
queue<int> q;
q.push(h);
while (q.size()) {
int val = q.front();
q.pop();
i = val % 100;
j = val / 100 % 100;
pos = val / 10000;
if (grid[i][j] == '\\') {
if (pos == 0) {
if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
} else {
if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
if (j + 1 < N) insert(q, hash(i, j + 1, 0));
}
} else if (grid[i][j] == '/') {
if (pos == 0) {
if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
} else {
if (j + 1 < N) insert(q, hash(i, j + 1, 0));
if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
}
} else {
insert(q, hash(i, j, 1 - pos));
if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1));
if (j + 1 < N) insert(q, hash(i, j + 1, 0));
if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0));
if (j - 1 >= 0) insert(q, hash(i, j - 1, 1));
}
}
return 1;
}
public:
int regionsBySlashes(vector<string>& grid) {
N = grid.size();
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
ans += bfs(grid, i, j, 0);
ans += bfs(grid, i, j, 1);
}
}
return ans;
}
};
Solution 2.
// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
const int dirs[4][2] = { {0, 1}, {0,-1}, {1, 0}, {-1, 0} };
int N;
void dfs(vector<vector<int>> &g, int x, int y, int color) {
if (x < 0 || x >= N || y < 0 || y >= N || g[x][y]) return;
g[x][y] = color;
for (auto &dir : dirs) dfs(g, x + dir[0], y + dir[1], color);
}
public:
int regionsBySlashes(vector<string>& grid) {
N = grid.size();
vector<vector<int>> g(3 * N, vector<int>(3 * N, 0));
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == '/') g[3 * i][3 * j + 2] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j] = 1;
else if (grid[i][j] == '\\') g[3 * i][3 * j] = g[3 * i + 1][3 * j + 1] = g[3 * i + 2][3 * j + 2] = 1;
}
}
N *= 3;
int ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
if (!g[i][j]) dfs(g, i, j, ++ans + 1);
}
}
return ans;
}
};
Solution 3.
// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Time: O(N^2)
// Space: O(N^2)
#define TO(d) dfs(grid, g, x + dirs[d][0], y + dirs[d][1], d, color)
class Solution {
int N;
void setLeftColor(vector<vector<int>> &g, int x, int y, int color) {
g[x][y] += color * 100;
}
void setRightColor(vector<vector<int>> &g, int x, int y, int color) {
g[x][y] += color;
}
int getLeftColor(vector<vector<int>> &g, int x, int y) {
return g[x][y] / 100;
}
int getRightColor(vector<vector<int>> &g, int x, int y) {
return g[x][y] % 100;
}
int dirs[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
// 0 U, 1 R, 2 D, 3 L
void dfs(vector<string>& grid, vector<vector<int>> &g, int x, int y, int d, int color) {
if (x < 0 || x >= N || y < 0 || y >= N) return;
if (grid[x][y] == ' ') {
if (g[x][y]) return;
g[x][y] = color;
for (int i = 0; i < 4; ++i) TO(i);
} else if (grid[x][y] == '/') {
if (!getLeftColor(g, x, y) && (d == 2 || d == 1)) {
setLeftColor(g, x, y, color);
TO(0);
TO(3);
}
if (!getRightColor(g, x, y) && (d == 0 || d == 3)) {
setRightColor(g, x, y, color);
TO(1);
TO(2);
}
} else {
if (!getLeftColor(g, x, y) && (d == 1 || d == 0)) {
setLeftColor(g, x, y, color);
TO(2);
TO(3);
}
if (!getRightColor(g, x, y) && (d == 2 || d == 3)) {
setRightColor(g, x, y, color);
TO(0);
TO(1);
}
}
}
public:
int regionsBySlashes(vector<string>& grid) {
N = grid.size();
int color = 0;
vector<vector<int>> g(N, vector<int>(N, 0));
for (int x = 0; x < N; ++x) {
for (int y = 0; y < N; ++y) {
if (grid[x][y] == ' ') {
if (!g[x][y]) dfs(grid, g, x, y, 0, ++color);
}
else if (grid[x][y] == '/') {
if (!getLeftColor(g, x, y)) {
++color;
dfs(grid, g, x, y, 1, color);
dfs(grid, g, x, y, 2, color);
}
if (!getRightColor(g, x, y)) {
++color;
dfs(grid, g, x, y, 0, color);
dfs(grid, g, x, y, 3, color);
}
} else {
if (!getLeftColor(g, x, y)) {
++color;
dfs(grid, g, x, y, 0, color);
dfs(grid, g, x, y, 1, color);
}
if (!getRightColor(g, x, y)) {
++color;
dfs(grid, g, x, y, 2, color);
dfs(grid, g, x, y, 3, color);
}
}
}
}
return color;
}
};
-
class Solution { public int regionsBySlashes(String[] grid) { int length = grid.length; int[][][] regions = new int[length][length][4]; int regionCount = 1; int remain = length * length * 4; Queue<int[]> queue = new LinkedList<int[]>(); char topLeft = grid[0].charAt(0); if (topLeft == ' ') { for (int i = 0; i < 4; i++) { regions[0][0][i] = regionCount; remain--; } for (int i = 2; i < 4; i++) queue.offer(new int[]{0, 0, i}); } else if (topLeft == '/') { for (int i = 0; i < 2; i++) { regions[0][0][i] = regionCount; remain--; } regionCount++; for (int i = 2; i < 4; i++) { regions[0][0][i] = regionCount; remain--; queue.offer(new int[]{0, 0, i}); } } else { for (int i = 0; i < 4; i += 2) { regions[0][0][i] = regionCount; remain--; queue.offer(new int[]{0, 0, i}); } } while (remain > 0) { while (!queue.isEmpty()) { int[] subcell = queue.poll(); int row = subcell[0], column = subcell[1], subcellNum = subcell[2]; char c = grid[row].charAt(column); if (c == ' ') { for (int i = 0; i < 4; i++) { if (regions[row][column][i] == 0) { regions[row][column][i] = regionCount; remain--; queue.offer(new int[]{row, column, i}); } } } else if (c == '/') { int num1 = subcellNum % 2 == 0 ? subcellNum : subcellNum - 1; int num2 = num1 + 1; for (int i = num1; i <= num2; i++) { if (regions[row][column][i] == 0) { regions[row][column][i] = regionCount; remain--; queue.offer(new int[]{row, column, i}); } } } else { int num1 = subcellNum < 2 ? subcellNum : subcellNum - 2; int num2 = num1 + 2; for (int i = num1; i <= num2; i += 2) { if (regions[row][column][i] == 0) { regions[row][column][i] = regionCount; remain--; queue.offer(new int[]{row, column, i}); } } } int[] adjacentSubcell = getAdjacentSubcell(row, column, subcellNum); int nextRow = adjacentSubcell[0], nextColumn = adjacentSubcell[1], nextSubcellNum = adjacentSubcell[2]; if (nextRow >= 0 && nextRow < length && nextColumn >= 0 && nextColumn < length && regions[nextRow][nextColumn][nextSubcellNum] == 0) { regions[nextRow][nextColumn][nextSubcellNum] = regionCount; remain--; queue.offer(adjacentSubcell); } } if (remain == 0) break; regionCount++; outer: for (int i = 0; i < length; i++) { for (int j = 0; j < length; j++) { for (int k = 0; k < 4; k++) { if (regions[i][j][k] == 0) { regions[i][j][k] = regionCount; remain--; queue.offer(new int[]{i, j, k}); break outer; } } } } } return regionCount; } public int[] getAdjacentSubcell(int row, int column, int subcellNum) { int[] adjacentSubcell = {row, column, subcellNum}; switch (subcellNum) { case 0: adjacentSubcell[0]--; break; case 1: adjacentSubcell[1]--; break; case 2: adjacentSubcell[1]++; break; case 3: adjacentSubcell[0]++; break; default: } adjacentSubcell[2] = 3 - adjacentSubcell[2]; return adjacentSubcell; } } ############ class Solution { private int[] p; private int size; public int regionsBySlashes(String[] grid) { int n = grid.length; size = n * n * 4; p = new int[size]; for (int i = 0; i < p.length; ++i) { p[i] = i; } for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { int k = i * n + j; if (i < n - 1) { union(4 * k + 2, (k + n) * 4); } if (j < n - 1) { union(4 * k + 1, (k + 1) * 4 + 3); } char v = grid[i].charAt(j); if (v == '/') { union(4 * k, 4 * k + 3); union(4 * k + 1, 4 * k + 2); } else if (v == '\\') { union(4 * k, 4 * k + 1); union(4 * k + 2, 4 * k + 3); } else { union(4 * k, 4 * k + 1); union(4 * k + 1, 4 * k + 2); union(4 * k + 2, 4 * k + 3); } } } return size; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } private void union(int a, int b) { int pa = find(a); int pb = find(b); if (pa == pb) { return; } p[pa] = pb; --size; } } -
// OJ: https://leetcode.com/problems/regions-cut-by-slashes/ // Time: O(N^2) // Space: O(N^2) class Solution { private: unordered_set<int> seen; int ans = 0, N; int hash(int i, int j, int pos) { return i + j * 100 + pos * 10000; } void insert(queue<int> &q, int h) { if (seen.find(h) != seen.end()) return; q.push(h); seen.insert(h); } int bfs(vector<string>& grid, int i, int j, int pos) { int h = hash(i, j, pos); if (seen.find(h) != seen.end()) return 0; seen.insert(h); queue<int> q; q.push(h); while (q.size()) { int val = q.front(); q.pop(); i = val % 100; j = val / 100 % 100; pos = val / 10000; if (grid[i][j] == '\\') { if (pos == 0) { if (j - 1 >= 0) insert(q, hash(i, j - 1, 1)); if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0)); } else { if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1)); if (j + 1 < N) insert(q, hash(i, j + 1, 0)); } } else if (grid[i][j] == '/') { if (pos == 0) { if (j - 1 >= 0) insert(q, hash(i, j - 1, 1)); if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1)); } else { if (j + 1 < N) insert(q, hash(i, j + 1, 0)); if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0)); } } else { insert(q, hash(i, j, 1 - pos)); if (i - 1 >= 0) insert(q, hash(i - 1, j, grid[i - 1][j] == '\\' ? 0 : 1)); if (j + 1 < N) insert(q, hash(i, j + 1, 0)); if (i + 1 < N) insert(q, hash(i + 1, j, grid[i + 1][j] == '\\' ? 1 : 0)); if (j - 1 >= 0) insert(q, hash(i, j - 1, 1)); } } return 1; } public: int regionsBySlashes(vector<string>& grid) { N = grid.size(); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { ans += bfs(grid, i, j, 0); ans += bfs(grid, i, j, 1); } } return ans; } }; -
class Solution: def regionsBySlashes(self, grid: List[str]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] def union(a, b): pa, pb = find(a), find(b) if pa != pb: p[pa] = pb nonlocal size size -= 1 n = len(grid) size = n * n * 4 p = list(range(size)) for i, row in enumerate(grid): for j, v in enumerate(row): k = i * n + j if i < n - 1: union(4 * k + 2, (k + n) * 4) if j < n - 1: union(4 * k + 1, (k + 1) * 4 + 3) if v == '/': union(4 * k, 4 * k + 3) union(4 * k + 1, 4 * k + 2) elif v == '\\': union(4 * k, 4 * k + 1) union(4 * k + 2, 4 * k + 3) else: union(4 * k, 4 * k + 1) union(4 * k + 1, 4 * k + 2) union(4 * k + 2, 4 * k + 3) return size ############ class Solution(object): def regionsBySlashes(self, grid): """ :type grid: List[str] :rtype: int """ self.N = len(grid) m_ = range(self.N * self.N * 4) self.count = self.N * self.N * 4 for row in range(self.N): line = grid[row] for col in range(self.N): w = line[col] if row > 0: self.union(m_, self.position(row - 1, col, 2), self.position(row, col, 0)) if col > 0: self.union(m_, self.position(row, col - 1, 1), self.position(row, col, 3)) if w != '/': self.union(m_, self.position(row, col, 0), self.position(row, col, 1)) self.union(m_, self.position(row, col, 3), self.position(row, col, 2)) if w != '\\': self.union(m_, self.position(row, col, 0), self.position(row, col, 3)) self.union(m_, self.position(row, col, 1), self.position(row, col, 2)) return self.count def find(self, m_, a): if m_[a] == a: return a return self.find(m_, m_[a]) def union(self, m_, a, b): pa = self.find(m_, a) pb = self.find(m_, b) if (pa == pb): return m_[pa] = pb self.count -= 1 def position(self, r, c, i): return (r * self.N + c) * 4 + i -
func regionsBySlashes(grid []string) int { n := len(grid) size := n * n * 4 p := make([]int, size) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } union := func(a, b int) { pa, pb := find(a), find(b) if pa == pb { return } p[pa] = pb size-- } for i, row := range grid { for j, v := range row { k := i*n + j if i < n-1 { union(4*k+2, (k+n)*4) } if j < n-1 { union(4*k+1, (k+1)*4+3) } if v == '/' { union(4*k, 4*k+3) union(4*k+1, 4*k+2) } else if v == '\\' { union(4*k, 4*k+1) union(4*k+2, 4*k+3) } else { union(4*k, 4*k+1) union(4*k+1, 4*k+2) union(4*k+2, 4*k+3) } } } return size }