NeetCode #593LC-959MediumGraphs
← Back to All Problems#593 · #959 · Regions Cut By Slashes(由斜杠划分区域)
📌 Problem Statement & Constraints
An
n x n grid of /, \ and represents a picture divided into regions by the slashes. Return the number of regions. Constraints: 1 <= n <= 30.💡 Core Algorithmic Approaches
- Expand each cell into a 3x3 block of pixels, marking the slash paths as walls.
- A
/occupies the anti-diagonal(0,2), (1,1), (2,0); a\occupies the main diagonal. - Then the number of regions equals the number of connected components of empty pixels -- a plain flood fill.
- The 3x3 expansion is what makes diagonal slashes block 4-directional movement correctly.
💻 Benchmark Python3 Implementation
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
N = 3 * n
big = [[0] * N for _ in range(N)]
for i in range(n):
for j in range(n):
r, c = 3 * i, 3 * j
ch = grid[i][j]
if ch == "/":
big[r][c + 2] = big[r + 1][c + 1] = big[r + 2][c] = 1
elif ch == "\\":
big[r][c] = big[r + 1][c + 1] = big[r + 2][c + 2] = 1
count = 0
for i in range(N):
for j in range(N):
if big[i][j] == 0:
count += 1
big[i][j] = 1
stack = [(i, j)]
while stack:
r, c = stack.pop()
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and big[nr][nc] == 0:
big[nr][nc] = 1
stack.append((nr, nc))
return count⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the expanded grid has 9n^2 cells, each visited once.
💾 Space Complexity
O(n^2) for the expanded grid.
⚠️ Interview Pitfalls & Follow-ups
- Working on the original grid: 4-directional movement cannot represent diagonal walls.
- Expanding by 2 instead of 3: a slash and a backslash crossing in the same cell would not be distinguishable.
- Using recursion for the flood fill: the expanded grid can be 90x90, which is fine, but the iterative stack avoids depth concerns.
- Forgetting that a space cell contributes one region: the expansion leaves it fully empty.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.