##### 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. 1 <= grid.length == grid[0].length <= 30
2. grid[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;
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});
}
}
}
if (nextRow >= 0 && nextRow < length && nextColumn >= 0 && nextColumn < length && regions[nextRow][nextColumn][nextSubcellNum] == 0) {
regions[nextRow][nextColumn][nextSubcellNum] = regionCount;
remain--;
}
}
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:
break;
case 1:
break;
case 2:
break;
case 3:
break;
default:
}
}
}

############

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
}