Leetcode 959. Regions Cut By Slashes

Explanation: The problem gives N x N grid with each grid having either "/", "", or a blank space. The characters "/" and "" divide the grid into various regions and our task is to return the total count of these regions.

Let's take a simple example for better understanding:

[" /", "/ ", " /", " /"]

The grid will look like this:

/
\ / /
/ \

And the regions are divided like this:

1 2 \ 5 \ 3 / 6 2 \ 4 \ 7 5 / 8 \

The total regions count is 8.

Approach:

The key to solving this problem efficiently is by enhancing the original grid to a larger scale (3 times), to get better clarity in defining the regions divided by "/", and "". We maintain an enhanced grid 'g' and while iterating through the original grid, we mark the cells in 'g' where the character is not a blank space (either "/" or "").

Once we have the enhanced grid 'g', we run a Depth-First Search for each white cell in 'g'. When we run DFS, we can mark the cell as visited and increase our answer count.

The DFS function in our solution will constantly check for valid cells to move (avoiding out of bounds and only choosing white cells/regions) and continue a bread-first traversal.

Python Solution:

1
2python
3class Solution:
4    def regionsBySlashes(self, grid):
5        n, ans = len(grid), 0
6        g = [[0] * (n * 3) for _ in range(n * 3)]
7        
8        for i in range(n):
9            for j in range(n):
10                if grid[i][j] == '/':
11                    g[i * 3][j * 3 + 2] = g[i * 3 + 1][j * 3 + 1] = g[i * 3 + 2][j * 3] = 1
12                elif grid[i][j] == '\\':
13                    g[i * 3][j * 3] = g[i * 3 + 1][j * 3 + 1] = g[i * 3 + 2][j * 3 + 2] = 1
14        
15        def dfs(x, y):
16            if 0 <= x < n * 3 and 0 <= y < n * 3 and g[x][y] == 0:
17                g[x][y] = 2
18                list(map(dfs, [x + 1, x - 1, x, x], [y, y, y + 1, y - 1]))
19
20        for i in range(n * 3):
21            for j in range(n * 3):
22                if g[i][j] == 0:
23                    dfs(i, j)
24                    ans += 1
25        return ans

We are performing DFS on the grid for valid cells and incrementing answer count while marking cells as visited in DFS.JavaScript Solution:

1
2javascript
3class Solution {
4    constructor(N, grid) {
5        this.count = 0;
6        this.dsz = Array.from(Array(N * 3), () => new Array(N * 3).fill(0));
7        this.grid = grid;
8    }
9  
10    regionsBySlashes() {
11        for (let i = 0; i < this.grid.length; i++) {
12            for (let j = 0; j < this.grid[i].length; j++) {
13                if (this.grid[i][j] === '/') {
14                    this.dsz[i * 3][j * 3 + 2] = 
15                    this.dsz[i * 3 + 1][j * 3 + 1] = 
16                    this.dsz[i * 3 + 2][j * 3] = 1;
17                } else if (this.grid[i][j] === '\\') {
18                    this.dsz[i * 3][j * 3] = 
19                    this.dsz[i * 3 + 1][j * 3 + 1] = 
20                    this.dsz[i * 3 + 2][j * 3 + 2] = 1;
21                }
22            }
23        }
24        
25        for (let i = 0; i < this.dsz.length; i++) {
26            for (let j = 0; j < this.dsz[i].length; j++) {
27                if (this.dsz[i][j] === 0) {
28                    this.DFS(i, j);
29                    this.count++;
30                }
31            }
32        }
33        return this.count;
34    }
35
36    DFS(i, j) {
37        if (i < 0 || i >= this.dsz.length || j < 0 || j >= this.dsz[i].length || this.dsz[i][j] !== 0) return;
38        this.dsz[i][j] = 1;
39        this.DFS(i + 1, j);
40        this.DFS(i - 1, j);
41        this.DFS(i, j + 1);
42        this.DFS(i, j - 1);
43    }
44}

A solutions object is created with the properties count, dsz and grid. The regionsBySlashes method and DFS method are very similar to Python where it multiplies the grid 3 times and performs search incrementing count.

Java Solution:

1
2java
3public class Solution {
4    private int ans = 0;
5    private int[][] grid;
6
7    public Solution(String[] inputGrid){
8        int n = inputGrid.length;
9        this.grid = new int[n * 3][n * 3];
10
11        for(int i = 0; i < n; i++)
12            for(int j = 0; j < inputGrid[i].length(); j++){
13                if(inputGrid[i].charAt(j) == '/'){
14                    grid[i * 3][j * 3 + 2] = grid[i * 3 + 1][j * 3 + 1] = grid[i * 3 + 2][j * 3] = 1;
15                } else if(inputGrid[i].charAt(j) == '\\'){
16                    grid[i * 3][j * 3] = grid[i * 3 + 1][j * 3 + 1] = grid[i * 3 + 2][j * 3 + 2] = 1;
17                }
18            }
19    }
20
21    public int regionsBySlashes(){
22        for(int i = 0; i < grid.length; i++){
23            for(int j = 0; j < grid.length; j++){
24                if(grid[i][j] == 0){
25                    DFS(i, j);
26                    ans++;
27                }
28            }
29        }
30        return ans;
31    }
32
33    private void DFS(int x, int y){
34        if(x >= 0 && y >= 0 && x < grid.length && y < grid.length && grid[x][y] == 0){
35            grid[x][y] = 1;
36            DFS(x + 1, y);
37            DFS(x - 1, y);
38            DFS(x, y + 1);
39            DFS(x, y - 1);
40        }
41    }
42}

The Java solution utilizes a class named Solution with its properties ans, grid and methods DFS(),regionsBySlashes(). It operates in a similar fashion to the previously explained solutions.