Algorithm
Problem Name: 959. Regions Cut By Slashes
Problem Link: https://leetcode.com/problems/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].length1 <= n <= 30grid[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)
}
}
Input
grid = [" /","/ "]
Output
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
Input
grid = [" /","/ "]
Output
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;
}
}
}
}
Input
grid = [" /"," "]
Output
1