## Algorithm

Problem Name: 959. Regions Cut By Slashes

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:

```Input: grid = [" /","/ "]
Output: 2
```

Example 2:

```Input: grid = [" /","  "]
Output: 1
```

Example 3:

```Input: grid = ["/\\","\\/"]
Output: 5
Explanation: Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.
```

Constraints:

• `n == grid.length == grid[i].length`
• `1 <= n <= 30`
• `grid[i][j]` is either `'/'`, `'\'`, or `' '`.

## Code Examples

### #1 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const regionsBySlashes = function(grid) {
const len = grid.length
let regionsNum = 0
const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]]
const matrix = Array.from({ length: 3 * len }, () => new Array(3 * len).fill(0))

for (let i = 0; i  <  len; i++) {
for (let j = 0; j  <  len; j++) {
if (grid[i][j] === '/') matrix[i * 3][j * 3 + 2] = matrix[i * 3 + 1][j * 3 + 1] = matrix[i * 3 + 2][j * 3] = 1
if (grid[i][j] === '\\') matrix[i * 3][j * 3] = matrix[i * 3 + 1][j * 3 + 1] = matrix[i * 3 + 2][j * 3 + 2] = 1
}
}

for (let i = 0; i  <  matrix.length; i++) {
for (let j = 0; j  <  matrix.length; j++) {
if (matrix[i][j] === 0) {
dfs(matrix, i, j, dirs)
regionsNum++
}
}
}
return regionsNum
}
function dfs(m, i, j, dirs) {
if (i >= 0 && j >= 0 && i < m.length && j < m.length && m[i][j] === 0) {
m[i][j] = 1
for (let dir of dirs) dfs(m, i + dir[0], j + dir[1], dirs)
}
}
``````
Copy The Code &

Input

cmd
grid = [" /","/ "]

Output

cmd
2

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def regionsBySlashes(self, grid):
def dfs(i, j, k):
if 0 <= i < n > j >= 0 and not matrix[i][j][k]:
if grid[i][j] == "*":
if k <= 1:
matrix[i][j][0] = matrix[i][j][1] = cnt
dfs(i - 1, j, 2)
dfs(i, j + 1, 3)
else:
matrix[i][j][2] = matrix[i][j][3] = cnt
dfs(i + 1, j, 0)
dfs(i, j - 1, 1)
elif grid[i][j] == "/":
if 1 <= k <= 2:
matrix[i][j][1] = matrix[i][j][2] = cnt
dfs(i, j + 1, 3)
dfs(i + 1, j, 0)
else:
matrix[i][j][0] = matrix[i][j][3] = cnt
dfs(i - 1, j, 2)
dfs(i, j - 1, 1)
else:
matrix[i][j][0] = matrix[i][j][1] = matrix[i][j][2] = matrix[i][j][3] = cnt
dfs(i - 1, j, 2)
dfs(i, j + 1, 3)
dfs(i + 1, j, 0)
dfs(i, j - 1, 1)
grid, n = [row.replace("\u005C\u005C", "*") for row in grid], len(grid)
matrix, cnt = [[[0, 0, 0, 0] for j in range(n)] for i in range(n)], 0
for i in range(n):
for j in range(n):
for k in range(4):
if not matrix[i][j][k]:
cnt += 1
dfs(i, j, k)
return cnt
``````
Copy The Code &

Input

cmd
grid = [" /","/ "]

Output

cmd
2

### #3 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0959_RegionsCutBySlashes
{
public int RegionsBySlashes(string[] grid)
{
var N = grid.Length;
var uf = new UnionFind(4 * N * N);
for (int i = 0; i  <  N; i++)
for (int j = 0; j  <  N; j++)
{
if (i > 0) uf.Union(ComputeIndex(i, j, 0, N), ComputeIndex(i - 1, j, 2, N));
if (j > 0) uf.Union(ComputeIndex(i, j, 3, N), ComputeIndex(i, j - 1, 1, N));
if (grid[i][j] != '\\')
{
uf.Union(ComputeIndex(i, j, 0, N), ComputeIndex(i, j, 3, N));
uf.Union(ComputeIndex(i, j, 1, N), ComputeIndex(i, j, 2, N));
}
if (grid[i][j] != '/')
{
uf.Union(ComputeIndex(i, j, 0, N), ComputeIndex(i, j, 1, N));
uf.Union(ComputeIndex(i, j, 2, N), ComputeIndex(i, j, 3, N));
}
}

return uf.Count();
}

private int ComputeIndex(int row, int column, int index, int N)
{
return (row * N + column) * 4 + index;
}

public class UnionFind
{
private int[] parents;
private int capacity;
private int count;

public UnionFind(int capacity)
{
this.capacity = capacity;
this.count = capacity;
this.parents = new int[capacity];
for (int i = 0; i  <  capacity; i++)
parents[i] = i;
}

public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);

return parents[index];
}

public void Union(int index1, int index2)
{
var p1 = Find(index1);
var p2 = Find(index2);

if (p1 != p2)
{
parents[p1] = p2;
count--;
}
}

public int Count()
{
return count;
}
}
}
}
``````
Copy The Code &

Input

cmd
grid = [" /"," "]

Output

cmd
1