# Solution For Regions Cut By Slashes

The problem “Regions Cut By Slashes” on LeetCode is about a 2D grid where each cell can be either empty or contain a slash (/) or a backslash (). The slashes divide the cell into four regions, and neighboring cells with slashes can either be connected or disconnected.

The task is to find the total number of regions in the grid. For example, in the following grid:

/\
/ \
\ /
\/

There are 5 regions, as indicated by the different colors:

RR
GBBG
GY
YY

To solve this problem, we can use a modified version of the Union-Find algorithm. We start by initializing a disjoint set for each cell, with the parent of each cell being itself. Then, we iterate over each cell in the grid and perform the following operations:

1. If the cell contains a backslash (), merge its bottom-left region with its top-right region, and its top-left region with its bottom-right region.
2. If the cell contains a slash (/), merge its top-left region with its top-right region, and its bottom-left region with its bottom-right region.
3. If the cell is empty, do nothing.

After all cells have been processed, we count the number of set representatives (i.e. the number of disjoint sets) in the grid to get the total number of regions.

The implementation of the algorithm can be done efficiently using the Union-Find data structure. Here is the example code in Python:

“`
class UnionFind:
def init(self, n):
self.parent = list(range(n))

def find(self, i):
if self.parent[i] != i:
self.parent[i] = self.find(self.parent[i])
return self.parent[i]

def union(self, i, j):
pi, pj = self.find(i), self.find(j)
if pi != pj:
self.parent[pi] = pj

class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
uf = UnionFind(4nn)
for i in range(n):
for j in range(n):
k = 4(in+j)
if grid[i][j] == ‘ ‘:
uf.union(k, k+1)
uf.union(k, k+2)
uf.union(k, k+3)
elif grid[i][j] == ‘/’:
uf.union(k, k+3)
uf.union(k+1, k+2)
else:
uf.union(k, k+1)
uf.union(k+2, k+3)
if i > 0:
uf.union(k, k-4n+2)
if i < n-1:
uf.union(k+2, k+4
n)
if j > 0:
uf.union(k+3, k-3)
if j < n-1:
uf.union(k+1, k+7)
return sum(uf.parent[i] == i for i in range(4nn))
“`

The time complexity of this algorithm is O(n^2 alpha(n)), where alpha(n) is the inverse Ackermann function, which is essentially a constant for any practical value of n. The space complexity is also O(n^2).

## Step by Step Implementation For Regions Cut By Slashes

class Solution {
public int regionsBySlashes(String[] grid) {

//create a n*n 2D array to store the grid information
int n = grid.length;
int[][] dirs = new int[n][n];

//fill in the 2D array
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (grid[r].charAt(c) == '/') {
dirs[r][c] = 1;
} else if (grid[r].charAt(c) == '\\') {
dirs[r][c] = -1;
}
}
}

//perform union find
UF uf = new UF(n * n * 4);
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int root = 4 * (r * n + c);
// north south
uf.union(root + 0, root + 1);
// east west
uf.union(root + 2, root + 3);
// northwest southwest
uf.union(root + 0, root + 2);
// northeast southeast
uf.union(root + 1, root + 3);

if (r + 1 < n) {
// south north
uf.union(root + 1, root + 4 * n + 0);
}
if (r - 1 >= 0) {
// north south
uf.union(root + 0, root - 4 * n + 1);
}
if (c + 1 < n) {
// east west
uf.union(root + 3, root + 4 + 0);
}
if (c - 1 >= 0) {
// west east
uf.union(root + 2, root - 4 + 3);
}
}
}

//count the number of regions
int count = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int root = 4 * (r * n + c);
if (uf.find(root) == root) {
count++;
}
}
}
return count;
}
}

class UF {
int[] parent;
int count;

public UF(int n) {
count = n;
parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}

public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}

public void union(int x, int y) {
int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {
parent[rootx] = rooty;
count--;
}
}
}
def regionsBySlashes(grid):
return 0
var regionsBySlashes = function(grid) {
};
std::vector regionsBySlashes(std::vector& grid) {
int n = grid.size();

// Create a 2D array of size n+1 to represent the
// graph. For eg, for input 3X3 matrix, we will
// have a 4X4 matrix
int graph[n+1][n+1];

// Initially, all the vertices are unvisited
// and hence set to 0
memset(graph, 0, sizeof(graph));

// For each cell of the input matrix, we will
// add edges between the vertices.
// For eg, for input 3X3 matrix, we will have
// total 8 vertices. So, we will have edges
// between all the combination of vertices
for(int i=0; i0 && graph[i-1][j] == 0)
dfs(graph, i-1, j, n);
if(j>0 && graph[i][j-1] == 0)
dfs(graph, i, j-1, n);
if(i
using System;

public class Solution {
public int RegionsBySlashes(string[] grid) {
int N = grid.Length;
DSU dsu = new DSU(4 * N * N);
for (int r = 0; r < N; ++r) {
for (int c = 0; c < N; ++c) {
int root = 4 * (r * N + c);
char val = grid[r][c];
if (val != '\\') {
dsu.Union(root + 0, root + 1);
dsu.Union(root + 2, root + 3);
}
if (val != '/') {
dsu.Union(root + 0, root + 2);
dsu.Union(root + 1, root + 3);
}
// north south
if (r + 1 < N) {
dsu.Union(root + 3, (root + 4 * N) + 0);
}
if (r - 1 >= 0) {
dsu.Union(root + 0, (root - 4 * N) + 3);
}
// east west
if (c + 1 < N) {
dsu.Union(root + 2, (root + 4) + 1);
}
if (c - 1 >= 0) {
dsu.Union(root + 1, (root - 4) + 2);
}
}
}
return dsu.Count;
}
}

public class DSU {
int[] parent;
public int Count {get; private set;}

public DSU(int N) {
parent = new int[N];
Count = N;
for (int i = 0; i < N; ++i) {
parent[i] = i;
}
}

public int Find(int x) {
if (parent[x] != x) parent[x] = Find(parent[x]);
return parent[x];
}

public bool Union(int x, int y) {
int xr = Find(x), yr = Find(y);
if (xr == yr) {
return false;
} else if (xr < yr) {
parent[yr] = xr;
} else {
parent[xr] = yr;
}
--Count;
return true;
}
}

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]