Welcome to Subscribe On Youtube
959. Regions Cut By Slashes
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
-
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; } } -
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]; } }; -
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 -
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 } -
/** * @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; } -
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; }