Description
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 ' '.
Solutions
Solution 1: Union-Find
PythonJavaC++GoTypeScriptJavaScript
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(code-box)
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;
}
}(code-box)
class Solution {
public:
vector<int> p;
int size;
int regionsBySlashes(vector<string>& grid) {
int n = grid.size();
size = n * n * 4;
p.resize(size);
for (int i = 0; i < size; ++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) merge(4 * k + 2, (k + n) * 4);
if (j < n - 1) merge(4 * k + 1, (k + 1) * 4 + 3);
char v = grid[i][j];
if (v == '/') {
merge(4 * k, 4 * k + 3);
merge(4 * k + 1, 4 * k + 2);
} else if (v == '\\') {
merge(4 * k, 4 * k + 1);
merge(4 * k + 2, 4 * k + 3);
} else {
merge(4 * k, 4 * k + 1);
merge(4 * k + 1, 4 * k + 2);
merge(4 * k + 2, 4 * k + 3);
}
}
}
return size;
}
void merge(int a, int b) {
int pa = find(a);
int pb = find(b);
if (pa == pb) return;
p[pa] = pb;
--size;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};(code-box)
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
}(code-box)
function regionsBySlashes(grid: string[]): number {
const find = (x: number) => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
const union = (a: number, b: number) => {
const pa = find(a);
const pb = find(b);
if (pa !== pb) {
p[pa] = pb;
size--;
}
};
const n = grid.length;
let size = n * n * 4;
const p = Array.from({ length: size }, (_, i) => i);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const 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 (grid[i][j] === '/') {
union(4 * k, 4 * k + 3);
union(4 * k + 1, 4 * k + 2);
} else if (grid[i][j] === '\\') {
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;
}(code-box)
/**
* @param {string[]} grid
* @return {number}
*/
function regionsBySlashes(grid) {
const find = x => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
const union = (a, b) => {
const pa = find(a);
const pb = find(b);
if (pa !== pb) {
p[pa] = pb;
size--;
}
};
const n = grid.length;
let size = n * n * 4;
const p = Array.from({ length: size }, (_, i) => i);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const 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 (grid[i][j] === '/') {
union(4 * k, 4 * k + 3);
union(4 * k + 1, 4 * k + 2);
} else if (grid[i][j] === '\\') {
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;
}(code-box)
Solution 2: DFS
TypeScriptJavaScript
function regionsBySlashes(grid: string[]): number {
const createGraph = () => {
const n = grid.length;
const g = Array.from({ length: n * 2 }, () => Array(n * 2).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const [y, x] = [i * 2, j * 2];
switch (grid[i][j]) {
case '/':
g[y][x] = g[y + 1][x + 1] = 0;
g[y][x + 1] = g[y + 1][x] = 1;
break;
case '\\':
g[y][x] = g[y + 1][x + 1] = 2;
g[y][x + 1] = g[y + 1][x] = 0;
break;
default:
g[y][x] = g[y][x + 1] = g[y + 1][x] = g[y + 1][x + 1] = 0;
break;
}
}
}
return g;
};
const isValid = (x: number) => 0 <= x && x < n;
const dfs = (i: number, j: number) => {
if (!isValid(i) || !isValid(j) || g[i][j]) return;
g[i][j] = -1;
const dirs = [-1, 0, 1, 0, -1];
const neighbours: number[] = [];
for (let d = 0; d < 4; d++) {
const [y, x] = [i + dirs[d], j + dirs[d + 1]];
if (isValid(y) && isValid(x)) {
dfs(y, x);
neighbours.push(g[y][x]);
} else {
neighbours.push(-1);
}
}
const [top, right, bottom, left] = neighbours;
if (top === 1 && right === 1) dfs(i - 1, j + 1);
if (bottom === 1 && left === 1) dfs(i + 1, j - 1);
if (top === 2 && left === 2) dfs(i - 1, j - 1);
if (bottom === 2 && right === 2) dfs(i + 1, j + 1);
};
const g = createGraph();
const n = g.length;
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] === 0) {
dfs(i, j);
res++;
}
}
}
return res;
}(code-box)
function regionsBySlashes(grid) {
const createGraph = () => {
const n = grid.length;
const g = Array.from({ length: n * 2 }, () => Array(n * 2).fill(0));
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const [y, x] = [i * 2, j * 2];
switch (grid[i][j]) {
case '/':
g[y][x] = g[y + 1][x + 1] = 0;
g[y][x + 1] = g[y + 1][x] = 1;
break;
case '\\':
g[y][x] = g[y + 1][x + 1] = 2;
g[y][x + 1] = g[y + 1][x] = 0;
break;
default:
g[y][x] = g[y][x + 1] = g[y + 1][x] = g[y + 1][x + 1] = 0;
break;
}
}
}
return g;
};
const isValid = x => 0 <= x && x < n;
const dfs = (i, j) => {
if (!isValid(i) || !isValid(j) || g[i][j]) return;
g[i][j] = -1;
const dirs = [-1, 0, 1, 0, -1];
const neighbours = [];
for (let d = 0; d < 4; d++) {
const [y, x] = [i + dirs[d], j + dirs[d + 1]];
if (isValid(y) && isValid(x)) {
dfs(y, x);
neighbours.push(g[y][x]);
} else {
neighbours.push(-1);
}
}
const [top, right, bottom, left] = neighbours;
if (top === 1 && right === 1) dfs(i - 1, j + 1);
if (bottom === 1 && left === 1) dfs(i + 1, j - 1);
if (top === 2 && left === 2) dfs(i - 1, j - 1);
if (bottom === 2 && right === 2) dfs(i + 1, j + 1);
};
const g = createGraph();
const n = g.length;
let res = 0;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (g[i][j] === 0) {
dfs(i, j);
res++;
}
}
}
return res;
}(code-box)
