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
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/
// Author: github.com/lzl124631x
// 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;
}
};// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Author: github.com/lzl124631x
// 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;
}
};// OJ: https://leetcode.com/problems/regions-cut-by-slashes/
// Author: github.com/lzl124631x
// 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;
}
};