البحث عن أكبر مستطيل: شرح مشكلة المستطيل الأقصى

في مجال الهندسة والخوارزميات، تُعد مشكلة المستطيل الأقصى تحديًا مثيرًا. تسأل هذه المشكلة كيف يمكن العثور بكفاءة على أكبر مستطيل من حيث المساحة يمكن رسمه داخل شبكة مكونة من مساحات مملوءة وفارغة. لهذه المشكلة آثار عملية في مشاريع متعددة، مثل تحديد مواقع النوافذ في تصميم واجهة المستخدم، مما يجعل من الضروري للمطورين والمصممين على حد سواء فهم وتنفيذ حل لها.

بيان المشكلة

تخيل شبكة تمثل شاشة حيث:

• تمثل المنطقة المملوءة بالحرف '#'.
• تمثل المساحة الفارغة بنقطة '.'.

بالنظر إلى هذا التمثيل، فإن المهمة هي تحديد أكبر مستطيل مكون بالكامل من '.' في هذه المساحة المملوءة. على سبيل المثال، قد تبدو شبكة عينة كما يلي:

....................
..............######
##..................
.................###
.................###
#####...............
#####............... 
#####...............

كما يمكنك أن ترى، فإن الهدف هو حساب مساحة أكبر مساحة فارغة مستمرة بين المناطق المملوءة.

فهم الحل

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

1. تمثيل الصفوف كرسوم بيانية

لكل صف في الشبكة، يمكننا حساب مصفوفة ارتفاع تمثل ارتفاع المربعات الفارغة المتجاورة التي تنتهي عند هذا الصف. أساسًا:

• إذا كان العنصر في الشبكة هو '.'، قم بزيادة الارتفاع من الصف أعلاه.
• إذا كان '#'، قم بإعادة تعيين الارتفاع إلى الصفر.

2. حساب مساحة المستطيل لكل صف

بمجرد أن نحصل على مصفوفة ارتفاع لكل صف، الخطوة التالية هي حساب مساحة أكبر مستطيل يمكن تشكيله باستخدام هذه المصفوفة. يمكن القيام بذلك بكفاءة باستخدام بنية بيانات المكدس:

• استعرض مصفوفة الارتفاع.
• استخدم مكدسًا لتتبع مؤشرات الأعمدة.
• كلما تم مواجهة عمود أقل ارتفاعًا، قم بإزالة من المكدس لتحديد الارتفاع وحساب المساحة، مع تحديث أكبر مساحة تم العثور عليها حتى الآن.

3. نظرة عامة على التنفيذ

للتنفيذ الفعال للخوارزمية، اتبع هذه الخطوات:

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

مثال على الكود

إليك مقتطف كود مبسط بلغة بايثون لتوضيح هذه العملية:

def maximalRectangle(matrix):
    if not matrix:
        return 0

    height = [0] * len(matrix[0])
    max_area = 0

    for row in matrix:
        for i in range(len(row)):
            height[i] = height[i] + 1 if row[i] == '.' else 0
        max_area = max(max_area, largestRectangleArea(height))
    return max_area

def largestRectangleArea(heights):
    stack = []
    max_area = 0
    heights.append(0)  # Sentinel

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

الخاتمة

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

للقراءة الإضافية والغوص في التفاصيل، ضع في اعتبارك المقالة المفصلة من مجلة دكتور دobb’s التي ذُكرت من قبل @lassevk، الموجودة هنا. مع معرفة هذه الخوارزمية، يمكنك مواجهة مشكلات مماثلة بثقة في مشاريعك.

كما هو الحال دائمًا، فإن المفتاح لإتقان الخوارزميات هو الممارسة! لذا، حاول تنفيذ هذا الحل بلغة البرمجة المفضلة لديك وانظر كيف يعمل مع تكوينات الشبكات المختلفة.