Sponsored
Sponsored
In this approach, each 1x1 square is divided into four smaller triangles. The / and \ slashes correspond to boundaries between these triangles. We can represent these triangles using a graph and use DFS to count the number of connected components in this graph. Each connection between triangles denotes a passage within the same region.
Time Complexity: O((n * 3) * (n * 3)), where n is the grid size as we traverse each 3x3 cell.
Space Complexity: O((n * 3) * (n * 3)) due to the graph representation.
1class Solution {
2 public int regionsBySlashes(String[] grid) {
3 int n = grid.length;
4 int[][] graph = new int[n * 3][n * 3];
5
6 for (int i = 0; i < n; ++i) {
7 for (int j = 0; j < n; ++j) {
8 if (grid[i].charAt(j) == '/') {
9 graph[i * 3][j * 3 + 2] = 1;
10 graph[i * 3 + 1][j * 3 + 1] = 1;
11 graph[i * 3 + 2][j * 3] = 1;
12 }
13 else if (grid[i].charAt(j) == '\\') {
14 graph[i * 3][j * 3] = 1;
15 graph[i * 3 + 1][j * 3 + 1] = 1;
16 graph[i * 3 + 2][j * 3 + 2] = 1;
17 }
18 }
19 }
20
21 int regions = 0;
22 for (int i = 0; i < n * 3; ++i) {
23 for (int j = 0; j < n * 3; ++j) {
24 if (graph[i][j] == 0) {
25 dfs(graph, i, j);
26 regions++;
27 }
28 }
29 }
30 return regions;
31 }
32
33 private void dfs(int[][] graph, int x, int y) {
34 if (x < 0 || x >= graph.length || y < 0 || y >= graph[0].length || graph[x][y] == 1)
35 return;
36 graph[x][y] = 1;
37 dfs(graph, x + 1, y);
38 dfs(graph, x - 1, y);
39 dfs(graph, x, y + 1);
40 dfs(graph, x, y - 1);
41 }
42}The Java solution follows a similar method to the Python one, where we divide each square into 3x3 graph sections and perform a DFS to find and count the connected components or regions.
This approach uses the Union-Find data structure to manage and merge connected components. Each cell in the grid is broken into four triangles and represented as nodes in the DSU. Connectivity relationships are established and merged as per slashes present in the cell, and the number of disconnected regions is determined.
Time Complexity: O(N^2 * α(N^2)), with α being a very slow-growing function (inverse Ackermann function), coming from the Union-Find operations.
Space Complexity: O(N^2) due to storing parent and rank structures for each cell division.
1var regionsBySlashes = function(grid)
JavaScript implementation uses an analog to the Union-Find model where each sub-triangle is treated as a node. Unions are performed based on grid slots; eventually, counting unique sets gives us the region count.