012 — Regions Cut By Slashes¶

Source¶

Original source: Grid-subdivision connectivity exercise
Platform: LeetCode — https://leetcode.com/problems/regions-cut-by-slashes/
Topic: disjoint set union
Difficulty: Medium
Pattern: cell subdivision + union (প্রতি cell-কে ছোট টুকরোয় ভেঙে DSU)
Basic idea inherited from: 10-এর grid DSU (#10 Number of Islands) — সেখানে cell ছিল একটা node; এখানে প্রতি cell-কে 4টা triangle-এ ভেঙে node বানাই

1. Problem in simple words¶

n × n একটা grid দেওয়া, প্রতিটা ঘরে ' ' (ফাঁকা), '/' বা '\' আঁকা। এই slash গুলো ঘরের ভেতর দিয়ে দেয়াল টানে। সব দেয়াল মিলে পুরো grid কতগুলো আলাদা region-এ ভাগ হলো — সেই সংখ্যা বের করো।

grid = [" /",
        "/ "]

প্রতিটা '/' একটা তির্যক দেয়াল।  দেখা যায় region = 2

2. Which basic idea does this inherit from?¶

এটা সরাসরি #10 (Number of Islands DSU)-র বড় ভাই। সেখানে grid-এর প্রতিটা cell ছিল একটা DSU node, আর পাশাপাশি land cell union হতো। এখানে একই grid-DSU চিন্তা, কিন্তু একটা cell-এর ভেতরেই দেয়াল ঢুকে যাওয়ায় cell-কে আর একটা unit ধরা যায় না — তাই আমরা প্রতিটা cell-কে 4টা triangle-এ ভেঙে আসল node বানাই।

3. What is the hidden math or logic?¶

লুকানো logic আবার সেই equivalence relation: "একই region-এ" সম্পর্কটা reflexive, symmetric, transitive। তাই region গোনা মানে disjoint equivalence class গোনা। চালাকিটা হলো ঠিক জিনিসকে node বানানো: cell নয়, cell-এর চারটে triangle (top=0, right=1, bottom=2, left=3)। দুটো triangle একই region-এ থাকলে union; শেষে আলাদা root-এর সংখ্যাই region সংখ্যা।

4. Which data structure is needed?¶

একটা DSU যাতে 4 · n · n টা element — প্রতিটা cell-এর 4টা triangle। কোনো আলাদা graph লাগে না; cell-এর character আর প্রতিবেশী সম্পর্ক থেকেই union গুলো বেরোয়।

5. Why this data structure fits¶

প্রশ্নটা region গোনা = "কয়টা connected piece?" — DSU-র জন্মগত কাজ। প্রতিটা triangle merge শুধু group জোড়ে, কখনো ভাঙে না — merge-only দুনিয়া, ঠিক DSU যেমন চায়। প্রতিটা union/find amortized near-constant, তাই n × n grid-এ পুরোটা প্রায় linear।

6. Real-life analogy¶

ভাবো একটা টালির মেঝে। প্রতিটা টালি / বা \ দিয়ে তির্যকভাবে দুই রঙে ভাগ করা — উপর-বাঁ অংশ এক, নিচ-ডান অংশ আরেক। তুমি জানতে চাও মেঝেতে মোট কতগুলো আলাদা রঙের "অঞ্চল" তৈরি হলো, যেখানে পাশাপাশি একই রঙের অংশ গুলো একসাথে গোনা হবে। প্রতিটা টালির চার কোণকে আলাদা টুকরো ধরে, যেগুলো ছোঁয়াছুঁয়ি করে তাদের জুড়ে দিলে — অঞ্চলের সংখ্যাই উত্তর।

7. Visual explanation¶

প্রতিটা cell-কে চার triangle-এ ভাঙো; index (r,c)-র triangle: top=0, right=1, bottom=2, left=3।

এক cell-এর চার triangle:

        +-----------+
        | \   0   / |
        |   \   /   |
        | 3   X   1 |
        |   /   \   |
        | /   2   \ |
        +-----------+

cell-এর ভেতরের union (character অনুযায়ী):

  ' '  :  0-1, 1-2, 2-3   (চারটেই এক)
  '/'  :  0-3  আর  1-2    (উপর-বাঁ একসাথে, নিচ-ডান একসাথে)
  '\'  :  0-1  আর  2-3    (উপর-ডান একসাথে, নিচ-বাঁ একসাথে)

প্রতিবেশী cell-এর সাথে union (দেয়াল যাই থাকুক, সীমানা ছোঁয়):

  ডানের cell আছে?   এই cell-এর right(1)  =  ডানের cell-এর left(3)
  নিচের cell আছে?   এই cell-এর bottom(2) =  নিচের cell-এর top(0)

8. Example input and output¶

Input : grid = [" /","/ "]        Output: 2
Input : grid = [" /","  "]        Output: 1
Input : grid = ["/\\","\\/"]      Output: 5
Edge  : grid = ["  ","  "]  ->  সব ফাঁকা, পুরোটা এক region  ->  1

9. Brute force thinking¶

সরল চিন্তা: grid-টাকে 3× (বা 2×) বড় করে এমন একটা pixel-grid বানাও, যেখানে প্রতিটা slash কে কয়েকটা blocked pixel দিয়ে আঁকা যায়।

1) n×n grid -> (3n)×(3n) pixel grid
2) '/' আর '\' কে তির্যক pixel দিয়ে দেয়াল হিসেবে আঁকো (1 = দেয়াল)
3) ফাঁকা (0) pixel-গুলোর উপর flood fill চালিয়ে region গোনো

10. Why brute force is slow¶

3× scaling ঠিক কাজ করে, কিন্তু grid-টা 9 গুণ বড় হয়ে যায় আর flood-fill এর জন্য আলাদা visited array, recursion/stack — code-ও বেশি, edge-এ ভুলও বেশি। DSU version মূল n × n-এই কাজ সারে, scaling লাগে না, আর "region গোনা" সরাসরি root-গোনায় নেমে আসে।

11. Key observation¶

মূল observation: cell নিজে atomic নয় — slash তাকে ভেতরে ভাগ করে দেয়। তাই সঠিক atomic unit হলো cell-এর 4টা triangle। একবার ঠিক unit ধরলে, character → কোন triangle জোড়ে আর প্রতিবেশী → কোন সীমানা ছোঁয় — দুটো নিয়মেই পুরো problem নেমে আসে।

12. Optimized intuition¶

4·n·n triangle নিয়ে DSU বানাও। প্রতিটা cell-এ (1) character অনুযায়ী ভেতরের triangle union করো, (2) ডান ও নিচের প্রতিবেশীর সীমানা-triangle union করো। শুরুতে region = 4·n·n; প্রতিটা সফল union region 1 করে কমায়। শেষে region-এর মান-ই উত্তর — আলাদা করে root গুনতেও হয় না।

13. Thinking tweak¶

মোচড়: "ঘরটা কোন region-এ?" জিজ্ঞেস কোরো না — ঘর তো ভেঙে গেছে। বদলে জিজ্ঞেস করো "এই ঘরের কোন টুকরোটা কোন region-এ?" Node-এর granularity cell থেকে নামিয়ে triangle-এ আনাই পুরো সমাধানের চাবি।

14. Step-by-step dry run¶

Input grid = [" /","/ "], n = 2, triangle index (r·n+c)·4 + t:

cell (0,0) = ' ' → ভেতরে 0-1, 1-2, 2-3 union (3টে সফল merge)
cell (0,0)-র ডান প্রতিবেশী (0,1): right(1) ↔ (0,1).left(3) union
cell (0,0)-র নিচ প্রতিবেশী (1,0): bottom(2) ↔ (1,0).top(0) union
cell (0,1) = '/' → 0-3 আর 1-2 union; ডান প্রতিবেশী নেই; নিচ (1,1): bottom(2) ↔ (1,1).top(0)
cell (1,0) = '/' → 0-3 আর 1-2 union; ডান (1,1): right(1) ↔ (1,1).left(3)
cell (1,1) = ' ' → ভেতরে 0-1, 1-2, 2-3 union
শেষে আলাদা root গোনা যায় 2 → region = 2

15. Python solution¶

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # প্রথমে সবাই নিজের নিজের root
        self.size = [1] * n              # প্রতিটা group-এ একজন

    def find(self, x):                   # representative + path compression
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x

    def union(self, x, y):               # union by size; merge হলে True
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False                 # আগে থেকেই এক group
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx              # rx এখন বড় root
        self.parent[ry] = rx            # ছোটটা বড়টার নিচে ঝোলে
        self.size[rx] += self.size[ry]
        return True


def regions_by_slashes(grid):
    n = len(grid)
    dsu = DSU(4 * n * n)                 # প্রতি cell -> 4 triangle: 0=top 1=right 2=bottom 3=left

    def idx(r, c, t):
        return (r * n + c) * 4 + t

    regions = 4 * n * n                  # শুরুতে সব triangle আলাদা region
    for r in range(n):
        for c in range(n):
            ch = grid[r][c]
            if ch == ' ':                # চার triangle এক
                if dsu.union(idx(r, c, 0), idx(r, c, 1)): regions -= 1
                if dsu.union(idx(r, c, 1), idx(r, c, 2)): regions -= 1
                if dsu.union(idx(r, c, 2), idx(r, c, 3)): regions -= 1
            elif ch == '/':              # top+left, right+bottom
                if dsu.union(idx(r, c, 0), idx(r, c, 3)): regions -= 1
                if dsu.union(idx(r, c, 1), idx(r, c, 2)): regions -= 1
            else:                        # '\\' : top+right, bottom+left
                if dsu.union(idx(r, c, 0), idx(r, c, 1)): regions -= 1
                if dsu.union(idx(r, c, 2), idx(r, c, 3)): regions -= 1
            if c + 1 < n:                # ডানের cell-এর left(3) = এই cell-এর right(1)
                if dsu.union(idx(r, c, 1), idx(r, c + 1, 3)): regions -= 1
            if r + 1 < n:                # নিচের cell-এর top(0) = এই cell-এর bottom(2)
                if dsu.union(idx(r, c, 2), idx(r + 1, c, 0)): regions -= 1
    return regions


# ---- tests ----
assert regions_by_slashes([" /", "/ "]) == 2
assert regions_by_slashes([" /", "  "]) == 1
assert regions_by_slashes(["/\\", "\\/"]) == 5
assert regions_by_slashes(["  ", "  "]) == 1        # সব ফাঁকা -> এক region
print("সব test pass!")

16. Line-by-line code explanation¶

DSU(4 * n * n) — প্রতিটা cell-এর 4টা triangle আলাদা node, তাই মোট 4·n·n।
idx(r, c, t) — (r,c) cell-এর t-তম triangle-এর global index; flatten করার সাধারণ formula।
if ch == ' ' — ফাঁকা ঘরে দেয়াল নেই, তাই চারটে triangle এক region; পরপর তিনটে union যথেষ্ট।
'/' → 0-3 আর 1-2 — তির্যক দেয়াল উপর-বাঁ (top,left) আর নিচ-ডান (right,bottom) আলাদা রাখে।
'\\' → 0-1 আর 2-3 — উল্টো তির্যক, উপর-ডান আর নিচ-বাঁ আলাদা।
প্রতিবেশী union — দেয়াল যাই থাক, দুই cell-এর গায়ে-লাগা সীমানা সবসময় এক region; তাই right↔left আর bottom↔top জোড়া।
regions -= 1 শুধু সফল union-এ — invariant: প্রতিটা সফল merge ঠিক একটা region কমায়।

17. Output walkthrough¶

প্রথম test-এ [" /","/ "] দুই region দেয় — উপরের আর নিচের। দ্বিতীয়ায় একটা মাত্র slash পুরোটা ভাগ করতে পারে না, তাই 1। তৃতীয়ায় ["/\\","\\/"] চারটে slash মাঝখানে একটা হীরের মতো region বানায় + চার কোণ = 5। চতুর্থায় সব ফাঁকা, কোনো দেয়াল নেই — পুরোটা এক, 1। শেষে print: সব test pass!।

18. Time complexity¶

O(n² · α(n²)) ≈ O(n²) — প্রতিটা cell-এ ধ্রুবসংখ্যক union/find, মোট O(n²) operation; প্রতিটা amortized near-constant (inverse Ackermann)।

19. Space complexity¶

O(n²) — DSU-র parent আর size array, প্রতিটার দৈর্ঘ্য 4·n·n। আলাদা scaled grid রাখতে হয় না।

20. Common mistakes¶

triangle index-এ top/right/bottom/left-এর ক্রম এলোমেলো করা, ফলে '/' vs '\\'-এর union ভুল জোড়ায় বসা।
প্রতিবেশী union ভুলে যাওয়া — তাহলে cell গুলো আলাদা থেকে region বেশি গোনা হয়।
'\\' লিখতে গিয়ে escape ভুল করা; Python string-এ backslash সবসময় '\\'।
region count-এর বদলে আলাদা করে root গুনতে গিয়ে find সব node-এ চালানো — অপ্রয়োজনীয়; running regions -= 1-ই যথেষ্ট।

21. Which basic problem this inherits from¶

ভিত্তি: 10-এর #10 Number of Islands (grid DSU)। সেখানে cell = node; এখানে slash cell-কে ভেতরে ভাঙায় triangle = node। দুটোতেই grid-কে DSU element-এ map করার কৌশল এক, শুধু granularity বদলেছে। DSU-র মূল snippet ../concept.md-র "বারো লাইন"-এ।

22. Similar harder problems¶

Number of Islands II (streaming grid connectivity) — https://leetcode.com/problems/number-of-islands-ii/ (এই tracker-এর #13)
Making A Large Island (flip + component size) — https://leetcode.com/problems/making-a-large-island/ (#14)
Most Stones Removed (creative union keys) — https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/ (#11)

23. Pattern learned¶

Cell subdivision + union: যখন একটা grid-cell নিজেই ভেতরে দেয়ালে ভাগ হয়, তখন cell-কে কয়েকটা sub-piece (এখানে 4 triangle)-এ ভেঙে সেই piece গুলোকে DSU node বানাও। ভেতরের union আসে cell-এর content থেকে, বাইরের union আসে প্রতিবেশী সীমানা থেকে। region/piece গোনা = সফল union দিয়ে count কমানো।

24. Final summary¶

ভবিষ্যতের আমাকে: "region/area কয়টা?" দেখলে DSU ভাবো; কিন্তু যদি প্রতিটা unit নিজেই ভেতরে ভাগ হতে পারে (slash, diagonal wall), তখন unit-কে আরও ছোট piece-এ ভাঙো। 4-triangle trick মনে রেখো — content ভেতরে জোড়ে, প্রতিবেশী সীমানায় জোড়ে, বাকিটা DSU-র স্বাভাবিক counting।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।