Flood Fill
الصورة عبارة عن شبكة من الأعداد الصحيحة، حيث يمثّل كل عدد لون بكسل واحد. تحصل على الصورة في صورة قائمة من الصفوف، وبكسل بداية في الصف sr والعمود sc، وcolor جديد. أعد تلوين المنطقة التي تضم بكسل البداية: كل بكسل له لون بكسل البداية ويمكن الوصول إليه منه بالتحرك إلى الأعلى أو الأسفل أو اليسار أو اليمين عبر بكسلات من اللون نفسه. أعد الصورة بعد إعادة التلوين.
الدالة
- imageinteger-2d-array
- الصورة على هيئة قائمة من الصفوف، رقم واحد لكل بكسل
- srinteger
- صفّ البكسل الأولي، مع بدء العدّ من 0
- scinteger
- عمود البكسل الابتدائي، مع احتساب العد من 0
- colorinteger
- اللون الجديد للمنطقة
- تُرجعinteger-2d-array
- الصورة بعد إعادة رسم المنطقة
القيود
1 ≤ image.length ≤ 801 ≤ image[i].length ≤ 80- لكل صف الطول نفسه.
0 ≤ image[i][j], color ≤ 655350 ≤ sr < image.lengthو0 ≤ sc < image[0].length
أمثلة
- المدخلات
- image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
- المخرجات
- [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
- الشرح
- تحتوي خانة البداية على اللون 1. يرتبط بها الرقم 1 الموجود على يمينها، والأرقام 1 نزولًا على العمود الأيسر وعلى طول الصف السفلي، والرقم 1 فوق الزاوية السفلية اليمنى، لذا تصبح الأرقام السبعة كلها 5. أما الرقمان 0 فلونهما مختلف، ويظلان كما هما.
- المدخلات
- image = [[3, 3, 3], [3, 7, 3], [3, 3, 3]]sr = 1sc = 1color = 7
- المخرجات
- [[3, 3, 3], [3, 7, 3], [3, 3, 3]]
- الشرح
- يكون اللون 7 موجودًا عند البداية بالفعل، لذا فإن تلوين منطقته باللون 7 لا يغيّر شيئًا. تعود الصورة كما كانت، وتبقى حلقة الأرقام 3 دون تغيير لأنها بلون مختلف.
- المدخلات
- image = [[2, 2, 4, 4], [4, 2, 2, 4], [4, 4, 2, 2]]sr = 2sc = 3color = 9
- المخرجات
- [[9, 9, 4, 4], [4, 9, 9, 4], [4, 4, 9, 9]]
- الشرح
- تشكل الأرقام 2 درجًا يبدأ من الزاوية السفلية اليمنى ويصعد إلى الزاوية العلوية اليسرى، بحيث تشترك كل درجة في ضلع مع الدرجة التالية، لذا تتحول الأرقام الستة كلها إلى 9. وتنقسم الأرقام 4 إلى مجموعتين منفصلتين، وتحتفظ بلونها.
+18 اختبارات مخفية عند الإرسال
سؤال إضافي
كيف سيتغير الحل إذا اعتُبرت وحدات البكسل التي تتلامس عند الزوايا فقط متصلة أيضًا؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أي وحدات بكسل يمكن أن يتغير لونها؟ فقط تلك التي لها اللون نفسه الذي لوحدة البكسل الابتدائية، وفقط إذا كان هناك مسار من ذلك اللون يصل بينها وبينها.
اعتبر كل بكسل عقدة، وصِل بين بكسلين عندما يشتركان في ضلع ويكون لوناهما هو اللون الابتدائي. المنطقة هي كل ما تصل إليه انطلاقًا من نقطة البداية، لذا فإن أي بحث في الرسم البياني يعثر عليها.
احتفِظ بمكدّس من وحدات البكسل التي ما زال عليك النظر إليها. لوّن وحدة البكسل لحظة دفعها إلى المكدّس، حتى لا تعود وحدة البكسل الملوّنة مطابقة، وبالتالي لن تُدفَع مرة أخرى. تحقّق أولًا مما إذا كان اللون الجديد يساوي اللون القديم.
الحل
المنطقة جزء متصل من رسم بياني: البكسلات هي العقد، وأي بكسلين من اللون الأصلي يتشاركان ضلعًا يكونان متصلين. أي عملية بحث تبدأ من البكسل المحدد ولا تمر إلا عبر ذلك اللون ستعثر على المنطقة بأكملها. الفخّان هما صورة يكون فيها اللون الجديد مساويًا للون القديم، ومنطقة طويلة متعرجة تؤدي إلى تعطل البحث العودي.
البحث بالعمق أولًا باستخدام الاستدعاء الذاتي
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
اكتب دالة paint(r, c) تنفّذ أمرًا صغيرًا واحدًا: إذا كان (r, c) داخل الصورة ولا يزال يحمل اللون القديم، فلوّنه باللون الجديد واستدعِ الدالة على جيرانه الأربعة. ينتشر استدعاء واحد على بكسل البداية عبر المنطقة كلها، لأن كل بكسل فيها متصل بنقطة البداية عبر مسار من البكسلات ذات اللون القديم، وتتبع الاستدعاءات ذلك المسار.
إن تلوين البكسل قبل الاستدعاءات الأربعة هو ما يمنع الانتشار من الدوران في حلقات: فعندما يستدعي أحد الجيران الدالة مجددًا على بكسل ملوّن، لن يعود اللون مطابقًا، فينتهي الاستدعاء فورًا. لا ينجح ذلك إلا عندما يختلف اللون الجديد عن اللون القديم، لذا تحقّق من ذلك أولًا وأعِد الصورة دون تغيير عندما يتساويان.
حجم العمل هو O(m × n)، لكن نقطة الضعف هي مكدس الاستدعاءات. يصل عمق الاستدعاء التعاودي إلى طول المسار الذي يتبعه. ثعبان بعرض بكسل واحد يمر عبر صورة بحجم 80 × 80 يبلغ طوله نحو 3,200 بكسل، لذا تتداخل الاستدعاءات حتى عمق يقارب 3,200. يتوقف Python افتراضيًا عند 1,000 استدعاء ويُصدر خطأ، ولهذا لا يكتمل هذا النهج في أكبر الاختبارات. تسمح اللغات الأخرى باستدعاءات أعمق، لكن صورة أكبر ستستنفد مكدس الاستدعاءات فيها أيضًا.
الخوارزمية
- اقرأ
old = image[sr][sc]. إذا كانت قيمةoldتساويcolor، فأعِد الصورة. - عرّف
paint(r, c): أعد التنفيذ إذا كان(r, c)خارج الصورة أو لم يكن لونهاold. - وإلا، فعيّن
image[r][c] = colorواستدعِpaintللبكسلات التي فوقه وتحته ويساره ويمينه. - استدعِ
paint(sr, sc)وأعِد الصورة.
def floodFill(image, sr, sc, color):
old = image[sr][sc]
if old == color:
return image
rows, cols = len(image), len(image[0])
def paint(r, c):
# Stop outside the image and at any pixel that is not the old color.
if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
return
image[r][c] = color
paint(r + 1, c)
paint(r - 1, c)
paint(r, c + 1)
paint(r, c - 1)
paint(sr, sc)
return imageالبحث بالعمق أولًا باستخدام مكدس صريح
الفكرة
نفّذ عملية الانتشار نفسها، لكن احتفظ بالبكسلات التي لا تزال بحاجة إلى الزيارة في مكدس خاص بك بدلًا من مكدس الاستدعاءات. لوّن بكسل البداية وأضِفه إلى المكدس. أخرج بكسلًا من المكدس، وافحص جيرانه الأربعة، ولكل جار يقع داخل الصورة وما زال يحمل اللون القديم، لوّنه وأضِفه إلى المكدس. عندما يصبح المكدس فارغًا، تكون قد لوّنت المنطقة بأكملها.
لوّن البكسل عند إضافته إلى المكدس، وليس عند إخراجه منه. فالبكسل الملوّن لم يعد يحمل اللون القديم، لذا يُستخدم فحص اللون أيضًا للتحقق مما إذا كان قد تمت زيارته: لا يدخل أي بكسل إلى المكدس مرتين، ولا تحتاج إلى شبكة علامات منفصلة. وكما في النسخة العودية، يتطلب ذلك أن يختلف اللون الجديد عن اللون القديم، لذا أعد الصورة دون تغيير عندما يتساويان.
يُضاف كل بكسل في المنطقة إلى المكدس مرة واحدة، وتُفحص جيرانه الأربعة، لذا فإن الزمن هو O(m × n). ويحتوي المكدس على بكسلات المنطقة بحد أقصى. وهو موجود في الذاكرة العادية، لذا لا تمثّل منطقة متعرجة تضم 3,200 بكسل أي مشكلة، بينما نفدت سعة مكدس الاستدعاءات في النسخة العودية.
الخوارزمية
- اقرأ
old = image[sr][sc]. إذا كانoldيساويcolor، فأعِد الصورة. - لوّن
(sr, sc)وادفعه إلى المكدس. - أخرج بكسلًا من المكدس وانظر إلى جيرانه الأربعة.
- لكل جار داخل الصورة يكون لونه
old، لوّنه وادفعه إلى المكدس. - عندما يصبح المكدس فارغًا، أعِد الصورة.
def floodFill(image, sr, sc, color):
old = image[sr][sc]
# Painting a region its own color changes nothing. Returning here also
# stops the search from pushing the same cells forever.
if old == color:
return image
rows, cols = len(image), len(image[0])
image[sr][sc] = color
stack = [(sr, sc)]
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and image[nr][nc] == old:
# Paint on push: a painted cell no longer matches old,
# so it can never be pushed twice.
image[nr][nc] = color
stack.append((nr, nc))
return image
أخطاء شائعة وحالات حدّية
تنتج معظم الإجابات الخاطئة عن حالة اللون نفسها، أو الخروج عن حدود الصورة، أو استخدام الاستدعاء الذاتي على منطقة طويلة.
- نسيان الحالة التي تكون فيها قيمة
colorمساوية للون نقطة البداية. عندها لا يغيّر التلوين شيئًا، لذا فإن البحث الذي يستخدم اللون علامةً على الزيارة سيدفع وحدات البكسل نفسها إلى المكدس إلى الأبد. - قراءة
image[sr][sc]بعد تلوينها. احفظ اللون القديم أولًا، وإلا فستقارن كل بكسل مجاور باللون الجديد. - احتساب وحدات البكسل المجاورة قطريًا. وحدات البكسل التي لا تتلامس إلا عند زاوية ليست متصلة.
- التحقق من لون البكسل المجاور قبل التحقق من وقوعه داخل الصورة. اختبر
0 ≤ row < rowsو0 ≤ col < colsأولًا. - استخدام الاستدعاء الذاتي على صورة كبيرة. فالمسار الذي يبلغ عرضه بكسلًا واحدًا عبر صورة بحجم 80 × 80 يبلغ طوله نحو 3,200 بكسل، وهو عمق كافٍ لتجاوز حد الاستدعاء الذاتي في Python.
- تلوين كل بكسل يحمل اللون القديم في الصورة كلها. يجب أن تحتفظ وحدات البكسل بهذا اللون إذا كانت معزولة عن نقطة البداية.
أسئلة شائعة4
ما هو التعقيد الزمني لخوارزمية الملء التدفقي؟
O(m × n) لصورة تتكون من m صفوف وn أعمدة. يُدفَع كل بكسل في المنطقة إلى المكدس مرة واحدة، ويُفحَص جيرانه الأربعة، بينما لا تُفحَص البكسلات خارج المنطقة إلا بوصفها جيرانًا. يمكن أن يحتوي المكدس على ما يصل إلى m × n بكسلًا عندما تكون الصورة بأكملها منطقة واحدة.
هل ينبغي أن تستخدم BFS أم DFS لملء المناطق؟
كلاهما صالح، ويستغرق كلٌّ منهما زمنًا قدره O(m × n). المنطقة هي نفسها بصرف النظر عن ترتيب زيارتها، لذا ترسم قائمة الانتظار (البحث بعرض الشجرة) والمكدس (البحث بعمق الشجرة) البكسلات نفسها. اختر الطريقة الأقصر كتابةً بلغتك، وتجنّب الاستدعاء التعاودي مع الصور الكبيرة.
لماذا تستمر خوارزمية التعبئة بالغمر في التكرار إلى ما لا نهاية عندما يكون اللون الجديد هو نفسه اللون القديم؟
يعتبر الحل المعتاد أن «ما زال يحمل اللون القديم» تعني «لم تتم زيارته بعد». عندما يكون اللون الجديد مساويًا للون القديم، فإن تلوين بكسل لا يغيّره، لذا تضيفه البكسلات المجاورة مجددًا إلى المكدس ولا ينتهي البحث أبدًا. يؤدي التحقق من هذه الحالة أولًا وإرجاع الصورة إلى إصلاح المشكلة، وتكون الصورة دون تغيير هي الإجابة الصحيحة.
هل يمكن حلّ التعبئة بالفيض باستخدام الاستدعاء الذاتي؟
نعم، الدالة التي تلوّن بكسلًا وتستدعي نفسها على كل جار له باللون القديم صحيحة. تكمن المخاطرة في العمق: يصل عمق الاستدعاء الذاتي إلى طول أطول مسار يتبعه البحث، وقد يصل في منطقة متعرجة إلى آلاف الاستدعاءات. تنفّذ المكدّسة الصريحة العمل نفسه من دون هذا الحد.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
Python
def floodFill(image, sr, sc, color):
# اكتب الكود هناالحالة 1
الحالة 2
الحالة 3
المدخلات
image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]] sr = 0 sc = 0 color = 5
المتوقع
[[5, 5, 0], [5, 0, 5], [5, 5, 5]]