⚡Flashcard Drill➔
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

  1. Expand each cell into a 3x3 block of pixels, marking the slash paths as walls.
  2. A / occupies the anti-diagonal (0,2), (1,1), (2,0); a \ occupies the main diagonal.
  3. Then the number of regions equals the number of connected components of empty pixels -- a plain flood fill.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems