কনটেন্টে যান

009 — Rotting Oranges

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

Problem link ও উৎস

  • Original source: Classic capstone interview problem (multi-source BFS)
  • Platform: LeetCode — https://leetcode.com/problems/rotting-oranges/
  • Topic: graphs (BFS) + grid indexing
  • Difficulty: Medium
  • Pattern: Multi-source BFS, counting levels (minutes)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 09 graphs (BFS দিয়ে level-by-level ছড়ানো, যেখানে একসাথে অনেক উৎস থেকে শুরু — multi-source) আর 02 grid indexing (grid-এর cell গুলোকে (r, c) দিয়ে ধরা, চার প্রতিবেশীতে যাওয়া)। দুই tool জোড়া লাগলেই এই problem।

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

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

তোমাকে একটা grid দেওয়া, যেখানে প্রতিটা ঘর — 0 (ফাঁকা), 1 (তাজা কমলা), বা 2 (পচা কমলা)। প্রতি মিনিটে, প্রতিটা পচা কমলা তার পাশের (উপর-নিচ-বাঁ-ডান) তাজা কমলাগুলোকেও পচিয়ে দেয়। প্রশ্ন: সব তাজা কমলা পচতে সর্বনিম্ন কত মিনিট লাগবে? যদি কখনো কোনো তাজা কমলা পচানো অসম্ভব হয় (চারপাশে কেউ নেই), তাহলে -1 ফেরত দাও।

উদাহরণ
minute 0       minute 1       minute 2       minute 3       minute 4
2 1 1          2 2 1          2 2 2          2 2 2          2 2 2
1 1 0    ->    2 1 0    ->    2 2 0    ->    2 2 0    ->    2 2 0
0 1 1          0 1 1          0 1 1          0 2 1          0 2 2
fresh=6        fresh=4        fresh=2        fresh=1        fresh=0
সব তাজা কমলা পচতে 4 মিনিট।

Input ও output

উদাহরণ
Input :
2 1 1
1 1 0
0 1 1
Output: 4

Edge case 1 (পৌঁছানো অসম্ভব):
2 1 1
0 1 1
1 0 1            -> Output: -1   # নিচ-বাঁয়ের তাজা কমলা বিচ্ছিন্ন
Edge case 2 (কোনো তাজা নেই): [[0,2]] -> Output: 0   # পচানোর কিছু নেই
Edge case 3 (শুধু ফাঁকা/পচা): [[0,0]] -> Output: 0

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

ভাবো একটা মাঠে কয়েক জায়গায় একসাথে আগুন লাগল (multi-source)। প্রতি মিনিটে আগুন তার ঠিক পাশের ঘাসে ছড়ায়। তুমি জানতে চাও পুরো মাঠ পুড়তে কত মিনিট লাগবে। সব আগুন একসাথে সমান গতিতে বাড়ে — তাই তুমি "এই মিনিটের আগুনের সীমানা" পুরোটা ছড়ানোর পর ঘড়িতে এক মিনিট যোগ করো, তারপর পরের সীমানা। কোথাও ঘাস থেকে গেলে যেখানে আগুন পৌঁছায় না — সেটাই -1।

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

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

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 09 graphs থেকে: BFS — যেটা level-by-level ছড়ায়, তাই "কত ধাপ/মিনিট লাগল" সরাসরি গোনা যায়। এখানে মোচড়: একটা উৎস না, অনেক পচা কমলা একসাথে উৎস (multi-source BFS)।
  • 02 grid indexing থেকে: cell গুলোকে (r, c) দিয়ে ধরা আর চার দিকে ((r±1,c), (r,c±1)) যাওয়ার সূত্র।

একা BFS দেয় shortest-time framing; একা grid-indexing দেয় প্রতিবেশীতে যাওয়ার কৌশল। দুটো মিললে minutes গোনা সহজ।

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

লুকানো logic: BFS-এর প্রতিটা level হলো এক মিনিট। শুরুতে সব পচা কমলা একসাথে queue-তে (level 0)। প্রতিটা level পুরো process করা মানে এক মিনিট কেটে যাওয়া, আর সেই মিনিটে যেসব তাজা কমলা পচল তারা পরের level। যেহেতু BFS সবচেয়ে ছোট দূরত্ব দেয়, প্রতিটা তাজা কমলা ঠিক যত মিনিটে পচা সম্ভব ততটাতেই পচে — তাই শেষ level-এর সংখ্যা = সর্বনিম্ন মিনিট।

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

একটা queue (Python-এ collections.deque) — BFS-এর হৃদয়, FIFO ক্রমে cell বের করে। সাথে একটা fresh counter (কত তাজা কমলা বাকি) আর minutes counter। grid নিজেই visited চিহ্ন রাখে (পচালে 2 করে দিই)।

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

আমরা চাই সব উৎস থেকে একই গতিতে, level ধরে ধরে ছড়াতে — যাতে minute-এর হিসাব নিখুঁত থাকে। queue (FIFO) ঠিক এটাই দেয়: যা আগে ঢুকেছে আগে বের হয়, তাই কাছের cell আগে process হয়। DFS/stack এখানে কাজ করবে না, কারণ সেটা গভীরে চলে যায়, level ভেঙে ফেলে — minute-গণনা গোলমাল হতো। এজন্যই BFS-queue (09) + grid-indexing (02) এখানে নিখুঁত।

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

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

প্রথম সরল চিন্তা: simulation — বারবার পুরো grid scan করো; প্রতি pass-এ যত পচা কমলা আছে তাদের তাজা প্রতিবেশীদের পচাও, এক মিনিট যোগ করো; যতক্ষণ কোনো নতুন কমলা পচছে চালিয়ে যাও।

উদাহরণ
minute = 0
while কোনো নতুন পচা হচ্ছে:
    এই মুহূর্তের সব পচা কমলা খুঁজে তাদের প্রতিবেশী পচাও (পরের pass-এর জন্য চিহ্নিত করো)
    minute += 1
শেষে fresh বাকি থাকলে -1

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

প্রতি মিনিটে পুরো grid আবার scan করা মানে worst case O((rows·cols)^2) — কারণ মিনিট সংখ্যা grid-আকারের সমান হতে পারে, আর প্রতি মিনিটে পুরো grid দেখা হয়। BFS-queue সেই অপচয় মুছে দেয়: প্রতিটা cell ঠিক একবার queue-তে ঢোকে-বেরোয়, তাই মোট O(rows·cols)।

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

মূল observation: সব পচা কমলা একসাথে সমান গতিতে ছড়ায়, তাই এটা multi-source BFS — শুরুতেই সব পচা কমলা queue-তে দিয়ে দাও। তখন BFS-এর প্রতিটা সম্পূর্ণ level = এক মিনিট, আর শেষ level-এর সংখ্যাই উত্তর। এই এক চিন্তাই simulation-এর পুনরাবৃত্তি মুছে দেয়।

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

শুরুতে grid scan করে সব পচা কমলা queue-তে ঢালো, আর তাজা কমলা গুনে রাখো (fresh)। তারপর level-by-level BFS: প্রতি level-এ queue-র বর্তমান সব cell বের করে তাদের তাজা প্রতিবেশীদের পচাও (queue-তে যোগ করো, fresh কমাও)। একটা level-এ যদি অন্তত একটা নতুন পচা হয়, minutes এক বাড়াও। শেষে fresh == 0 হলে minutes, নাহলে -1।

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

মোচড়: "একটা উৎস থেকে BFS" ভাবার বদলে ভাবো "সব উৎস একসাথে queue-তে ঢুকিয়ে দিই — তখন level মানেই মিনিট।" multi-source-এর এই চালেই simulation একটা পরিষ্কার BFS-এ গলে যায়।

ছবিতে বোঝা

2 1 1 / 1 1 0 / 0 1 1 — minute ধরে ধরে (* = এইমাত্র পচল):

উদাহরণ
minute 0 queue: [(0,0)]      grid: 2 1 1 / 1 1 0 / 0 1 1   fresh=6
--- minute 1 process করে ---
(0,0) থেকে: (0,1),(1,0) পচল   grid: 2 2* 1 / 2* 1 0 / 0 1 1  fresh=4
--- minute 2 ---
(0,1)->(0,2); (1,0)->(1,1)    grid: 2 2 2* / 2 2* 0 / 0 1 1  fresh=2
--- minute 3 ---
(1,1)->(2,1)                   grid: 2 2 2 / 2 2 0 / 0 2* 1  fresh=1
--- minute 4 ---
(2,1)->(2,2)                   grid: 2 2 2 / 2 2 0 / 0 2 2*            fresh=0
fresh=0 -> উত্তর = 4 মিনিট

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

Input [[2,1],[0,1]]:

  1. scan: পচা (0,0) queue-তে; fresh = 2 ((0,1), (1,1)); minutes = 0
  2. level 1: (0,0) বের → প্রতিবেশী (0,1) তাজা → পচাও, queue-তে; (1,0) ফাঁকা; fresh = 1; এই level-এ পচা হয়েছে → minutes = 1
  3. level 2: (0,1) বের → প্রতিবেশী (1,1) তাজা → পচাও, queue-তে; fresh = 0; minutes = 2
  4. level 3: (1,1) বের → কোনো তাজা প্রতিবেশী নেই → নতুন পচা নেই, minutes বাড়ে না
  5. fresh == 0 → return minutes = 2

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

Python

Python
from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # শুরুর সব পচা কমলা = BFS-এর উৎস; তাজা গুনে রাখো
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1

    if fresh == 0:
        return 0                       # পচানোর কিছুই নেই

    minutes = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while queue and fresh > 0:
        minutes += 1                   # একটা নতুন মিনিট শুরু
        for _ in range(len(queue)):    # ঠিক এই level-এর cell গুলো
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2   # পচাও
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

# ---- tests ----
assert oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) == 4
assert oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]) == -1   # বিচ্ছিন্ন তাজা
assert oranges_rotting([[0,2]]) == 0                      # কোনো তাজা নেই
assert oranges_rotting([[1]]) == -1                       # একা তাজা, উৎস নেই
assert oranges_rotting([[2,2],[1,1]]) == 1               # এক মিনিটেই সব
print("সব test pass!")

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

  • প্রথম double loop — grid scan করে সব পচা cell queue-তে (multi-source উৎস), তাজা সংখ্যা fresh-এ।
  • if fresh == 0: return 0 — শুরুতেই কোনো তাজা কমলা না থাকলে 0 মিনিট।
  • directions — চার প্রতিবেশীর offset (02 grid indexing)।
  • while queue and fresh > 0 — যতক্ষণ ছড়ানোর জায়গা আর বাকি তাজা আছে।
  • minutes += 1 — এই level শুরু = এক মিনিট।
  • for _ in range(len(queue)) — এই মুহূর্তের level-এর ঠিক যতগুলো cell, ততবার — এটাই level আলাদা রাখে।
  • popleft() — FIFO, BFS-এর queue।
  • boundary + == 1 চেক — সীমার ভেতরে আর তাজা হলেই পচাও, fresh কমাও, queue-তে দাও।
  • return minutes if fresh == 0 else -1 — সব পচলে minutes, নাহলে পৌঁছানো গেল না → -1।

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

[[2,1,1],[1,1,0],[0,1,1]]-এ একটামাত্র উৎস (0,0) থেকে ছড়িয়ে level গুনতে গুনতে minute 1,2,3,4-এ সব তাজা কমলা পচে, fresh 0 হয় → return 4 — assert pass। বিচ্ছিন্ন তাজা থাকলে শেষে fresh > 0, return -1; কোনো তাজা না থাকলে 0; একা তাজা কমলায় উৎস নেই, return -1। শেষে print: সব test pass!।

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

সময়

O(rows · cols) — scan একবার, আর প্রতিটা cell queue-তে সর্বোচ্চ একবার ঢোকে-বেরোয়।

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

O(rows · cols) — worst case queue-তে অনেক cell একসাথে থাকতে পারে।

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

  • শুরুর সব পচা কমলা একসাথে queue-তে না দেওয়া — multi-source না হলে minute-হিসাব ভুল হয়।
  • level আলাদা না করা (for _ in range(len(queue)) বাদ) — তখন এক মিনিটে কত cell process হলো গুলিয়ে যায়, minute ভুল।
  • শেষে অবশিষ্ট fresh চেক না করা — বিচ্ছিন্ন কমলার জন্য -1 ফেরত দিতে ভুলে যাওয়া।
  • শুরুতে fresh == 0 case বাদ — তখন অযথা minutes বেড়ে ভুল উত্তর (0-র বদলে) আসতে পারে।

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

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

ভিত্তি: graph-এ BFS / shortest-path-by-levels (09 graphs, ../../09-graphs/) + grid-এ (r,c) indexing ও 4-direction move (02 arrays/grid, ../../02-arrays-and-strings/)। একক-উৎস BFS-এর সরাসরি সম্প্রসারণ — শুধু শুরুতে একাধিক উৎস।

পরের অনুশীলন

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

Multi-source BFS by levels: সব উৎস একসাথে queue-তে দিয়ে, প্রতিটা সম্পূর্ণ level-কে এক "ধাপ/মিনিট" ধরে ছড়ানো — "একসাথে অনেক জায়গা থেকে সমান গতিতে ছড়ানো, কত ধাপ লাগল" — এই ধরনের problem-এর canonical চাল।

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

ভবিষ্যতের আমাকে: "একসাথে অনেক জায়গা থেকে ছড়ায়, সর্বনিম্ন সময়/ধাপ" শুনলেই multi-source BFS মনে করবে। মূল চাল — শুরুতেই সব উৎস queue-তে ঢালো, আর for _ in range(len(queue)) দিয়ে level আলাদা রেখে ধাপ গোনো। শেষে অবশিষ্ট target চেক করে "পৌঁছানো গেল না → -1" বলতে ভুলো না।

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