An n x n grid is filled with / \ or space. Each cell is divided into four triangles (0=top, 1=right, 2=bottom, 3=left). Count regions.
Input: ["/\\","\\/"] → Output: 4Input: ["//"," /"] → Output: 3
Treat each cell as 4 triangles. / divides top-left from bottom-right: union 0 with 3, union 1 with 2. \ divides top-right from bottom-left: union 0 with 1, union 2 with 3. Space: union all 4. Also union adjacent cell triangles.
- Each cell (i,j) has 4 triangles: 4*(i*n+j)+{0,1,2,3} (top=0,right=1,bottom=2,left=3).
- For /: union top(0) with left(3), right(1) with bottom(2).
- For \: union top(0) with right(1), left(3) with bottom(2).
- For space: union all 4.
- Union adjacent cells: bottom of (i,j) with top of (i+1,j); right of (i,j) with left of (i,j+1).
- Count distinct components.
class Solution {
int[] parent;
int count;
public int regionsBySlashes(String[] grid) {
int n = grid.length;
parent = new int[4 * n * n]; count = 4 * n * n;
for (int i = 0; i < parent.length; i++) parent[i] = i;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char c = grid[i].charAt(j);
int base = 4*(i*n+j);
if (c == '/') { union(base,base+3); union(base+1,base+2); }
else if (c == '\') { union(base,base+1); union(base+2,base+3); }
else { union(base,base+1); union(base+1,base+2); union(base+2,base+3); }
if (i+1<n) union(base+2, 4*((i+1)*n+j));
if (j+1<n) union(base+1, 4*(i*n+j+1)+3);
}
}
return count;
}
private int find(int x) { return parent[x]==x?x:(parent[x]=find(parent[x])); }
private void union(int a, int b) {
int pa=find(a), pb=find(b);
if (pa!=pb) { parent[pa]=pb; count--; }
}
}
- Time Complexity: O(N^2 * alpha(N^2))
- Space Complexity: O(N^2)