009 — 01 Matrix¶

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

Problem link ও উৎস

Original source: Classic multi-source BFS distance exercise
Platform: LeetCode — https://leetcode.com/problems/01-matrix/
Topic: graphs
Difficulty: Medium
Pattern: multi-source BFS on a grid (distance to the nearest target)
Basic idea inherited from: Rotting Oranges (এই tracker-এর #8, 008-rotting-oranges.md); multi-source BFS (../bfs.md)

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

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

তোমাকে একটা m x n binary matrix mat দেওয়া আছে — প্রতিটা cell হয় 0 নয় 1। প্রতিটা cell-এর জন্য বের করো তার সবচেয়ে কাছের 0-এর দূরত্ব কত, যেখানে দূরত্ব মাপা হয় চার দিকের (উপর-নিচ-বাম-ডান) পদক্ষেপে। উত্তর হিসেবে একই আকারের একটা matrix ফেরত দাও, যেখানে প্রতিটা ঘরে সেই দূরত্ব লেখা। (0-cell গুলোর দূরত্ব অবশ্যই 0।)

উদাহরণ

mat:              উত্তর (প্রতিটা cell -> nearest 0-এর দূরত্ব):
  0 0 0             0 0 0
  0 1 0             0 1 0
  1 1 1             1 2 1

Input ও output¶

উদাহরণ

Input : mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Input : mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Edge case (একটাই 0, বাকি সব 1): mat = [[1,1],[1,0]] -> [[2,1],[1,0]]

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

একটা মাঠে কয়েকটা পানির কল (0) ছড়িয়ে আছে, বাকি জায়গা শুকনো (1)। প্রতিটা শুকনো জায়গা থেকে সবচেয়ে কাছের কলে যেতে কত পা লাগে জানতে চাও। প্রতিটা শুকনো জায়গায় দাঁড়িয়ে কল খুঁজতে বেরোনোর বদলে উল্টোটা করো: সব কল থেকে একসাথে পানি ছড়াতে দাও। যে জায়গায় পানি যত মিনিটে পৌঁছাল, সেটাই সেই জায়গার nearest কলের দূরত্ব — কারণ সবচেয়ে কাছের কলের ঢেউই আগে পৌঁছায়।

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

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

মূল ভিত হলো multi-source BFS (#8 Rotting Oranges)। ওখানে সব পচা কমলা একসাথে seed করে ঢেউ ছড়িয়েছিলাম; এখানে সব 0-cell একসাথে seed করব (দূরত্ব 0), আর ঢেউ ছড়িয়ে প্রতিটা 1-cell-কে দেবে তার nearest 0 পর্যন্ত দূরত্ব। হুবহু একই trick — শুধু "source" এবার পচা কমলা নয়, প্রতিটা 0। BFS-এর first-arrival = shortest থিওরেমই নিশ্চিত করে প্রথম যে ঢেউ কোনো cell-কে ছোঁয়, সেটাই nearest।

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

লুকানো logic: "প্রতিটা cell-এর nearest source পর্যন্ত দূরত্ব" = সব source একসাথে seed করা multi-source BFS। ভুল পথ হবে প্রতিটা 1-cell থেকে আলাদা করে nearest 0 খোঁজা — তাতে বহুবার BFS, খরচ বিশাল। সঠিক উল্টো চিন্তা: 0-গুলো থেকে BFS শুরু করো; সব 0 queue-তে distance 0-তে; BFS layer ছড়ালে প্রতিটা 1-cell প্রথমবার যে layer-এ ছোঁয়া হয়, সেটাই তার nearest 0-এর দূরত্ব (first-arrival = shortest, কারণ সব edge cost সমান)।

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

Grid নিজেই — implicit graph; neighbor চার দিকের cell।
collections.deque — BFS frontier; multi-source বলে শুরুতেই সব 0-cell ঢোকে।
distance matrix (dist) — উত্তর; একই সাথে visited-marker (যে cell-এর dist এখনো set হয়নি, সে unvisited)।

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

Grid-কে graph ধরা fit করে কারণ neighbor চার দিকেই fixed আর দূরত্ব মাপা step গোনা। deque fit করে কারণ BFS-এর FIFO-ই first-arrival = shortest নিশ্চিত করে; heap লাগে না, কারণ সব edge-এর cost সমান (1)। dist matrix double-duty করে — উত্তর জমা রাখে আর dist[nr][nc] == -1 (বা সেট-হয়নি) দিয়ে visited চেক করে, আলাদা visited set বাঁচায়।

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

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা 1-cell-এর জন্য আলাদা করে nearest 0 খোঁজা — যেমন প্রতিটা 1-cell থেকে একটা পুরো BFS চালিয়ে প্রথম 0-তে পৌঁছানো পর্যন্ত দূরত্ব মাপা, বা প্রতিটা 1-cell থেকে প্রতিটা 0-cell-এর Manhattan distance তুলনা করে minimum নেওয়া।

উদাহরণ

1) প্রতিটা cell (r,c) যেটা 1:
2)   (r,c) থেকে BFS চালিয়ে nearest 0-এর দূরত্ব মাপো
3)   সেই দূরত্ব dist[r][c]-এ লেখো

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা 1-cell থেকে আলাদা BFS মানে O(m·n) cell-এর প্রত্যেকটার জন্য O(m·n) কাজ — মোট O((m·n)^2), বড় matrix-এ অসহনীয়। সব 0-cell-এর সাথে দূরত্ব তুলনা করলেও একই রকম খারাপ। অথচ একটাই multi-source BFS — সব 0 একসাথে seed করে — প্রতিটা cell ঠিক একবার ছোঁয়, মোট O(m·n)। মূল ভুল: দিক উল্টো; 1 থেকে 0 না খুঁজে 0 থেকে ঢেউ ছড়াও।

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

মূল observation: BFS-টা উল্টো দিকে চালাও — 0-গুলো থেকে, 1-গুলো থেকে নয়। সব 0 একসাথে distance 0-তে seed করলে এক BFS-ই প্রতিটা 1-cell-কে তার nearest 0-এর দূরত্ব দিয়ে দেয়, কারণ সবচেয়ে কাছের source-এর ঢেউ আগে পৌঁছায় (first-arrival = shortest)।

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

dist matrix বানাও — সব 0-cell-এ 0, বাকি সব -1 (অসেট/unvisited)। সব 0-cell queue-তে ঢোকাও। তারপর সাধারণ BFS: front pop করো, প্রতিটা প্রতিবেশী যার dist == -1, তাকে dist[cur] + 1 দাও আর enqueue করো। queue খালি হলে dist-ই উত্তর। প্রতিটা cell একবার set হয় (first arrival), একবার pop হয় — O(m·n)।

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

মোচড়: "প্রতিটা 1 থেকে nearest 0 খুঁজব" না ভেবে দিকটা উল্টে দাও — "সব 0 থেকে একসাথে ঢেউ ছড়াই, প্রতিটা 1 প্রথম যে ঢেউ ছোঁয় সেটাই তার উত্তর।" বহু BFS থেকে নেমে এসো একটাই reverse multi-source BFS-এ। কোন দিক থেকে শুরু করছ — সেটাই এই problem-এর আসল মোচড়।

ছবিতে বোঝা¶

mat = [[0,0,0],[0,1,0],[1,1,1]] দিয়ে ঢেউ ছড়ানো (. = এখনো অসেট):

উদাহরণ

seed (সব 0, distance 0):     ঢেউ layer 1:           ঢেউ layer 2:
  0 0 0                        0 0 0                  0 0 0
  0 . 0                        0 1 0                  0 1 0
  . . .                        1 . 1                  1 2 1

(1,1) layer 1-এ ছোঁয়া (উপরের/পাশের 0 থেকে)।
(2,1) layer 2-এ ছোঁয়া (তার আগে layer 1-এর 1-cell গুলো থেকে)।
উত্তর = শেষ grid

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

mat = [[1,1],[1,0]]:

dist = [[-1,-1],[-1,0]]। queue = [(1,1)] (একমাত্র 0)।
pop (1,1) → প্রতিবেশী (0,1) (dist -1) → dist[0][1] = 1, enqueue; (1,0) (dist -1) → dist[1][0] = 1, enqueue।
pop (0,1) → প্রতিবেশী (0,0) (dist -1) → dist[0][0] = 2, enqueue; (1,1) already 0।
pop (1,0) → প্রতিবেশী (0,0) already 2 (set), (1,1) already 0। নতুন কিছু না।
pop (0,0) → প্রতিবেশী সব set। queue খালি।
return dist = [[2,1],[1,0]]।

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

Python¶

Python

from collections import deque


def update_matrix(mat):
    R, C = len(mat), len(mat[0])
    dist = [[-1] * C for _ in range(R)]   # -1 মানে এখনো অসেট (unvisited)
    q = deque()
    # multi-source seeding: সব 0-cell distance 0-তে
    for r in range(R):
        for c in range(C):
            if mat[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))

    while q:
        r, c = q.popleft()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if (0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1):
                dist[nr][nc] = dist[r][c] + 1   # first arrival = nearest 0
                q.append((nr, nc))              # mark করার সময়ই enqueue
    return dist


# ---- tests ----
m1 = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
m2 = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
m3 = [[1, 1], [1, 0]]
m4 = [[0, 1, 1, 0]]

assert update_matrix(m1) == [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
assert update_matrix(m2) == [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
assert update_matrix(m3) == [[2, 1], [1, 0]]
assert update_matrix(m4) == [[0, 1, 1, 0]]
print("সব test pass!")

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

dist = [[-1] * C ...] — -1 দ্বৈত কাজ করে: উত্তরের placeholder আর "এখনো visit হয়নি" চিহ্ন।
প্রথম double loop — সব 0-cell-কে dist = 0 দিয়ে queue-তে (multi-source seeding)।
q.popleft() — deque-এর O(1) front pop; FIFO-ই first-arrival = shortest নিশ্চিত করে।
if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] == -1 — bounds আগে, তারপর শুধু অসেট প্রতিবেশী।
dist[nr][nc] = dist[r][c] + 1 — current cell-এর দূরত্ব + 1; প্রথম যে ঢেউ ছোঁয় সেটাই nearest।
enqueue ঠিক set করার পাশে — mark-on-push, যাতে একই cell queue-তে বারবার না ঢোকে।

Output মিলিয়ে দেখা¶

update_matrix(m2): সব 0 seed হয়; ঢেউ ছড়িয়ে (1,1) পায় 1, (2,0) ও (2,2) পায় 1, আর (2,1) পায় 2 → [[0,0,0],[0,1,0],[1,2,1]]। m3-এ একমাত্র 0 থেকে ছড়িয়ে [[2,1],[1,0]]। m1 সব 0/একা-1 → অপরিবর্তিত। সব assert pass, শেষে print: সব test pass!।

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

সময়¶

O(m · n) — initial scan সব cell একবার; BFS-এ প্রতিটা cell ঠিক একবার set ও একবার pop হয়, প্রতিটা প্রতিবেশী constant-বার দেখা হয়।

অতিরিক্ত জায়গা¶

O(m · n) — dist matrix O(m·n), আর queue worst case একটা পুরো level (গ্রিড-আকারের) ধরে রাখতে পারে।

যে ভুলগুলো এড়াতে হবে¶

দিক উল্টো ধরা — 1 থেকে 0 খোঁজা; এতে multi-source-এর সুবিধাই হারায়, খরচ ফুলে যায়। সবসময় 0 থেকে ছড়াও।
0-cell গুলোকে আলাদা আলাদা seed না করে একটাই super-source ভেবে গোলমাল করা — সবগুলোকে distance 0-তে queue-তে ঢোকাও।
visited চেক বাদ দিয়ে already-set cell আবার আপডেট করা — dist == -1 শর্তই প্রথম (nearest) মান রক্ষা করে।
list.pop(0) ব্যবহার করা — প্রতি pop O(n), BFS quadratic; deque নাও।

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

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

ভিত্তি: multi-source BFS (#8 Rotting Oranges) আর BFS distance theorem (../bfs.md)। Rotting Oranges-এ উত্তর ছিল level সংখ্যা; এখানে উত্তর প্রতিটা cell-এর দূরত্ব — তাই সময় না গুনে cell-এ distance store করি। মূল নতুন শিক্ষা: কখনো BFS-এর দিক উল্টো চালাতে হয় (target থেকে, source থেকে নয়) — এটাই multi-source-এর সবচেয়ে শক্তিশালী চিন্তা।

পরের অনুশীলন¶

Rotting Oranges (multi-source, level = সময়) — https://leetcode.com/problems/rotting-oranges/ (এই tracker-এর #8)
Walls and Gates (প্রতিটা ঘর থেকে nearest gate) — https://leetcode.com/problems/walls-and-gates/
Map of Highest Peak (multi-source BFS height assignment) — https://leetcode.com/problems/map-of-highest-peak/

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

Multi-source BFS for nearest-target distance: "প্রতিটা cell থেকে nearest X-এর দূরত্ব" = সব X একসাথে seed করে BFS, আর distance cell-এ store করো। চাবি হলো দিক উল্টো ধরা — target থেকে ছড়াও, প্রতিটা cell থেকে আলাদা খুঁজো না। সব edge cost সমান বলে heap লাগে না, খরচ O(m·n)।

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

ভবিষ্যতের আমাকে: "01 Matrix = reverse multi-source BFS; সব 0 একসাথে seed করো, প্রতিটা 1 প্রথম যে ঢেউ ছোঁয় সেটাই উত্তর।" যখনই 'nearest X পর্যন্ত দূরত্ব প্রতিটা cell-এ' দেখবে — দিক উল্টে target থেকে ঢেউ ছড়াও; বহু BFS-এর ফাঁদ এড়িয়ে একটাই multi-source BFS চালাও।

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