Graphs على Gridimplicit graph · DIRS · flood fill · islands · multi-source BFS · shortest path in a grid

أغلب مسائل الـ graphs في الاختبارات مش هتديك nodes و edges. هتديك matrix: خريطة أرض ومية، متاهة، صورة، قفص برتقان. كل خانة node، والخانات اللازقة في بعض بينهم edge. نفس الـ BFS و DFS بالظبط، بس الـ neighbors بتحسبهم on the fly.

هتطلع من الفصل ده وإنت عارف

  • تشوف الـ graph المستخبي في أي grid، وتجيب الـ neighbors بـ DIRS و bounds check من غير off-by-one (>= مش >).
  • تختار بين 4 و 8 directions، وتعرف تعلّم الـ visited فين، وليه fill(new Array(m)) فخ.
  • تكتب قالب الـ BFS وقالب الـ DFS على grid، وتعرف إمتى كل واحد.
  • تحل 8 مسائل مشهورة بترتيب، كل واحدة بتضيف فكرة واحدة: من Flood Fill لحد Pacific Atlantic.
  • تفهم الـ multi-source BFS ولوب الـ levelSize، وفكرة "ابدأ من الحافة".

ليه الـ grid محتاجة فصل لوحدها؟

في الفصل اللي فات عملنا BFS و DFS على graph عادي: nodes مترقّمة و edges في list، وبنينا منها adjacency list. دلوقتي هنشوف النوع اللي بيتسأل أكتر بكتير، اللي شكله كده:

مفيش كلمة graph، بس هو موجود: كل خانة node، وكل خانتين لازقين (فوق/تحت/شمال/يمين) بينهم edge. والجزيرة؟ مجموعة خانات أرض متوصلة، يعني connected component، نفس اللي عدّيناه في الفصل اللي فات.

تشبيه أرضية مطبخ بلاط. لو دلقت كوباية مية على بلاطة، المية بتروح للبلاط اللازق فيها من الأربع نواحي، وبعدين للي لازق في دول. البلاطة node واللزق edge. ولو فيه دولاب، المية بتلف حواليه.

بص الـ BFS وهو بيتنشر من خانة في النص زي المية بالظبط، layer by layer. الرقم = أقل عدد خطوات من البداية، والخانات الغامقة حيطان:

ده نفس الـ BFS بالحرف. الفرق الوحيد إن بدل adj[u]، بتحسب الـ neighbors بنفسك وتتأكد إنهم جوه الـ grid. والفرق الصغير ده هو كل الفصل.

طب إزاي تعرف من كلام المسألة إنها grid graph، وأنهي نوع فيهم؟

إزاي تعرفه من المسألة

لما تشوف: grid / matrix / board / mapislandconnected cells4-directionally 8-directionally / diagonalfill / paint / colorspreads every minutemaze minimum stepsnearest 0 / nearest exitsurroundedborder / edge of the board
ومش هو غالبًا لو: only move right or down + min/max sumeach cell has a cost and you minimize total costsorted rows and columns + search

لو الحركة يمين وتحت بس والمطلوب أقل مجموع، ده DP على grid. لو كل خانة ليها cost مختلف، ده Dijkstra في الفصل الجاي. ولو الصفوف والأعمدة مترتبة، ده binary search.

النمطبتبدأ منينالأداةمسائل الفصل
مناطق
regions
كل خانة لسه ما اتزارتشDFS أو BFSFlood Fill، Number of Islands، Max Area
أقصر طريق
single-source BFS
الـ startBFS + distShortest Path in Binary Matrix
كذا مصدر
multi-source BFS
كل المصادر مع بعضBFS + levelSize أو distRotting Oranges، 01 Matrix
من الحافة
reverse from the border
خانات الحافةBFS بالعكسSurrounded Regions، Pacific Atlantic
flowchart TD
  A["Grid problem"] --> B{"Count, size or fill connected regions?"}
  B -- yes --> R["DFS or BFS from every unvisited cell"]
  B -- no --> C{"Minimum steps or minutes?"}
  C -- one start --> S["BFS from the start with dist"]
  C -- many starts --> M["Multi-source BFS: push all sources first"]
  C -- no --> D{"Depends on reaching the border?"}
  D -- yes --> E["Reverse: start from the border cells"]
  D -- no --> F["Maybe DP (right/down only) or Dijkstra (costs)"]
  

اسأل نفسك الأسئلة دي بالترتيب.

كل الأنماط دي محتاجة حاجة واحدة الأول: إزاي تجيب جيران خانة من غير ما تخرج برا الـ grid؟

الـ grid هي graph، من غير ما تبنيه

كل خانة عنوانها (r, c): r رقم الصف (من فوق لتحت) و c رقم العمود (من الشمال لليمين). في الكود grid[r][c]: الصف الأول وبعدين العمود.

في الـ graphفي الـ grid
nodeخانة (r, c)
edgeخانتين لازقين، ومسموح تعدّي بينهم (مش حيطة ولا مية)
adj[u]بتتحسب on the fly: فوق وتحت وشمال ويمين
V و EV = rows × cols، و E حوالي 2V، فـ O(V + E) = O(rows × cols)

تقدر تبني adjacency list بجد لو حبيت: كل خانة تاخد رقم واحد id = r * cols + c (يعني (1, 2) في grid عرضها 5 تبقى 7)، والرجوع r = Math.floor(id / cols) و c = id % cols. بس ده memory على الفاضي. الـ trick نفسه هتحتاجه في Union-Find، والـ neighbors بنجيبهم on the fly كده:

  1. كل pair هو [dr, dc]: هتزوّد كام على الصف وكام على العمود. فوق = الصف اللي قبله، فـ dr = -1. بدل 4 if شبه بعض، loop واحدة.
  2. rows = عدد الصفوف = grid.length، و cols = طول أول صف. لو الـ grid فاضية grid[0] هتبقى undefined، فاعمل early return لو مش مضمونة.
  3. الجار المحتمل. لسه ما نعرفش هو موجود ولا لأ.
  4. الـ bounds check. الصفوف من 0 لـ rows - 1، فـ nr === rows نفسه برا. عشان كده >= مش >، نفس غلطة i <= n.
  5. والـ check ده لازم ييجي قبل أي grid[nr][nc]. الـ || بيقف عند أول true، فعمرنا ما هنقرا grid[-1].
  6. خانة في النص ليها 4 neighbors، على الحافة 3، وفي الركن 2.

الـ animation دي بترسم الـ grid جوه برواز وهمي (الخانات الباهتة) عشان تشوف اللي برا. خانة في النص، وبعدين الركنين:

grid فيها 4 صفوف، وكتبت nr > rows بدل nr >= rows. إيه اللي هيحصل مع الخانة (3, 4)؟

  • ولا حاجة، الشرطين واحد
  • "تحت" هتدّي nr = 4، و 4 > 4 false، فهيقرا grid[4] اللي هي undefined ويضرب TypeError
  • هيرجّع جار زيادة من غير error
  • الـ loop مش هتخلص

آخر صف رقمه rows - 1. ولو الغلطة في الأعمدة (nc > cols) الموضوع أسوأ: grid[r][5] بترجع undefined من غير error، والكود يكمّل غلط في صمت.

كده عندنا 4 neighbors. طب لو المسألة بتعدّ القطري كمان؟

4 اتجاهات ولا 8؟

المسألة بتقولها في جملة واحدة: "4-directionally" أو "horizontally or vertically" يبقى 4، و "8-directionally" أو "including diagonals" يبقى 8. لو مش واضح، اسأل.

وفيه ناس بتكتبها بـ loopين: for (let dr = -1; dr <= 1; dr++) ونفسها لـ dc، وتعمل skip لـ (0, 0) لأنها الخانة نفسها. هنا الصح <= لأن الـ 1 مسموح. الـ rule of thumb: الرقم اللي في الشرط مسموح؟ يبقى <=. مش مسموح (زي rows)؟ يبقى <.

جبنا الـ neighbors. بس من غير ما نعلّم اللي زرناه، هنلف في دواير للأبد. نعلّم فين؟

الـ visited: في نفس الـ grid ولا في matrix لوحدها؟

زي ما شفت في الفصل اللي فات، من غير visited الخانة A بتحط B في الـ queue، و B بتحط A تاني، وهكذا. في الـ grid كل خانتين جيران بيشوفوا بعض، فده بيحصل على طول. عندك اختيارات:

الطريقةالكودالميزةالعيب
عدّل الـ grid نفسهاgrid[r][c] = '0'zero extra memoryبتبوّظ الـ input
matrix لوحدهاseen[r][c] = trueالـ input سليمO(rows × cols) memory
Set من stringsseen.add(r + ',' + c)مش محتاج تعرف الحجمأبطأ: string + hash كل خطوة
الـ dist نفسهاdist[r][c] === -1matrix واحدة لشغلانتينلما تكون محتاج distance أصلًا
في الانترفيو قبل ما تعدّل الـ grid قول: "هعلّم الـ visited in-place عشان أوفّر memory، ينفع أعدّل الـ input؟". السؤال ده لوحده بيبيّن إنك فاهم الـ tradeoff.

فخ JavaScript: matrix بـ fill

أول حاجة بتيجي في دماغك عشان تعمل seen: تعمل صف واحد، وتعمل بيه fill للصفوف كلها (السطر 1 تحت). الـ fill بيحط نفس الـ reference في كل الصفوف، فكلهم array واحدة. شوف الكود ده وهو شغال بجد:

الـ callback بتاع Array.from بيتنادي مرة لكل صف، فكل مرة array جديدة. و fill(false) جوه الصف تمام، لأن false primitive مش object.

عندنا neighbors و visited. نجمعهم في الـ BFS template اللي هنستخدمه في كل الفصل.

قالب الـ BFS على grid

ده نفس قالب الفصل اللي فات، ومتغيّر فيه 3 حاجات بس: الـ queue فيها [r, c] بدل رقم، و adj[u] بقت loop على DIRS + bounds check + wall check، و visited بقت dist[nr][nc] !== -1.

المسألة: متاهة فيها '.' فاضي و '#' حيطة. طلّع أقل عدد خطوات من (sr, sc) لكل خانة، و -1 للي مش ممكن توصله.

  1. dist شغالة distance و visited مع بعض. ليه -1 مش 0؟ لأن 0 distance حقيقية (البداية نفسها)، فمش هتفرّق بين "لسه" و "دي البداية".
  2. Mark on push: البداية بتتعلّم في نفس لحظة ما تدخل الـ queue. كده أي خانة عمرها ما تدخل الـ queue مرتين.
  3. ليه head مش queue.shift()؟ الـ shift() بيزق كل العناصر خانة لقدام، يعني O(n) كل مرة. الـ head مجرد index لأول عنصر لسه ما اتعالجش.
  4. queue[head++]: postfix، ياخد queue[head] وبعدين يزوّد. لو كتبت ++head هتنط على عنصر.
  5. الـ bounds check الأول، قبل أي سطر بيقرا grid[nr][nc].
  6. ده السطر اللي بيتغير من مسألة للتانية: حيطة، مية، "أوطى مني"، "مش برتقانة سليمة".
  7. اتشافت قبل كده، يعني عندها distance أصغر أو قد اللي هنديهالها، لأن الـ BFS ماشي layer by layer.
  8. distance الجار = distance اللي جه منها + 1، وفي نفس السطر بقت visited.
  9. أي خانة لسه -1 يا حيطة، يا مقفول عليها.

شوفه على متاهة 4 × 5 من (0,0). الـ queue تحت فيها كل اللي اتحط فيها، والباهت هو اللي قبل head، يعني اتعالج خلاص:

لاحظ (0,3): لو عدّيت الحيطة هي على بعد 3، بس الـ BFS لقاها على بعد 7 لأنه لف من تحت. وده الصح.

Complexity: كل خانة بتدخل الـ queue مرة واحدة بالكتير (بفضل الـ mark on push)، وكل خانة بتبص على 4 neighbors. يعني O(rows × cols) time و memory.

والـ DFS على grid؟

نفس الفكرة بـ recursion: ادخل الخانة، علّمها، وادخل في كل جار. ده الـ template اللي هتستخدمه في الـ regions:

هنا الـ bounds check بقى base case جوه الدالة: بننادي على الجار من غير ما نتأكد، والنداء نفسه بيعمل early return. والعلامة قبل الـ recursion ضرورية، وإلا الجار هينادي عليك تاني وتلفوا في دايرة.

خلي بالك من الـ recursion depth في Node الـ call stack بيستحمل حوالي 10 آلاف نداء متداخل (الرقم بيختلف حسب الدالة). grid 300 × 300 كلها أرض ممكن توصل لعمق أكبر بكتير، وتضرب RangeError. لو الـ grid كبيرة، استخدم BFS، أو DFS بـ stack بإيدك: نفس كود الـ BFS بالحرف، بس stack.pop() (آخر عنصر) بدل queue[head++] (أول عنصر).
BFS ولا DFS؟ عايز أقل عدد خطوات؟ BFS بس، لأنه بيوصل لكل خانة بأقصر طريق من أول مرة. عايز region (عدّ، مساحة، تلوين)؟ الاتنين صح، واختار الأسهل عليك.

عندنا الأدوات كلها. يلا نطبّق، ونبدأ بأبسط region ممكنة: خانة واحدة وكل اللي متوصل بيها.

مثال محلول 1: Flood Fill

Flood Fill

easyLeetCode 733

صورة كـ matrix أرقام، كل رقم لون. اديناك خانة بداية (sr, sc) ولون جديد color. لوّن البداية وكل خانة متوصلة بيها (4 اتجاهات) ولونها زي لون البداية الأصلي. زرار الجردل في Paint بالظبط.

Input: image = [[1,1,0,2],[0,1,1,2],[2,1,0,1]], sr = 0, sc = 0, color = 3 Output: [[3,3,0,2],[0,3,3,2],[2,3,0,1]] (the 1 at (2,3) is not connected: it stays 1) Input: image = [[4,4],[4,4]], sr = 1, sc = 0, color = 4 Output: [[4,4],[4,4]] (same color: nothing to do)

الجديد هنا: أول DFS على grid، من خانة واحدة، على region واحدة.

  1. الـ graph: فيه edge بين خانتين لازقين لو الاتنين لونهم زي لون البداية. المطلوب كل الـ component بتاع البداية، يعني DFS منها.
  2. الـ visited ببلاش: أول ما تلوّن خانة، لونها بقى color مش start، فالشرط هيرفضها لو رجعنالها. التلوين نفسه هو العلامة.
  3. الـ edge case: لو color === start التلوين مش بيغيّر حاجة، فمفيش علامة، والـ DFS هيلف للأبد. الحل early return.
  1. نحفظ اللون الأصلي قبل أي تلوين، لأن أول خطوة هتغيّر image[sr][sc] نفسها.
  2. من غيره، مع color === start، dfs(0,0) بينادي dfs(0,1) اللي بينادي dfs(0,0) تاني للأبد. جرّبناها: RangeError.
  3. الـ base cases: برا الـ grid، أو لون مختلف. التاني بيمسك كمان الخانات اللي لوّناها خلاص.
  4. بنلوّن قبل النداءات، وإلا الجار هيرجع ينادي علينا وإحنا لسه بلوننا القديم.
  5. كل نداء بيخلص خالص (هو وكل اللي نادى عليهم) قبل اللي بعده. ده معنى depth first.

المرة دي بنعرض كل نداء، حتى اللي بيرجع على طول. الـ call stack جنب الـ grid، والخانات اللي بإطار نداءاتها لسه مفتوحة:

Inputالمتوقعليه مهمة
[[4,4],[4,4]], (1,0), 4[[4,4],[4,4]]نفس اللون: من غير السطر 4 الـ stack يفرقع
[[5]], (0,0), 7[[7]]خانة واحدة، كل النداءات برا
[[1,2],[2,1]], (0,0), 9[[9,2],[2,1]]القطري مش جار

Complexity: كل خانة بتتلوّن مرة واحدة، فـ O(rows × cols) time، والـ recursion depth في الـ worst case O(rows × cols).

هنا كان عندنا region واحدة من خانة معروفة. طب لو عايز تعدّ كل الـ regions في الخريطة؟

مثال محلول 2: Number of Islands

Number of Islands

mediumLeetCode 200

خريطة فيها '1' أرض و '0' مية (strings مش أرقام). الجزيرة = خانات أرض لازقة أفقي أو رأسي، والقطري ما يتحسبش. كام جزيرة؟

Input: grid = [["1","1","0","1","1"], ["1","0","0","0","1"], ["0","0","1","0","0"], ["0","1","1","0","1"]] Output: 4 Input: grid = [["1","0"],["0","1"]] Output: 2 (diagonal does not connect)

الجديد هنا: outer loop على كل الخانات، وكل مرة نلاقي أرض جديدة نبدأ منها search. ده عدّ الـ connected components، نفس Number of Provinces (مسألة "قسّم الـ data centers لـ regions")، بس على grid.

  1. الخطة: لف على كل خانة. أرض ما حدّش زارها؟ دي جزيرة جديدة: islands++، وغرّق الجزيرة كلها عشان ما تتعدّش تاني.
  2. الـ visited: نحوّل الأرض لـ '0' وإحنا بنزورها. لو تعديل الـ input ممنوع، استخدم seen.
  3. Complexity: لازم تبص على كل خانة أصلًا، فـ O(rows × cols) هو الأحسن.

الحل الأول: BFS

  1. الـ outer loop هي اللي بتضمن إن ولا جزيرة تفوتنا، حتى لو معزولة.
  2. '1' الـ string مش 1 الرقم. '1' === 1 false، فلو كتبت الرقم هتطلع 0 جزر دايمًا. والسطر ده بيرفض المية والأرض المتغرّقة مع بعض.
  3. أرض جديدة = جزيرة جديدة. نعلّمها ونبدأ BFS بـ queue جديدة، نفس الـ template.
  4. cr, cc (current) عشان ما يتلخبطوش مع r, c بتوع الـ outer loop.
  5. Sink on push، عشان جارين ما يحطوش نفس الخانة مرتين.

الألوان بتقولك كل خانة اتغرّقت في أنهي جزيرة، بس القيمة الحقيقية جواها بقت 0. الـ queue تحت فيها اللي لسه مستني بس:

الحل التاني: DFS

نفس الفكرة، بس التغريق بـ recursion. أقصر وأسهل تكتبه وإنت متوتر في الاختبار:

  1. sink(r, c) بتغرّق الجزيرة اللي فيها الخانة دي كلها. مش بترجّع حاجة.
  2. نفس شروط الـ BFS بالظبط، بس continue بقت return.
  3. لما sink ترجع، الجزيرة كلها بقت مية، فالـ outer loop مش هتعدّ أي خانة منها تاني.

النداءات اللي بترجع على طول (برا أو مية) متلخّصة عشان الـ animation ما تبقاش 60 خطوة. قارن ترتيب التغريق بالـ BFS:

Inputالمتوقعليه مهمة
[["0"]]0مفيش أرض خالص
[["1","1"],["1","1"]]1كلها أرض، والـ BFS بيلاقي نفس الخانة من جارين
[["1","0"],["0","1"]]2القطري مش بيوصّل

Complexity: O(rows × cols) time. والـ memory في الـ worst case (كلها أرض) O(rows × cols)، للـ queue أو للـ recursion.

في الانترفيو قول: "دي connected components على grid. هلف على كل خانة، ولما ألاقي أرض جديدة أزوّد العداد وأغرّق الجزيرة بـ BFS. O(rows × cols)". وبعدين اسأل عن تعديل الـ input.

عرفنا نعدّ الجزر. طب لو عايز حجم كل جزيرة؟ الـ DFS لازم يرجّع رقم.

مثال محلول 3: Max Area of Island

Max Area of Island

mediumLeetCode 695

نفس الخريطة بأرقام 0 و 1 المرة دي. مساحة الجزيرة = عدد خاناتها. رجّع أكبر مساحة، أو 0 لو مفيش أرض.

Input: grid = [[0,1,1,0,0], [0,1,0,0,1], [1,0,0,1,1], [1,1,0,0,1]] Output: 4 (islands of size 3, 4 and 3)

الجديد هنا: الـ DFS بيرجّع قيمة. فكّر فيها recursive: "مساحتي = 1 (أنا) + اللي ورا فوق + تحت + شمال + يمين"، والخانة اللي برا أو مية أو اتعدّت بترجّع 0.

  1. ليه ما فيش عدّ مرتين؟ بنصفّر الخانة قبل ما ندخل في جيرانها، فلو جار رجع لها هيلاقيها 0.
  2. الهيكل: نفس Number of Islands بالظبط، بس islands++ بقت Math.max على مساحة كل جزيرة.
  1. الـ base cases بترجّع 0 مش return فاضية. 1 + undefined = NaN، والإجابة كلها تبوظ. والمقارنة بـ 1 الرقم، لأن الـ input أرقام هنا.
  2. نصفّر قبل الجمع، وإلا الجار هيعدّنا تاني.
  3. JS بيحسب الجمع من الشمال لليمين، فكل area(...) بتخلص خالص قبل اللي بعدها.
  4. best = 0 مش -Infinity: لو مفيش أرض الإجابة 0.

جنب كل نداء في الـ call stack مكتوب الـ sum لحد دلوقتي. لما نداء يخلص، رقمه بيتضاف على اللي ناداه:

وبـ BFS؟ نفس الـ template، وفي الآخر return queue.length: كل خانة دخلت الـ queue مرة بالظبط، والـ queue ما بتصغرش (بنحرّك head بس)، فطولها = حجم الجزيرة. Complexity: O(rows × cols).

لحد هنا كنا بنجمع regions، والترتيب مش فارق. طب لو المطلوب أقصر طريق، والحركة القطري مسموحة؟

مثال محلول 4: Shortest Path in Binary Matrix

Shortest Path in Binary Matrix

mediumLeetCode 1091

grid مربعة n × n، 0 مفتوح و 1 مقفول. روح من (0, 0) لـ (n-1, n-1) في 8 اتجاهات. طول الطريق = عدد الخانات اللي عدّيت عليها، بما فيهم البداية والنهاية. رجّع أقصر طول، أو -1.

Input: grid = [[0,1,0,0,0], [0,1,0,1,0], [0,0,1,1,0], [1,0,1,0,0], [1,1,0,0,0]] Output: 7 Input: grid = [[0]] → 1 (start = end, one cell) Input: grid = [[1,0],[0,0]] → -1 (the start itself is blocked)

الجديد هنا: BFS عشان أقصر طريق لهدف معيّن، بـ 8 directions، ونقف أول ما نوصل.

  1. أقصر طريق + كل خطوة بنفس الـ cost = BFS. الـ DFS غلط هنا، ممكن يوصل الأول من لفة طويلة.
  2. الطول بيعدّ خانات: البداية لوحدها طولها 1، فـ dist[0][0] = 1، و 0 تبقى علامة "لسه ما اتشافتش".
  3. Edge cases: البداية أو النهاية مقفولة: -1 على طول. n = 1 ومفتوحة: 1.
  1. Early return. ومن غيره [[1]] هترجّع 1، لأن الكود هيطلّع (0,0) ويلاقيها النهاية. الصح -1، وجرّبناها.
  2. أصفار، والبداية 1. المهم إن العلامة تبقى قيمة مستحيلة كـ distance.
  3. أول مرة النهاية تطلع من الـ queue، دي أقصر distance، لأن الـ BFS بيطلّع بترتيب الطول. والـ check هنا بيغطي n = 1 من غير كود زيادة.
  4. مقفولة أو اتشافت. الـ bounds اتأكدنا منها في السطر اللي قبله، فالقراية آمنة.
  5. الـ queue خلصت ولسه ما طلّعناش النهاية، يبقى مفيش طريق.

الأرقام هي dist، والغامق مقفول. في الآخر هنلوّن طريق من الطرق الأقصر (الكود مش محتاج الطريق نفسه، إحنا تتبعناه عشان تشوفه):

Complexity: كل خانة بتدخل الـ queue مرة وبتبص على 8 neighbors: O(n²). ولو المطلوب الطريق نفسه، خزّن parent[nr][nc] = [r, c] وإنت بتحط، وامشي ورا الـ parents من النهاية.

هنا كان فيه start واحد. طب لو فيه كذا start بيتنشروا في نفس الوقت؟

مثال محلول 5: Rotting Oranges (multi-source BFS)

Rotting Oranges

mediumLeetCode 994

قفص برتقان: 0 فاضي، 1 سليمة، 2 بايظة. كل دقيقة، أي سليمة لازقة (4 اتجاهات) في بايظة بتبوظ. رجّع أقل عدد دقايق لحد ما مفيش سليم، أو -1 لو فيه سليمة عمرها ما هتبوظ.

Input: grid = [[2,1,1,0,1], [0,1,0,1,1], [1,1,1,0,2]] Output: 4 Input: grid = [[2,0,1]] → -1 (the empty cell protects the last orange) Input: grid = [[0,2]] → 0 (no fresh orange at all)

الجديد هنا: حاجتين. multi-source: كل البايظ يدخل الـ queue من الأول. وlevel by level: الإجابة عدد الـ layers نفسه، مش distance خانة.

  1. Brute force: كل دقيقة لف على الـ grid كلها وبوّظ اللي جنب بايظ. O(rows × cols) لكل دقيقة، وممكن rows × cols دقيقة، يعني O((rows × cols)²).
  2. الـ key insight: البوظان بيتنشر layer by layer زي الـ BFS بالظبط. اللي بايظ من الأول layer 0، واللي يبوظ في الدقيقة الأولى layer 1. كأن فيه node وهمية متوصلة بكل البايظين.
  3. نعدّ الدقايق: قبل كل دقيقة نشوف في الـ queue كام عنصر (levelSize)، نطلّعهم هما بس، وبعدين minutes++.
  4. الـ -1: نعدّ السليم في الأول (fresh) وننقص مع كل برتقانة تبوظ. لو في الآخر fresh > 0، فيه برتقانة محبوسة.
تشبيه حريقة بدأت في كذا شقة في نفس اللحظة. كل دقيقة، كل الشقق اللي بتولّع دلوقتي بتولّع جيرانها مع بعض. الـ levelSize هو "عدد الشقق اللي بتولّع الدقيقة دي".
  1. لفة واحدة: كل البايظ في الـ queue (layer 0 كله مع بعض)، وكل السليم يتعدّ. البايظ مش محتاج علامة، الـ 2 هي العلامة.
  2. ليه && fresh > 0؟ من غيره الـ loop هتطلّع آخر layer (اللي مش هتبوّظ حد) وتزوّد دقيقة على الفاضي: 5 بدل 4، و [[0,2]] ترجّع 1 بدل 0. جرّبنا الاتنين.
  3. أهم سطر: levelSize بيتحسب مرة واحدة قبل الـ inner loop. في اللحظة دي، اللي في الـ queue من head لآخرها هما بالظبط بايظين الدقيقة دي، واللي هيتضافوا جوه الـ loop بتوع الدقيقة الجاية (شوف الغلطة 3 تحت).
  4. الجار لازم يكون سليم (1). ده السطر اللي بيتغير عن الـ template.
  5. نبوّظه وإحنا بنحطه وننقص fresh. لو استنّينا للـ pop، جارين ممكن يحطوه مرتين.
  6. layer كامل = دقيقة. مكانه برا الـ inner loop، وإلا هتعدّ دقيقة لكل برتقانة.

الأحمر بايظ والأصفر سليم. في الـ queue، الأزرق هو layer الدقيقة الحالية، واللي بعده للدقيقة الجاية:

Inputالمتوقعليه مهمة
[[0,2]]0مفيش سليم: fresh > 0 بيمنع الـ loop
[[1]]-1سليم ومفيش بايظ: الـ queue فاضية
[[2,0,1]]-1خانة فاضية فاصلة

Complexity: كل برتقانة بتدخل الـ queue مرة: O(rows × cols) time و memory.

هنا كنا عايزين رقم واحد: عدد الـ layers. طب لو عايز distance كل خانة لأقرب مصدر؟

مثال محلول 6: 01 Matrix

01 Matrix

mediumLeetCode 542

matrix فيها 0 و 1 بس، وفيها صفر واحد على الأقل. لكل خانة رجّع الـ distance لأقرب 0 (خطوات فوق/تحت/شمال/يمين).

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

الجديد هنا: multi-source تاني، بس من غير levelSize. عايزين distance لكل خانة، فبنخزّنها في dist زي الـ template.

  1. Brute force: BFS من كل 1 لحد أول صفر: O((rows × cols)²). مع 100 × 100 ده 100 مليون عملية.
  2. اقلب السؤال: بدل "كل خانة تدوّر على أقرب صفر"، خلّي "كل الأصفار تتنشر مع بعض". أول مرة الموجة توصل لخانة، دي الـ distance لأقرب صفر.
  3. الـ rule: عايز رقم واحد (عدد layers)؟ levelSize. عايز distance كل خانة؟ dist.
  1. -1 = لسه. مش 0، لأن 0 إجابة حقيقية للأصفار.
  2. كل الأصفار في الـ queue بـ distance 0 قبل ما الـ BFS يبدأ. ده الـ multi-source.
  3. ليه ما بنحدّثهاش لو اتشافت؟ الـ BFS بيطلّع بترتيب الـ distance، فأول قيمة اتحطت هي الأصغر.
  4. matrix جديدة، والـ input ما اتلمسش.

الأخضر أصفار، والإطار المتقطّع لسه مستني في الـ queue:

Complexity: O(rows × cols) بدل O((rows × cols)²). ولما تشوف "أقرب X لكل خانة" وفيه X كتير، ابدأ من كل الـ X مع بعض: As Far from Land، Map of Highest Peak، نفس الحيلة.

لحد دلوقتي المصادر كانت خانات بقيمة معيّنة. طب لو المسألة كلها عن مين يقدر يوصل للحافة؟

مثال محلول 7: Surrounded Regions (ابدأ من الحافة)

Surrounded Regions

mediumLeetCode 130

board فيه 'X' و 'O'. أي مجموعة 'O' متوصلة وولا خانة فيها على الحافة، اقلبها كلها 'X'. المجموعة اللي فيها ولو خانة واحدة على الحافة بتفضل. عدّل in-place.

Input: Output: X X X X X X X X X X X O O X X X X X X X X X O X O X X X X O X O X X O X O X X O X O X X X X O X X X

الجديد هنا: reverse thinking. بدل "مين المحاصر؟" اسأل "مين مش محاصر؟": أي O متوصلة بـ O على الحافة. يعني المصادر هي خانات الحافة.

  1. الطريقة المباشرة: BFS لكل مجموعة، اجمع خاناتها، وشوف فيه حد على الحافة ولا لأ، وبعدين اقلب. شغالة بس أطول وأسهل تغلط فيها.
  2. الخطة: multi-source BFS من كل O على الحافة، علّمها 'S' (safe). بعدها أي O فاضلة محاصرة: X. والـ S ترجع O.
تشبيه قرية بيوت والبحر حواليها. بدل ما تروح لكل بيت وتسأل "توصل للبحر؟"، اقف على الشط وامشي لجوه من كل بيت على الشط. اللي ما وصلتلوش محاصر.
  1. على الحافة = أول أو آخر صف (rows - 1 مش rows) أو أول أو آخر عمود.
  2. كل O على الحافة source. نفس الـ multi-source، بس المصادر هي البرواز.
  3. بنتنشر لـ 'O' بس. الـ X حيطة، والـ S اتعلّمت.
  4. else if مش if. هنا مش فارقة، بس لو عكست الترتيب من غير else هترجّع الآمن O وتقلبه X في نفس اللفة.

الغامق X، والأخضر اتعلّم safe. في الآخر اللي فضل O بيتقلب:

Complexity: 3 لفات، وكل خانة بتدخل الـ queue مرة بالكتير: O(rows × cols). ونفس الفكرة في Number of Enclaves و Number of Closed Islands.

هنا كان فيه حافة واحدة وشرط بسيط. طب لو فيه حافتين، والحركة ليها شرط ارتفاع؟

مثال محلول 8: Pacific Atlantic Water Flow

Pacific Atlantic Water Flow

mediumLeetCode 417

جزيرة كـ matrix ارتفاعات. الـ Pacific لازق في الحافة اللي فوق واللي على الشمال، والـ Atlantic في اللي تحت واللي على اليمين. المية بتمشي لجار (4 اتجاهات) ارتفاعه أقل من أو يساوي ارتفاعها، ومن الحافة بتنزل في المحيط. رجّع الخانات اللي المية منها توصل للمحيطين.

Input: heights = [[1,3,2,4], [2,5,3,3], [4,4,6,2], [3,1,5,1]] Output: [[0,3],[1,1],[1,2],[1,3],[2,0],[2,1],[2,2],[3,0]]

الجديد هنا: reverse BFS مرتين بشرط ارتفاع، وبعدين intersection.

  1. Brute force: من كل خانة BFS لتحت، وشوف وصلت للمحيطين ولا لأ: O((rows × cols)²).
  2. اقلب الاتجاه: اقف في المحيط وامشي عكس المية، لفوق. من خانة بتوصل للمحيط، تقدر تروح لجار ارتفاعه أكبر من أو يساوي ارتفاعها، لأن المية منه هتنزل لها.
  3. مرتين: BFS من حافة الـ Pacific يدّي pac، ومن حافة الـ Atlantic يدّي atl. الإجابة الخانات اللي في الاتنين.
  4. خلي بالك من التساوي: نرفض الجار بس لو أوطى (<). لو كتبت <=، المثال ده يطلع 5 خانات بدل 8. جرّبناها.
  1. دالة واحدة للمحيطين، الفرق في الـ starts بس. ما تكتبش الـ BFS مرتين.
  2. هنا لازم seen لوحدها: محتاجين heights سليمة للـ BFS التاني، وكل محيط له visited خاص بيه.
  3. الركن (0,0) موجود في قائمة الصف وقائمة العمود، فمن غير السطر ده هيدخل الـ queue مرتين.
  4. السطر اللي فيه المسألة كلها. الجار يبعت مية لنا لو heights[nr][nc] >= heights[r][c]، فنرفضه لو أقل.
  5. Pacific: العمود 0 والصف 0. Atlantic: العمود cols - 1 والصف rows - 1.

الأزرق يوصل للـ Pacific، والبنفسجي للـ Atlantic، والأخضر للاتنين. الأرقام ارتفاعات:

Complexity: 2 BFS ولفة للـ intersection: O(rows × cols) بدل O((rows × cols)²).

في الانترفيو لو المسألة "من كل خانة، تقدر توصل لـ X؟"، اقلبها لـ "من X، أقدر أوصل لأنهي خانات؟". ده الـ insight اللي الـ interviewer مستنيه في Surrounded Regions و Pacific Atlantic.

كده شفنا الأنماط الأربعة. يلا نجمع الغلطات اللي بتوقّع الناس فيهم.

غلطات مشهورة

كلهم اتجرّبوا في node بجد، وكلهم بيطلّعوا wrong answer أو crash من غير ما يبان السبب. (وفخ fill شفناه بالـ animation في جزء الـ visited.)

1. > بدل >= في الـ bounds check

آخر index هو الطول ناقص 1، فالصح >=. والأخطر الأعمدة: مفيش error خالص، بس إجابة غلط.

2. تعلّم الـ visited وقت الـ pop بدل الـ push

على [[2,1],[1,1]] بترجّع 3 بدل 2: (1,1) بتدخل من جارين، والبوظان كله بيتأخر layer. القاعدة: mark on push.

3. levelSize جوه شرط الـ loop

بيخلط برتقان الدقيقة الجاية مع الحالية: [[2,1],[1,1]] ترجّع 1 بدل 2. احسب levelSize في سطر لوحده قبل الـ loop.

4. 1 الرقم بدل '1' الـ string

Islands و Surrounded فيهم حروف، و Max Area و Oranges و 01 Matrix فيهم أرقام. لو فيه علامات تنصيص في المثال يبقى strings.

5. Flood Fill لما اللون الجديد زي القديم

أي مرة تستخدم تعديل الـ grid كـ visited، اسأل: "القيمة الجديدة مختلفة عن اللي بدوّر عليها؟".

لو الغلطات دي واضحة، جرّب نفسك في كام سؤال سريع.

اختبر نفسك

BFS على grid فيها rows صف و cols عمود. الـ time complexity؟

  • O(rows + cols)
  • O(rows × cols)
  • O((rows × cols)²)
  • O(rows × cols × log(rows × cols))

كل خانة بتدخل الـ queue مرة بالكتير، ولما تطلع بتبص على 4 neighbors: حوالي 4 × rows × cols. ده O(V + E) بالظبط.

خريطة مدينة فيها كذا مستشفى. لكل خانة عايز الـ distance لأقرب مستشفى. أحسن حل؟

  • BFS من كل خانة لحد ما تلاقي مستشفى
  • BFS من كل مستشفى لوحده، وتاخد الأقل
  • BFS واحد، وكل المستشفيات في الـ queue من الأول بـ distance 0
  • DFS من أول مستشفى

multi-source BFS، زي 01 Matrix. O(rows × cols) بدل ما تضرب في عدد الخانات أو المستشفيات.

ليه الـ DFS ما ينفعش لأقصر طريق في متاهة؟

  • لأنه أبطأ من الـ BFS
  • لأنه مش بيزور كل الخانات
  • لأنه بيجري في اتجاه لآخره، فأول مرة يوصل لخانة ممكن يكون جاي من لفة طويلة
  • لأن الـ recursion مش بتشتغل على grid

الاتنين O(rows × cols). الفرق في الـ order: الـ BFS بيطلّع بترتيب الـ distance، والـ DFS مالوش الضمان ده.

في Surrounded Regions، مجموعة O فيها 10 خانات، واحدة بس على الحافة. هيحصلها إيه؟

  • الـ 9 اللي جوه يتقلبوا X
  • المجموعة كلها تفضل O
  • المجموعة كلها تتقلب X
  • حسب حجمها

الـ BFS بيبدأ من خانة الحافة ويتنشر للمجموعة كلها، فكلها تبقى safe.

تمرين: فكّر قبل ما تفتح

As Far from Land as Possible

mediumLeetCode 1162

grid مربعة n × n، 1 أرض و 0 مية. لاقي خانة المية اللي أبعد حاجة عن أقرب أرض ليها، ورجّع الـ distance دي. لو مفيش أرض خالص أو مفيش مية خالص، رجّع -1.

[[1,0,1],[0,0,0],[1,0,1]] → 2 (the middle cell is 2 steps from every corner) [[1,0,0],[0,0,0],[0,0,0]] → 4 (the bottom-right corner) [[1,1],[1,1]] → -1 (no water)
تلميح 1

"أقرب أرض لكل خانة مية"، وفيه أرض كتير. ده 01 Matrix بالظبط، بس الأرض مكان الأصفار.

تلميح 2

multi-source BFS من كل الأرض بـ distance 0، وخد أكبر dist. وقبله: لو عدد الأرض 0 أو n × n، رجّع -1.

الحل

O(n²). الـ BFS بيطلّع بترتيب الـ distance، فآخر خانة طلعت هي الأبعد. جرّبناه على الأمثلة التلاتة: 2 و 4 و -1.

لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

اتمرن على LeetCode بالترتيب

كل مسألة بتضيف فكرة واحدة. لو قعدت أكتر من 25 دقيقة، ارجع للـ template بتاعها هنا، وبعدين حاول تاني من غير ما تبص.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة الـ grid هي graph الـ neighbors فيه بـ DIRS و bounds check (>= rows). region؟ DFS أو BFS من كل خانة جديدة. أقل خطوات؟ BFS. كذا مصدر؟ كلهم في الـ queue من الأول. الحافة؟ ابدأ منها.
السؤالالإجابة
> ولا >= في الحدود؟nr >= rows و nc >= cols: الطول نفسه برا.
الـ visited فين؟in-place لو مسموح، أو seen بـ Array.from، أو dist = -1. ودايمًا on push.
BFS ولا DFS؟shortest path: BFS. region: الاتنين، وخلي بالك من الـ recursion depth.
levelSize ولا dist؟رقم واحد (دقايق): levelSize. distance كل خانة: dist.
"محاصر" أو "يوصل للحافة"؟reverse: ابدأ من الحافة وامشي لجوه.

كل اللي عملناه هنا كل خطوة فيه بنفس الـ cost، فالـ BFS كفاية. في الفصل الجاي الـ edges هيبقى ليها weights (Dijkstra، ومنها Path With Minimum Effort اللي هي grid بالظبط بس كل خطوة ليها cost)، أو direction معناه "ده قبل ده" (Topological Sort)، أو هتيجي واحدة واحدة وإنت عايز تعرف مين متوصل بمين (Union-Find). وحيلة r * cols + c مستنياك هناك.

طب لو كل خطوة ليها cost مختلف، أو الـ edges ليها اتجاه؟ ده الفصل الجاي.