LeetCode Daily Question 10/08/2024 - Regions Cut By Slashes

Problem 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 '\\'.

class Solution:
  def regionsBySlashes(self, grid: List[str]) -> int:
    n = len(grid)
    size = n * 3
    visited = [[False] * size for _ in range(size)]
    def dfs(i,j):
      if i < 0 or i >= size or j < 0 or j >= size or visited[i][j]:
        return 
      visited[i][j] = True
      dfs(i+1,j)
      dfs(i-1,j)
      dfs(i,j+1)
      dfs(i,j-1)
    
    for i in range(n):
      for j in range(n):
        if grid[i][j] == '/':
          visited[i*3][j*3+2] = True
          visited[i*3+1][j*3+1] = True
          visited[i*3+2][j*3] = True
          
        elif grid[i][j] == '\\':
          visited[i*3][j*3] = True
          visited[i*3+1][j*3+1] = True
          visited[i*3+2][j*3+2] = True
          
    result = 0
    
    for i in range(size):
      for j in range(size):
        if not visited[i][j]:
          dfs(i,j)
          result += 1
          
          
    return result

Explanation:

We can imagine each individual 1x1 cell as a 3x3 binary dot display. Each slash will divide this 3x3 dot display into 2 regions.

So say length of the given grid is 1. We can represent it as

#Example len(grid) = 1, sub-divide into 3 x 3 dot grid.
0 0 0
0 0 0
0 0 0

#If we have '/'
0 0 1
0 1 0 
1 0 0 

#If we have '\'
1 0 0
0 1 0
0 0 1

So now the problem reduces to traversing each 3 x 3 sub-grid and record how these slashes act upon the sub-grid.

n = len(grid)
size = n * 3 #Expand grid
visited = [[False] * size for _ in range(size)]
#so if n = 2 we have 
#0 0 0 0 0 0
#0 0 0 0 0 0
#0 0 0 0 0 0
#0 0 0 0 0 0
#0 0 0 0 0 0
#0 0 0 0 0 0

for i in range(n):
  for j in range(n):
    if grid[i][j] = '/':
      visited[i*3+2][j*3] = True
      visited[i*3+1][j*3+1] = True
      visited[i*3][j*3+2] = True
      
    elif grid[i][j] = '\\':
      visited[i*3][j*3] = True
      visited[i*3+1][j*3+1] = True
      visited[i+3+2][j*3+2] = True

Next, we perform dfs to count the regions. Everytime we arrive at an unvisited cell, we know we are in a separated region, we increment the result count by 1.

def dfs(i,j):
  if i < 0 or i >= size or j < 0 or j >= size or visited[i][j]:
    return
  visited[i][j] = True
  #explore all 4 directions
  dfs(i+1,j)
  dfs(i-1,j)
  dfs(i,j+1)
  dfs(i,j-1)
  
result = 0
#explore the entire expanded subgrid
for i in range(size):
  for j in range(size):
    if not visited[i][j]:
      dfs(i,j)
      result += 1

Finally, we return the result

return result

The full solution can be found near the top of this page.