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، نفس اللي عدّيناه في الفصل اللي فات.
بص الـ BFS وهو بيتنشر من خانة في النص زي المية بالظبط، layer by layer. الرقم = أقل عدد خطوات من البداية، والخانات الغامقة حيطان:
ده نفس الـ BFS بالحرف. الفرق الوحيد إن بدل adj[u]، بتحسب الـ neighbors بنفسك وتتأكد إنهم جوه الـ grid. والفرق الصغير ده هو كل الفصل.
طب إزاي تعرف من كلام المسألة إنها grid graph، وأنهي نوع فيهم؟
إزاي تعرفه من المسألة
لو الحركة يمين وتحت بس والمطلوب أقل مجموع، ده DP على grid. لو كل خانة ليها cost مختلف، ده Dijkstra في الفصل الجاي. ولو الصفوف والأعمدة مترتبة، ده binary search.
| النمط | بتبدأ منين | الأداة | مسائل الفصل |
|---|---|---|---|
| مناطق regions | كل خانة لسه ما اتزارتش | DFS أو BFS | Flood Fill، Number of Islands، Max Area |
| أقصر طريق single-source BFS | الـ start | BFS + dist | Shortest Path in Binary Matrix |
| كذا مصدر multi-source BFS | كل المصادر مع بعض | BFS + levelSize أو dist | Rotting 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 و E | V = 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 كده:
- كل pair هو
[dr, dc]: هتزوّد كام على الصف وكام على العمود. فوق = الصف اللي قبله، فـdr = -1. بدل 4ifشبه بعض، loop واحدة. rows= عدد الصفوف =grid.length، وcols= طول أول صف. لو الـ grid فاضيةgrid[0]هتبقىundefined، فاعمل early return لو مش مضمونة.- الجار المحتمل. لسه ما نعرفش هو موجود ولا لأ.
- الـ bounds check. الصفوف من
0لـrows - 1، فـnr === rowsنفسه برا. عشان كده>=مش>، نفس غلطةi <= n. - والـ check ده لازم ييجي قبل أي
grid[nr][nc]. الـ||بيقف عند أول true، فعمرنا ما هنقراgrid[-1]. - خانة في النص ليها 4 neighbors، على الحافة 3، وفي الركن 2.
الـ animation دي بترسم الـ grid جوه برواز وهمي (الخانات الباهتة) عشان تشوف اللي برا. خانة في النص، وبعدين الركنين:
grid فيها 4 صفوف، وكتبت nr > rows بدل nr >= rows. إيه اللي هيحصل مع الخانة (3, 4)؟
- ولا حاجة، الشرطين واحد
- "تحت" هتدّي
nr = 4، و4 > 4false، فهيقرا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 من strings | seen.add(r + ',' + c) | مش محتاج تعرف الحجم | أبطأ: string + hash كل خطوة |
| الـ dist نفسها | dist[r][c] === -1 | matrix واحدة لشغلانتين | لما تكون محتاج distance أصلًا |
فخ 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 للي مش ممكن توصله.
distشغالة distance و visited مع بعض. ليه-1مش0؟ لأن0distance حقيقية (البداية نفسها)، فمش هتفرّق بين "لسه" و "دي البداية".- Mark on push: البداية بتتعلّم في نفس لحظة ما تدخل الـ queue. كده أي خانة عمرها ما تدخل الـ queue مرتين.
- ليه
headمشqueue.shift()؟ الـshift()بيزق كل العناصر خانة لقدام، يعني O(n) كل مرة. الـheadمجرد index لأول عنصر لسه ما اتعالجش. queue[head++]: postfix، ياخدqueue[head]وبعدين يزوّد. لو كتبت++headهتنط على عنصر.- الـ bounds check الأول، قبل أي سطر بيقرا
grid[nr][nc]. - ده السطر اللي بيتغير من مسألة للتانية: حيطة، مية، "أوطى مني"، "مش برتقانة سليمة".
- اتشافت قبل كده، يعني عندها distance أصغر أو قد اللي هنديهالها، لأن الـ BFS ماشي layer by layer.
- distance الجار = distance اللي جه منها + 1، وفي نفس السطر بقت visited.
- أي خانة لسه
-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 ضرورية، وإلا الجار هينادي عليك تاني وتلفوا في دايرة.
RangeError. لو الـ grid كبيرة، استخدم BFS، أو DFS بـ stack بإيدك: نفس كود الـ BFS بالحرف، بس stack.pop() (آخر عنصر) بدل queue[head++] (أول عنصر).
عندنا الأدوات كلها. يلا نطبّق، ونبدأ بأبسط region ممكنة: خانة واحدة وكل اللي متوصل بيها.
مثال محلول 1: Flood Fill
صورة كـ matrix أرقام، كل رقم لون. اديناك خانة بداية (sr, sc) ولون جديد color. لوّن البداية وكل خانة متوصلة بيها (4 اتجاهات) ولونها زي لون البداية الأصلي. زرار الجردل في Paint بالظبط.
الجديد هنا: أول DFS على grid، من خانة واحدة، على region واحدة.
- الـ graph: فيه edge بين خانتين لازقين لو الاتنين لونهم زي لون البداية. المطلوب كل الـ component بتاع البداية، يعني DFS منها.
- الـ visited ببلاش: أول ما تلوّن خانة، لونها بقى
colorمشstart، فالشرط هيرفضها لو رجعنالها. التلوين نفسه هو العلامة. - الـ edge case: لو
color === startالتلوين مش بيغيّر حاجة، فمفيش علامة، والـ DFS هيلف للأبد. الحل early return.
- نحفظ اللون الأصلي قبل أي تلوين، لأن أول خطوة هتغيّر
image[sr][sc]نفسها. - من غيره، مع
color === start،dfs(0,0)بيناديdfs(0,1)اللي بيناديdfs(0,0)تاني للأبد. جرّبناها:RangeError. - الـ base cases: برا الـ grid، أو لون مختلف. التاني بيمسك كمان الخانات اللي لوّناها خلاص.
- بنلوّن قبل النداءات، وإلا الجار هيرجع ينادي علينا وإحنا لسه بلوننا القديم.
- كل نداء بيخلص خالص (هو وكل اللي نادى عليهم) قبل اللي بعده. ده معنى 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
خريطة فيها '1' أرض و '0' مية (strings مش أرقام). الجزيرة = خانات أرض لازقة أفقي أو رأسي، والقطري ما يتحسبش. كام جزيرة؟
الجديد هنا: outer loop على كل الخانات، وكل مرة نلاقي أرض جديدة نبدأ منها search. ده عدّ الـ connected components، نفس Number of Provinces (مسألة "قسّم الـ data centers لـ regions")، بس على grid.
- الخطة: لف على كل خانة. أرض ما حدّش زارها؟ دي جزيرة جديدة:
islands++، وغرّق الجزيرة كلها عشان ما تتعدّش تاني. - الـ visited: نحوّل الأرض لـ
'0'وإحنا بنزورها. لو تعديل الـ input ممنوع، استخدمseen. - Complexity: لازم تبص على كل خانة أصلًا، فـ
O(rows × cols)هو الأحسن.
الحل الأول: BFS
- الـ outer loop هي اللي بتضمن إن ولا جزيرة تفوتنا، حتى لو معزولة.
'1'الـ string مش1الرقم.'1' === 1false، فلو كتبت الرقم هتطلع 0 جزر دايمًا. والسطر ده بيرفض المية والأرض المتغرّقة مع بعض.- أرض جديدة = جزيرة جديدة. نعلّمها ونبدأ BFS بـ queue جديدة، نفس الـ template.
cr, cc(current) عشان ما يتلخبطوش معr, cبتوع الـ outer loop.- Sink on push، عشان جارين ما يحطوش نفس الخانة مرتين.
الألوان بتقولك كل خانة اتغرّقت في أنهي جزيرة، بس القيمة الحقيقية جواها بقت 0. الـ queue تحت فيها اللي لسه مستني بس:
الحل التاني: DFS
نفس الفكرة، بس التغريق بـ recursion. أقصر وأسهل تكتبه وإنت متوتر في الاختبار:
sink(r, c)بتغرّق الجزيرة اللي فيها الخانة دي كلها. مش بترجّع حاجة.- نفس شروط الـ BFS بالظبط، بس
continueبقتreturn. - لما
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.
عرفنا نعدّ الجزر. طب لو عايز حجم كل جزيرة؟ الـ DFS لازم يرجّع رقم.
مثال محلول 3: Max Area of Island
نفس الخريطة بأرقام 0 و 1 المرة دي. مساحة الجزيرة = عدد خاناتها. رجّع أكبر مساحة، أو 0 لو مفيش أرض.
الجديد هنا: الـ DFS بيرجّع قيمة. فكّر فيها recursive: "مساحتي = 1 (أنا) + اللي ورا فوق + تحت + شمال + يمين"، والخانة اللي برا أو مية أو اتعدّت بترجّع 0.
- ليه ما فيش عدّ مرتين؟ بنصفّر الخانة قبل ما ندخل في جيرانها، فلو جار رجع لها هيلاقيها 0.
- الهيكل: نفس Number of Islands بالظبط، بس
islands++بقتMath.maxعلى مساحة كل جزيرة.
- الـ base cases بترجّع
0مشreturnفاضية.1 + undefined=NaN، والإجابة كلها تبوظ. والمقارنة بـ1الرقم، لأن الـ input أرقام هنا. - نصفّر قبل الجمع، وإلا الجار هيعدّنا تاني.
- JS بيحسب الجمع من الشمال لليمين، فكل
area(...)بتخلص خالص قبل اللي بعدها. 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
grid مربعة n × n، 0 مفتوح و 1 مقفول. روح من (0, 0) لـ (n-1, n-1) في 8 اتجاهات. طول الطريق = عدد الخانات اللي عدّيت عليها، بما فيهم البداية والنهاية. رجّع أقصر طول، أو -1.
الجديد هنا: BFS عشان أقصر طريق لهدف معيّن، بـ 8 directions، ونقف أول ما نوصل.
- أقصر طريق + كل خطوة بنفس الـ cost = BFS. الـ DFS غلط هنا، ممكن يوصل الأول من لفة طويلة.
- الطول بيعدّ خانات: البداية لوحدها طولها 1، فـ
dist[0][0] = 1، و0تبقى علامة "لسه ما اتشافتش". - Edge cases: البداية أو النهاية مقفولة:
-1على طول.n = 1ومفتوحة:1.
- Early return. ومن غيره
[[1]]هترجّع 1، لأن الكود هيطلّع(0,0)ويلاقيها النهاية. الصح -1، وجرّبناها. - أصفار، والبداية
1. المهم إن العلامة تبقى قيمة مستحيلة كـ distance. - أول مرة النهاية تطلع من الـ queue، دي أقصر distance، لأن الـ BFS بيطلّع بترتيب الطول. والـ check هنا بيغطي
n = 1من غير كود زيادة. - مقفولة أو اتشافت. الـ bounds اتأكدنا منها في السطر اللي قبله، فالقراية آمنة.
- الـ queue خلصت ولسه ما طلّعناش النهاية، يبقى مفيش طريق.
الأرقام هي dist، والغامق مقفول. في الآخر هنلوّن طريق من الطرق الأقصر (الكود مش محتاج الطريق نفسه، إحنا تتبعناه عشان تشوفه):
Complexity: كل خانة بتدخل الـ queue مرة وبتبص على 8 neighbors: O(n²). ولو المطلوب الطريق نفسه، خزّن parent[nr][nc] = [r, c] وإنت بتحط، وامشي ورا الـ parents من النهاية.
هنا كان فيه start واحد. طب لو فيه كذا start بيتنشروا في نفس الوقت؟
مثال محلول 5: Rotting Oranges (multi-source BFS)
قفص برتقان: 0 فاضي، 1 سليمة، 2 بايظة. كل دقيقة، أي سليمة لازقة (4 اتجاهات) في بايظة بتبوظ. رجّع أقل عدد دقايق لحد ما مفيش سليم، أو -1 لو فيه سليمة عمرها ما هتبوظ.
الجديد هنا: حاجتين. multi-source: كل البايظ يدخل الـ queue من الأول. وlevel by level: الإجابة عدد الـ layers نفسه، مش distance خانة.
- Brute force: كل دقيقة لف على الـ grid كلها وبوّظ اللي جنب بايظ.
O(rows × cols)لكل دقيقة، وممكنrows × colsدقيقة، يعنيO((rows × cols)²). - الـ key insight: البوظان بيتنشر layer by layer زي الـ BFS بالظبط. اللي بايظ من الأول layer 0، واللي يبوظ في الدقيقة الأولى layer 1. كأن فيه node وهمية متوصلة بكل البايظين.
- نعدّ الدقايق: قبل كل دقيقة نشوف في الـ queue كام عنصر (
levelSize)، نطلّعهم هما بس، وبعدينminutes++. - الـ -1: نعدّ السليم في الأول (
fresh) وننقص مع كل برتقانة تبوظ. لو في الآخرfresh > 0، فيه برتقانة محبوسة.
levelSize هو "عدد الشقق اللي بتولّع الدقيقة دي".
- لفة واحدة: كل البايظ في الـ queue (layer 0 كله مع بعض)، وكل السليم يتعدّ. البايظ مش محتاج علامة، الـ
2هي العلامة. - ليه
&& fresh > 0؟ من غيره الـ loop هتطلّع آخر layer (اللي مش هتبوّظ حد) وتزوّد دقيقة على الفاضي: 5 بدل 4، و[[0,2]]ترجّع 1 بدل 0. جرّبنا الاتنين. - أهم سطر:
levelSizeبيتحسب مرة واحدة قبل الـ inner loop. في اللحظة دي، اللي في الـ queue منheadلآخرها هما بالظبط بايظين الدقيقة دي، واللي هيتضافوا جوه الـ loop بتوع الدقيقة الجاية (شوف الغلطة 3 تحت). - الجار لازم يكون سليم (
1). ده السطر اللي بيتغير عن الـ template. - نبوّظه وإحنا بنحطه وننقص
fresh. لو استنّينا للـ pop، جارين ممكن يحطوه مرتين. - 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
matrix فيها 0 و 1 بس، وفيها صفر واحد على الأقل. لكل خانة رجّع الـ distance لأقرب 0 (خطوات فوق/تحت/شمال/يمين).
الجديد هنا: multi-source تاني، بس من غير levelSize. عايزين distance لكل خانة، فبنخزّنها في dist زي الـ template.
- Brute force: BFS من كل
1لحد أول صفر:O((rows × cols)²). مع 100 × 100 ده 100 مليون عملية. - اقلب السؤال: بدل "كل خانة تدوّر على أقرب صفر"، خلّي "كل الأصفار تتنشر مع بعض". أول مرة الموجة توصل لخانة، دي الـ distance لأقرب صفر.
- الـ rule: عايز رقم واحد (عدد layers)؟
levelSize. عايز distance كل خانة؟dist.
-1= لسه. مش0، لأن 0 إجابة حقيقية للأصفار.- كل الأصفار في الـ queue بـ distance 0 قبل ما الـ BFS يبدأ. ده الـ multi-source.
- ليه ما بنحدّثهاش لو اتشافت؟ الـ BFS بيطلّع بترتيب الـ distance، فأول قيمة اتحطت هي الأصغر.
- matrix جديدة، والـ input ما اتلمسش.
الأخضر أصفار، والإطار المتقطّع لسه مستني في الـ queue:
Complexity: O(rows × cols) بدل O((rows × cols)²). ولما تشوف "أقرب X لكل خانة" وفيه X كتير، ابدأ من كل الـ X مع بعض: As Far from Land، Map of Highest Peak، نفس الحيلة.
لحد دلوقتي المصادر كانت خانات بقيمة معيّنة. طب لو المسألة كلها عن مين يقدر يوصل للحافة؟
مثال محلول 7: Surrounded Regions (ابدأ من الحافة)
board فيه 'X' و 'O'. أي مجموعة 'O' متوصلة وولا خانة فيها على الحافة، اقلبها كلها 'X'. المجموعة اللي فيها ولو خانة واحدة على الحافة بتفضل. عدّل in-place.
الجديد هنا: reverse thinking. بدل "مين المحاصر؟" اسأل "مين مش محاصر؟": أي O متوصلة بـ O على الحافة. يعني المصادر هي خانات الحافة.
- الطريقة المباشرة: BFS لكل مجموعة، اجمع خاناتها، وشوف فيه حد على الحافة ولا لأ، وبعدين اقلب. شغالة بس أطول وأسهل تغلط فيها.
- الخطة: multi-source BFS من كل
Oعلى الحافة، علّمها'S'(safe). بعدها أيOفاضلة محاصرة:X. والـSترجعO.
- على الحافة = أول أو آخر صف (
rows - 1مشrows) أو أول أو آخر عمود. - كل
Oعلى الحافة source. نفس الـ multi-source، بس المصادر هي البرواز. - بنتنشر لـ
'O'بس. الـXحيطة، والـSاتعلّمت. 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
جزيرة كـ matrix ارتفاعات. الـ Pacific لازق في الحافة اللي فوق واللي على الشمال، والـ Atlantic في اللي تحت واللي على اليمين. المية بتمشي لجار (4 اتجاهات) ارتفاعه أقل من أو يساوي ارتفاعها، ومن الحافة بتنزل في المحيط. رجّع الخانات اللي المية منها توصل للمحيطين.
الجديد هنا: reverse BFS مرتين بشرط ارتفاع، وبعدين intersection.
- Brute force: من كل خانة BFS لتحت، وشوف وصلت للمحيطين ولا لأ:
O((rows × cols)²). - اقلب الاتجاه: اقف في المحيط وامشي عكس المية، لفوق. من خانة بتوصل للمحيط، تقدر تروح لجار ارتفاعه أكبر من أو يساوي ارتفاعها، لأن المية منه هتنزل لها.
- مرتين: BFS من حافة الـ Pacific يدّي
pac، ومن حافة الـ Atlantic يدّيatl. الإجابة الخانات اللي في الاتنين. - خلي بالك من التساوي: نرفض الجار بس لو أوطى (
<). لو كتبت<=، المثال ده يطلع 5 خانات بدل 8. جرّبناها.
- دالة واحدة للمحيطين، الفرق في الـ starts بس. ما تكتبش الـ BFS مرتين.
- هنا لازم
seenلوحدها: محتاجينheightsسليمة للـ BFS التاني، وكل محيط له visited خاص بيه. - الركن
(0,0)موجود في قائمة الصف وقائمة العمود، فمن غير السطر ده هيدخل الـ queue مرتين. - السطر اللي فيه المسألة كلها. الجار يبعت مية لنا لو
heights[nr][nc] >= heights[r][c]، فنرفضه لو أقل. - Pacific: العمود 0 والصف 0. Atlantic: العمود
cols - 1والصفrows - 1.
الأزرق يوصل للـ Pacific، والبنفسجي للـ Atlantic، والأخضر للاتنين. الأرقام ارتفاعات:
Complexity: 2 BFS ولفة للـ intersection: O(rows × cols) بدل O((rows × cols)²).
كده شفنا الأنماط الأربعة. يلا نجمع الغلطات اللي بتوقّع الناس فيهم.
غلطات مشهورة
كلهم اتجرّبوا في 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.
تمرين: فكّر قبل ما تفتح
grid مربعة n × n، 1 أرض و 0 مية. لاقي خانة المية اللي أبعد حاجة عن أقرب أرض ليها، ورجّع الـ distance دي. لو مفيش أرض خالص أو مفيش مية خالص، رجّع -1.
تلميح 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 بتاعها هنا، وبعدين حاول تاني من غير ما تبص.
- Flood Fillالمثال المحلول 1. أبسط DFS على grid، وفخ اللون المساوي.
- Island Perimeterمن غير BFS: لكل أرض عدّ الـ neighbors اللي مية أو برا. تمرين على DIRS والـ bounds لوحدهم.
- Number of Islandsالمثال المحلول 2. اكتبه BFS مرة و DFS مرة. خلي بالك من
'1'. - Max Area of IslandDFS بيرجّع رقم:
1 + الأربع اتجاهات. - Number of Enclavesأول "ابدأ من الحافة": غرّق اللي لازق في الحافة وعدّ الباقي.
- Surrounded Regionsالمثال المحلول 7: نفس الحافة، مع علامة تالتة
'S'. - Number of Closed Islandsالأرض
0والمية1هنا، بالعكس. غرّق جزر الحافة، وبعدين عدّ. - Rotting Orangesالمثال المحلول 5. multi-source و
levelSize، وافهم الـfresh > 0. - 01 Matrixmulti-source بـ
distبدلlevelSize. - As Far from Land as Possibleالتمرين اللي فوق: 01 Matrix بس الإجابة أكبر distance، وحالات الـ -1.
- Nearest Exit from Entrance in MazeBFS من نقطة لحد أول خانة على الحافة. المدخل نفسه مش مخرج.
- Shortest Path in Binary Matrixالمثال المحلول 4. 8 directions، والطول بيعدّ خانات.
- Shortest Bridgeتجميعة: DFS يعلّم جزيرة، وبعدين multi-source BFS منها لحد التانية.
- Pacific Atlantic Water Flowالمثال المحلول 8. لو حليتها لوحدك، يبقى الفصل ده خلص.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
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 ليها اتجاه؟ ده الفصل الجاي.