003 — Flood Fill

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

Problem link ও উৎস

• Original source: Classic paint-bucket / flood fill exercise
• Platform: LeetCode — https://leetcode.com/problems/flood-fill/
• Topic: graphs
• Difficulty: Easy
• Pattern: DFS on a grid (implicit graph)
• Basic idea inherited from: recursion (../../06-recursion-and-backtracking/); grid-as-graph

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

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

একটা image দেওয়া আছে — সংখ্যা দিয়ে ভরা একটা 2D grid, প্রতিটা সংখ্যা একটা pixel-এর রং। তোমাকে একটা শুরুর pixel (sr, sc) আর একটা নতুন রং color দেওয়া হবে। শুরুর pixel-টা আর তার সাথে 4-দিকে (উপর/নিচ/বাম/ডান) লেগে থাকা একই রঙের সব pixel-কে নতুন রঙে বদলে দাও — ঠিক image editor-এর paint-bucket tool যেভাবে কাজ করে।

উদাহরণ

আগে (start (1,1), new color 2):    পরে:
  1 1 1                               2 2 2
  1 1 0                               2 2 0
  1 0 1                               2 0 1

Input ও output

উদাহরণ

Input : image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]

Edge case (নতুন রং == পুরোনো রং): image = [[0,0,0],[0,0,0]], sr=0, sc=0, color=0
Output: [[0,0,0],[0,0,0]]   (কোনো পরিবর্তন নেই; infinite loop এড়াতে আগেই return)

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

একটা coloring book-এর একটা আবদ্ধ ঘরে এক ফোঁটা রং ফেলো। রংটা ছড়াতে থাকে যতক্ষণ না কোনো সীমারেখায় (ভিন্ন রঙে) আটকায়। flood fill ঠিক তাই: শুরুর pixel থেকে রং ততক্ষণ ছড়ায় যতক্ষণ একই-রঙা pixel পাওয়া যায়; ভিন্ন রং বা grid-এর প্রান্ত এলেই থেমে যায়।

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

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

মূল ভিত হলো recursion (../../06-recursion-and-backtracking/) আর grid-as-graph। একটা grid আসলে একটা implicit graph: প্রতিটা cell একটা node, আর তার 4 প্রতিবেশী হলো তার edges (../concept.md)। DFS এই graph-এ এক pixel থেকে নেমে recursively একই-রঙা প্রতিবেশীতে ছড়ায় — ../dfs.md-এর "flood fill = pixels-এ DFS"।

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

লুকানো logic: যে সব pixel শুরুর pixel-এর সাথে একই-রঙা পথ ধরে connected, তারা মিলে একটা connected region তৈরি করে। DFS এই region-এর প্রতিটা pixel ঠিক একবার ছোঁয়। মোক্ষম জায়গা — recolor করাটাই visited-marking: একবার একটা pixel নতুন রং পেয়ে গেলে সে আর old রঙের সাথে match করে না, তাই আবার ছোঁয়া হয় না। এই কারণেই old == color হলে আগেই থামতে হয়, নাহলে কিছুই বদলায় না বলে DFS চিরকাল loop করবে।

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

• Grid নিজেই — কোনো আলাদা adjacency list লাগে না; 4-দিকের offset গুলোই edges।
• Recursion (call stack) — DFS-এর implicit stack; কোনো দৃশ্যমান visited set লাগে না কারণ recolor-ই mark।

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

Grid implicit graph হিসেবে fit করে কারণ neighbor গুলো on the fly compute করা যায় — (r±1, c) আর (r, c±1); কোনো dict বানানোর দরকার নেই। আর recursion fit করে কারণ flood fill-এর গঠনটাই self-similar: "এই pixel রং করো, তারপর প্রতিটা প্রতিবেশীতে একই কাজ করো" — হুবহু recursive সংজ্ঞা।

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

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

সরল চিন্তা: পুরো grid বারবার scan করো; যতবার এমন কোনো old-রঙা pixel পাও যে ইতিমধ্যে রং-হওয়া কোনো pixel-এর প্রতিবেশী, তাকে রং করো — যতক্ষণ না একটা পুরো pass-এ আর কিছু বদলায়।

উদাহরণ

পুনরাবৃত্তি করো:
  grid scan করো
  rang-হওয়া কোনো cell-এর প্রতিবেশী old-রঙা cell পেলে রং করো
যতক্ষণ একটা pass-এ কোনো পরিবর্তন না হয়

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

বারবার পুরো grid scan করা মানে region-এর প্রতিটা cell রং হতে পুরো একেকটা O(R·C) pass লাগতে পারে — সবমিলে অনেক বেশি কাজ। DFS (বা BFS) প্রতিটা cell ঠিক একবার ছোঁয়, পুরো region O(R·C)-তেই শেষ — repeated scanning সম্পূর্ণ অপ্রয়োজনীয়।

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

মূল observation: রং করা মানেই দেখা-হয়ে-গেছে চিহ্নিত করা। আলাদা visited set লাগে না — একটা pixel নতুন রং পাওয়ার পর সে আর old-এর সাথে match করে না, তাই স্বাভাবিকভাবেই আর প্রক্রিয়া হয় না। শুধু খেয়াল: old == color হলে এই চিহ্নিতকরণটাই কাজ করে না, তাই আগে থামতে হবে।

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

শুরুর pixel-এর old রং মনে রাখো। যদি old == color, কিছু করার নেই — return। নাহলে DFS: cell-টা bounds-এর ভেতরে আর old-রঙা হলে তাকে নতুন রং দাও, তারপর তার 4 প্রতিবেশীতে recurse করো। recolor নিজেই mark, তাই কোনো loop হয় না।

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

মোচড়: "কোন pixel গুলো একই region-এ আছে আগে বের করব, তারপর রং করব" না ভেবে ভাবো "এই pixel রং করো, তারপর হুবহু একই কাজ চার প্রতিবেশীতে চালাও।" region খোঁজা আর রং করা একই recursive পদক্ষেপে মিলে যায়।

ছবিতে বোঝা

image এর (1,1), রং 1, নতুন রং 2 দিয়ে দেখি কীভাবে DFS ছড়ায়:

উদাহরণ

grid (. = ভিন্ন রং, সীমা):
  1 1 1                start = (1,1)
  1 1 .
  1 . 1

DFS ক্রম (recolor = mark):
  (1,1)->2  ->  (0,1)->2  ->  (0,0)->2  ->  (0,2)->2
            ->  (1,0)->2  ->  (2,0)->2
  (2,1)=. থামো,  (1,2)=. থামো,  (2,2) connected না

ফল:
  2 2 2
  2 2 .
  2 . 1

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

Input image = [[1,1,1],[1,1,0],[1,0,1]], sr=1, sc=1, color=2:

1. old = image[1][1] = 1। old != color (2), তাই এগোও।
2. dfs(1,1): bounds OK, value 1 == old → রং 2। প্রতিবেশী: (0,1),(2,1),(1,0),(1,2)।
3. dfs(0,1): 1 == old → রং 2। প্রতিবেশী (0,0),(0,2) পরে রং পাবে।
4. dfs(0,0): 1 → 2। dfs(0,2): 1 → 2।
5. dfs(2,1): value 0 ≠ old → থামো। dfs(1,2): value 0 ≠ old → থামো।
6. dfs(1,0): 1 → 2। প্রতিবেশী dfs(2,0): 1 → 2।
7. (2,2) কখনো connected না, রং 1-ই থাকে। ফল: [[2,2,2],[2,2,0],[2,0,1]]।

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

Python

Python

def flood_fill(image, sr, sc, color):
    R, C = len(image), len(image[0])
    old = image[sr][sc]
    if old == color:                 # crucial: একই রং হলে infinite loop এড়াও
        return image

    def dfs(r, c):
        # grid = implicit graph; recolor করাটাই visited-mark
        if 0 <= r < R and 0 <= c < C and image[r][c] == old:
            image[r][c] = color
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                dfs(r + dr, c + dc)  # recursion = call stack DFS

    dfs(sr, sc)
    return image

# ---- tests ----
assert flood_fill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2) == [[2, 2, 2], [2, 2, 0], [2, 0, 1]]
assert flood_fill([[0, 0, 0], [0, 0, 0]], 0, 0, 0) == [[0, 0, 0], [0, 0, 0]]   # same color
assert flood_fill([[0, 0, 0], [0, 1, 0]], 1, 1, 2) == [[0, 0, 0], [0, 2, 0]]   # একা pixel
print("সব test pass!")

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

• R, C = len(image), len(image[0]) — grid-এর মাপ, bounds check-এর জন্য।
• old = image[sr][sc] — যে রংটা flood করতে হবে; এটাই DFS-এর match শর্ত।
• if old == color: return image — নতুন রং পুরোনোটার সমান হলে কিছু বদলায় না, আর mark কাজ না করায় infinite loop হতো; তাই আগে থামো।
• if 0 <= r < R and 0 <= c < C and image[r][c] == old — bounds-এর ভেতরে আর old-রঙা হলেই এগোও; index করার আগে bounds check।
• image[r][c] = color — recolor; এটাই visited-marking।
• for dr, dc in (...) — চার প্রতিবেশীতে recurse; offset list-ই হলো implicit edges।

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

flood_fill([[1,1,1],[1,1,0],[1,0,1]], 1, 1, 2): old = 1, color = 2, আলাদা। (1,1) থেকে DFS ছড়িয়ে সব connected 1-কে 2 করে; 0 আর বিচ্ছিন্ন কোণার 1 অছোঁয়া থাকে → [[2,2,2],[2,2,0],[2,0,1]]। same-color test কিছু না বদলে return করে। শেষে print: সব test pass!।

JavaScript ও test cases

JavaScript

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

function floodFill(image, sr, sc, color) {
  const R = image.length, C = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image;             // crucial: একই রং হলে infinite loop এড়াও

  const dfs = (r, c) => {
    // grid = implicit graph; recolor করাটাই visited-mark
    if (r >= 0 && r < R && c >= 0 && c < C && image[r][c] === old) {
      image[r][c] = color;
      dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);  // চার প্রতিবেশী
    }
  };
  dfs(sr, sc);
  return image;
}

const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);

// ---- test cases ----
assert(eq(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2), [[2, 2, 2], [2, 2, 0], [2, 0, 1]]), "basic");
assert(eq(floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0), [[0, 0, 0], [0, 0, 0]]), "same color");
assert(eq(floodFill([[0, 0, 0], [0, 1, 0]], 1, 1, 2), [[0, 0, 0], [0, 2, 0]]), "একা pixel");
console.log("সব JS test pass!");

JS টীকা: old === color check-টা গুরুত্বপূর্ণ — JS-এও recolor-ই হলো visited-mark, তাই নতুন রং পুরোনোটার সমান হলে mark কাজ করে না আর DFS অসীম loop করবে; তাই আগেই return। bounds check অবশ্যই index করার আগে করতে হয়, কারণ JS-এ out-of-range index undefined দেয় (Python-এর negative-wrap-এর মতো নয়, কিন্তু তবু ভুল)। 2D array তুলনায় JSON.stringify।

TypeScript ও test cases

TypeScript

type Image = number[][];

function floodFill(image: Image, sr: number, sc: number, color: number): Image {
  const R = image.length, C = image[0].length;
  const old = image[sr][sc];
  if (old === color) return image;

  const dfs = (r: number, c: number): void => {
    if (r >= 0 && r < R && c >= 0 && c < C && image[r][c] === old) {
      image[r][c] = color;
      dfs(r - 1, c); dfs(r + 1, c); dfs(r, c - 1); dfs(r, c + 1);
    }
  };
  dfs(sr, sc);
  return image;
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a: Image, b: Image): boolean =>
  a.length === b.length && a.every((row, i) => row.length === b[i].length && row.every((v, j) => v === b[i][j]));

expect(eq(floodFill([[1, 1, 1], [1, 1, 0], [1, 0, 1]], 1, 1, 2), [[2, 2, 2], [2, 2, 0], [2, 0, 1]]), "basic");
expect(eq(floodFill([[0, 0, 0], [0, 0, 0]], 0, 0, 0), [[0, 0, 0], [0, 0, 0]]), "same");
expect(eq(floodFill([[0, 0, 0], [0, 1, 0]], 1, 1, 2), [[0, 0, 0], [0, 2, 0]]), "একা");
console.log("সব TS test pass!");

TS টীকা: type Image = number[][] grid-এর আকার type-এ লিখে দেয়, তাই image[r][c]-এ ভুল করে string তুলনা করলে compiler ধরবে। sr, sc, color সব number — coordinate আর রং একই ধরনের, ভুল argument-order সহজে আটকায়। return type Image নিশ্চিত করে function পরিবর্তিত grid-ই ফেরত দেয়।

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

সময়

O(R · C) — সবচেয়ে খারাপ ক্ষেত্রে (পুরো grid এক রঙ) প্রতিটা cell ঠিক একবার visit হয়।

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

O(R · C) — recursion-এর call stack সবচেয়ে খারাপ ক্ষেত্রে পুরো region গভীরে নামতে পারে (এক লম্বা snake-আকৃতির region)। আলাদা visited structure লাগে না।

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

• old == color check বাদ দেওয়া — তখন recolor mark হিসেবে কাজ করে না, DFS চিরকাল loop করে।
• index করার আগে bounds check না করা — Python negative index-কে চুপিচুপি wrap করে ভুল cell ছোঁয়।
• recolor করার আগে recurse করা — region আবার আবার ছোঁয়া হয়ে loop হয়।
• diagonal প্রতিবেশী যোগ করে ফেলা যখন শুধু 4-direction চাওয়া।

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

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

ভিত্তি: recursion (../../06-recursion-and-backtracking/) আর grid-as-graph (../concept.md-এর neighbors snippet)। ../dfs.md-এর flood_fill snippet হুবহু এই pattern — paint-bucket = DFS, recolor = mark। এর ঠিক উপরেই দাঁড়ায় Number of Islands (#4): flood fill plus একটা counter।

পরের অনুশীলন

• Number of Islands (flood fill + component counter) — https://leetcode.com/problems/number-of-islands/ (এই tracker-এর #4)
• Max Area of Island (flood fill + size গোনা) — https://leetcode.com/problems/max-area-of-island/ (#5)
• Pacific Atlantic Water Flow (border থেকে reverse flood) — https://leetcode.com/problems/pacific-atlantic-water-flow/ (#14)

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

DFS flood fill on a grid: grid কে implicit graph ধরে এক cell থেকে recursively connected region ছড়ানো, যেখানে cell mutate করাই (recolor / sink) visited-marking। এটাই গোটা grid-component পরিবারের মূল building block।

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

ভবিষ্যতের আমাকে: "flood fill = grid-এ DFS, যেখানে রং বদলানোটাই দেখা-হলো চিহ্ন।" old == color হলে আগেই থামবে; নাহলে bounds + match check করে cell রং করে চার প্রতিবেশীতে recurse করবে। এই reflex পাকা হলে islands, area, reverse-flood — সব এর উপর গড়ে উঠবে।

কোথায় কাজে লাগে

• Paint-bucket tool: যেকোনো image editor (Photoshop, MS Paint)-এ একটা region একই রঙে ভরে দেওয়া — এটাই আক্ষরিক flood fill।
• Region selection / magic wand: একটা pixel ক্লিক করলে তার সাথে একই-রঙা connected অঞ্চল select করা।
• Maze / connectivity check: একটা কোষ থেকে শুরু করে কোন কোষগুলোতে পৌঁছানো যায় তা বের করা (reachability)।
• Game mechanics: Minesweeper-এ খালি ঘর খোলা, বা match-3/puzzle গেমে connected একই-রঙা গুচ্ছ চিহ্নিত করা।
• Terrain / GIS labeling: একটা মানচিত্রে একই ধরনের ভূমি (পানি, বন) connected অঞ্চল হিসেবে রং করা।

মূল সুর: "একটা শুরু-বিন্দু থেকে connected একই-ধরনের region ছড়াও/রং করো" — grid-কে implicit graph ধরে DFS/BFS, আর cell mutate করাই visited-mark। এর উপরেই islands, area, reverse-flood দাঁড়ায়।

---

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