شرح خوارزمية تعبئة الفيضان

تعبئة الفيضان هي خوارزمية تستخدم بشكل أساسي لتحديد منطقة محدودة متصلة بعقدة معينة في مصفوفة متعددة الأبعاد. إنه تشابه وثيق مع أداة الجرافة في برامج الطلاء.

أكثر طرق تنفيذ الخوارزمية اقترابًا منها هي دالة تكرارية قائمة على التكديس ، وهذا ما سنتحدث عنه بعد ذلك.

كيف يعمل؟

المشكلة بسيطة جدًا وعادة ما تتبع الخطوات التالية:

  1. اتخذ موقف نقطة البداية.
  2. حدد ما إذا كنت تريد الذهاب في 4 اتجاهات ( شمال ، جنوب ، غرب ، شرق ) أو 8 اتجاهات ( شمال ، جنوب ، غرب ، شرق ، شمال غربي ، شمال شرقي ، جنوب شرقي ).
  3. اختر لونًا بديلاً ولونًا مستهدفًا.
  4. سافر في تلك الاتجاهات.
  5. إذا كانت القطعة التي تهبط عليها هدفًا ، فاستبدلها باللون المختار.
  6. كرر 4 و 5 حتى تكون في كل مكان داخل الحدود.

لنأخذ المصفوفة التالية كمثال:

نص بديل

المربع الأحمر هو نقطة البداية والمربعات الرمادية هي ما يسمى بالجدران.

لمزيد من التفاصيل ، إليك جزء من الكود يصف الوظيفة:

int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color) 

كما رأينا أعلاه ، فإن نقطة البداية هي (4،4). بعد استدعاء الوظيفة لإحداثيات البداية x = 4 و y = 4 ، يمكنني البدء في التحقق مما إذا كان لا يوجد جدار أو لون على الفور. إذا كان هذا صحيحًا ، فقم بتمييز البقعة "بلون" واحد وابدأ في فحص المربعات الأخرى.

إذا اتجهنا جنوبًا ، سنصل إلى النقطة (5،4) وستعمل الوظيفة مرة أخرى.

مشكلة التمرين

لطالما اعتبرت أن حل مشكلة (أو أكثر) باستخدام خوارزمية تم تعلمها حديثًا هو أفضل طريقة لفهم المفهوم تمامًا.

إذن هذه واحدة:

بيان:

في مصفوفة ثنائية الأبعاد ، يتم إعطاؤك عدد n من "الجزر" . حاول العثور على أكبر مساحة في الجزيرة ورقم الجزيرة المقابل. 0 يشير إلى الماء وأي علامة أخرى بين 1 و n تشير إلى مربع واحد من السطح المقابل للجزيرة x.

إدخال

  • ن - عدد الجزر.
  • ل ، ج - أبعاد المصفوفة.
  • المقبل ل خطوط، ج أعداد إعطاء لتر عشر صف من المصفوفة.

انتاج |

  • ط - رقم الجزيرة ذات المساحة الأكبر.
  • A - منطقة ط "عشر الجزيرة.

مثال:

لديك المدخلات التالية:

2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2

التي سوف تحصل على الجزيرة لا. 2 كأكبر جزيرة بمساحة 5 مربعات.

تلميحات

المشكلة سهلة للغاية ، ولكن إليك بعض التلميحات:

1. Use the flood-fill algorithm whenever you encounter a new island. 2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).