012 — Regions Cut By Slashes

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• 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 বানাই

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

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

উদাহরণ

grid = [" /",
        "/ "]

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

Input ও output

উদাহরণ

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

চেনা উদাহরণে বোঝা

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

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

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

ভেতরের যুক্তি

লুকানো 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 সংখ্যা।

কী দিয়ে তথ্য রাখব

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

এটি কেন উপযুক্ত

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

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: 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 গোনো

কোথায় বেশি কাজ হচ্ছে

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

যে বিষয়টি খেয়াল করতে হবে

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

আরও কম কাজে সমাধান

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

ভাবনার পরিবর্তন

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

ছবিতে বোঝা

প্রতিটা 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)

ছোট input-এ ধাপে ধাপে

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

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

কোড ও ব্যাখ্যা

Python

Python

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!")

কোডের প্রতিটি অংশ

• 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 কমায়।

Output মিলিয়ে দেখা

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

খরচ ও সাধারণ ভুল

সময়

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

অতিরিক্ত জায়গা

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

যে ভুলগুলো এড়াতে হবে

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

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

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

পরের অনুশীলন

• 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)

কৌশলটি মনে রাখুন

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

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "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।