959. Regions Cut By Slashes
DFS, BFS, Union Find, Array, Hash Table, Matrix, AMateList ·Problem Statement
link: LeetCode.cn LeetCode 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:
Input: grid = [" /","/ "]
Output: 2
Input: grid = [" /"," "]
Output: 1
Input: grid = ["/\\","\\/"]
Output: 5
Constraints: n == grid.length == grid[i].length 1 <= n <= 30 grid[i][j] is either ‘/’, ‘', or ‘ ‘.
Solution Approach
The solution transforms the grid into a larger matrix where each cell is divided into 9 smaller cells based on the slashes, and then uses DFS to count the number of connected components in the resulting matrix.
Algorithm
- Grid Expansion: The original grid is expanded into a larger matrix (3 times the size in both dimensions) where each cell is divided into 9 smaller cells to accommodate the slashes and their impact on the region boundaries.
- Slash Representation: The slashes (/ and ) are used to mark boundaries in the expanded matrix, creating barriers between different regions by setting appropriate cells to 1.
- DFS Traversal: A depth-first search (DFS) is performed on the expanded matrix to identify and count distinct regions by marking all connected cells starting from any unvisited cell.
Complexity
time complexity: O((3n)^2) DFS is performed on the expanded grid. In the worst case, every cell in the 3m x 3n grid could be visited once, leading to a time complexity of O((3m) * (3n)) which simplifies to O(m * n). space complexity: O((3n)^2) The space required to store the 3m x 3n grid is O((3m) * (3n)) which simplifies to O(m * n). In the worst case, the depth of the recursion could be the size of the grid, so the space required for the DFS call stack is also O(m * n).
Implement
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
m, n = len(grid), len(grid[0])
new_grid = [[0 for _ in range(3 * n)] for _ in range(3 * m)]
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '/':
new_grid[3 * i][3 * j + 2] = 1
new_grid[3 * i + 1][3 * j + 1] = 1
new_grid[3 * i + 2][3 * j] = 1
if grid[i][j] == '\\':
new_grid[3 * i][3 * j] = 1
new_grid[3 * i + 1][3 * j + 1] = 1
new_grid[3 * i + 2][3 * j + 2] = 1
def dfs(i, j):
if 0 <= i < 3 * m and 0 <= j < 3 * n and new_grid[i][j] == 0:
new_grid[i][j] = 1
for r, c in [(i + 1, j),(i, j + 1), (i - 1, j), (i, j - 1)]:
dfs(r, c)
for i in range(3 * m):
for j in range(3 * n):
if new_grid[i][j] == 0:
res += 1
dfs(i, j)
return res