Longest Increasing Path in a Matrix

صعبالبرمجة الديناميكية الرسوم البيانية الترتيب الطوبولوجي

+10

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

الدالة

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: شبكة من القيم، على شكل قائمة من الصفوف المتساوية في الطول
تُرجعinteger: عدد الخلايا في أطول مسار متزايد تمامًا

القيود

1 ≤ m, n ≤ 100، حيث m = matrix.length وn = matrix[i].length
يبلغ طول كل صف n.
0 ≤ matrix[i][j] ≤ 2³¹-1

أمثلة

المدخلات: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
المخرجات: 7
الشرح: يسير المسار 3، 4، 5، 6، 7، 8، 9 نزولًا على العمود الأيمن، ثم يسارًا على طول الصف السفلي، ثم صعودًا في العمود الأوسط، ثم يسارًا إلى 9 في الزاوية: 7 خلايا. وتكون نتيجة أصغر قيمة أسوأ: فمن 1، أفضل المسارات هي 1، 2، 7، 8، 9 و1، 6، 7، 8، 9، ويتكوّن كل منها من 5 خلايا.

+18 اختبارات مخفية عند الإرسال

سؤال إضافي

هل يمكنك أيضًا إرجاع خلايا أحد أطول المسارات، وليس طوله فقط؟

الحل

ارسم سهمًا من كل خلية إلى كل خلية مجاورة لها تحمل قيمة أكبر. تزداد القيم على امتداد كل سهم، لذا لا يمكن لأي سلسلة من الأسهم أن تعود إلى نقطة بدايتها: الشبكة رسم بياني موجّه لا دوري، والمطلوب هو إيجاد أطول مسار فيه. في رسم بياني عام، يكون هذا السؤال مستحيلًا عمليًا عند المدخلات الكبيرة، لكن في غياب الدورات، يعتمد أطول مسار من خلية على تلك الخلية وحدها، لذا تحسبه مرة واحدة لكل خلية، وتُختزل المسألة بأكملها إلى O(m × n). تحسبه عملية البحث العميق مع التخزين المؤقت من الأعلى إلى الأسفل؛ أما تقشير الشبكة بدءًا من قممها، أي تطبيق خوارزمية Kahn بالعكس، فيحسبه من الأسفل إلى الأعلى.

اتبع كل مسار تصاعدي

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

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

لا يحتاج المسار إلى مجموعة للخلايا التي تمت زيارتها. فالقيم تزداد عند كل خطوة، لذا لا يمكن للمسار العودة إلى خلية: إذ سيتعين عليه الرجوع إلى قيمة تلك الخلية كي يقف عليها مجددًا. احتفظ بالمسارات في مكدس من عناصر بالشكل (cell, length). يؤدي إخراج عنصر من المكدس إلى إنهاء مسار عند تلك الخلية، وتؤدي إضافة جيرانها ذوي القيم الأكبر إلى تمديده.

هذه الطريقة صحيحة، لكنها بطيئة للغاية، لأن المسارات تتشعب. في شبكة 100 × 100 تكون فيها قيمة كل خلية هي مجموع رقم صفها ورقم عمودها، تمثل كل خطوة إلى اليمين أو إلى الأسفل خطوة صعود، ويزيد عدد المسارات التي تبدأ من الزاوية العلوية اليسرى وحدها على 10^58. والأسوأ أن المسار من أي خلية يُعاد حسابه كلما مرّ بها مسار آخر، وهذا هو الهدر الذي يزيله النهج التالي.

الخوارزمية

لكل خلية، أضف (تلك الخلية، 1) إلى المكدس.
أخرج مدخلًا (الخلية، الطول)، وحدّث الإجابة باستخدام الطول.
أضف (الخلية المجاورة، الطول + 1) لكل خلية مجاورة داخل الشبكة ذات قيمة أكبر بصرامة.
كرّر حتى يصبح المكدس فارغًا، ثم انتقل إلى خلية البداية التالية.
أعِد أكبر طول تمّت رؤيته.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

البحث بالعمق أولًا مع التخزين المؤقت باستخدام مكدس خاص بك

الفكرة

لتكن best[cell] عدد الخلايا في أطول مسار متزايد يبدأ من تلك الخلية. ينتهي المسار عندها، أو تكون خطوته التالية إلى جار أكبر ويواصل على طول أطول مسار من ذلك الجار. لذا تكون best[cell] = 1 + max(best[nb]) بين الجيران الأكبر nb، أو 1 إذا لم يوجد أيٌّ منهم. ومن الآمن إعادة استخدام هذه القيمة بسبب البنية غير الدورية: فجميع الخلايا التي تسبق cell على أي مسار أصغر منها، لذا لا يمكن أن تظهر بعدها، كما أن أفضل امتداد من cell هو نفسه مهما كانت طريقة الوصول إليها. احسب best لكل خلية مرة واحدة، وخزّنها، فتتحول شجرة المسارات الأسية إلى زيارة واحدة لكل خلية.

في المثال الأول، ليس للخلية 9 أي جار أكبر، لذا تكون قيمة best فيها 1. ثم تحصل 8 على 2، و7 على 3، و6 و2 على 4، و5 و1 على 5، و4 على 6، و3 على 7، وهي الإجابة. تفحص كل خلية جيرانها الأربعة، لذا يكون العمل O(m × n).

الشفرة الطبيعية递 هي عودية: دالة تعيد best لخلية، وتستدعي نفسها لكل جار أكبر. يساوي عمق الاستدعاءات طول المسار الذي تتبعه، وتسمح القيود بمسار يمر عبر كل خلية: فالقيم التي تتعرج ذهابًا وإيابًا عبر شبكة بحجم 100 × 100 تكوّن مسارًا واحدًا من 10,000 خلية، بينما تتوقف Python افتراضيًا عند 1,000 استدعاء متداخل. تنفّذ الشفرة أدناه العودية بنفسها، لذا لا يوجد مسار أطول من أن تتمكن من التعامل معه. احتفظ بمكدس من الخلايا، ولكل خلية عدد الاتجاهات الأربعة التي جرّبتها. انظر إلى الخلية في أعلى المكدس: إذا بقي لها اتجاه، فجرّبه، وأضف الجار هناك إلى المكدس إذا كان أكبر ولم يكن قد اكتمل بعد. عندما تُجرَّب الاتجاهات الأربعة كلها، يكون كل جار أكبر قد اكتمل، لذا أزل الخلية من المكدس واضبط قيمة best لها. هذا هو بالضبط الترتيب الذي سيتبعه الاستدعاء العودي.

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

الخوارزمية

املأ best بالقيمة 0 (غير معروف بعد)، وعداد الاتجاهات بالقيمة 0 لكل خلية.
لكل خلية تكون قيمة best فيها 0، ادفعها إلى المكدس.
انظر إلى الخلية في أعلى المكدس. إذا كان لها اتجاه متبقٍ، فزِد عدادها وادفع الخلية المجاورة في ذلك الاتجاه إذا كانت داخل الشبكة، وأكبر، ولم تنتهِ معالجتها.
إذا جُرّبت الاتجاهات الأربعة كلها، فأخرج الخلية من المكدس واجعل best تساوي 1 زائد أكبر قيمة best بين جيرانها الأكبر، أو 1 إذا لم يكن لها أيٌّ منهم.
أعِد أكبر قيمة best.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

أزل الشبكة عن قممها

الفكرة

اعكس اتجاه البرمجة الديناميكية وابنِها من القيم العليا إلى الأدنى، كما تبني خوارزمية Kahn ترتيبًا طوبولوجيًا. سمِّ الخلية قمةً إذا لم يكن أي جار لها أكبر منها. لا يمكن للمسار انطلاقًا من قمة أن يتحرك، لذا يتكون من خلية واحدة. أزِل جميع القمم دفعة واحدة: هذه هي الطبقة 1. الآن فقدت بعض الخلايا آخر جار أكبر منها، فأصبحت قممًا في الجزء المتبقي. أزِلها في الطبقة 2، وتابع بهذه الطريقة حتى تصبح الشبكة فارغة. عدد الطبقات هو الإجابة.

السبب: تقع الخلية في الطبقة k بالضبط عندما يكون أطول مسار يبدأ منها مكوّنًا من k خلايا. تُزال الخلية في الجولة التي تلي إزالة آخر جار أكبر منها، لذا فإن طبقتها تساوي 1 زائد أعلى طبقة بين جيرانها الأكبر منها، وهي الصيغة best[cell] = 1 + max(best[nb]) من النهج السابق. تنتمي أعمق طبقة إلى بداية أطول مسار.

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

للعثور على الطبقة التالية بسرعة، احسب لكل خلية عدد جيرانها الأكبر منها الذين ما زالوا موجودين. تؤدي إزالة خلية إلى إنقاص العدد لكل جار أصغر منها مباشرةً، وأي عدد يصل إلى 0 يضع ذلك الجار في الطبقة التالية. تُزال كل خلية مرة واحدة، ويُنظر إلى كل زوج من الجيران عددًا ثابتًا من المرات، لذا يكون العمل O(m × n)، من دون مكدس أو استدعاء递帰ي.

الخوارزمية

لكل خلية، احسب عدد الجيران ذوي القيم الأكبر.
ضع كل خلية يكون عددها 0 في الطبقة الحالية.
ما دامت الطبقة غير فارغة، أضف 1 إلى عدد الطبقات. ولكل خلية فيها، أنقص عدد كل جار أصغر منها تمامًا، وضع الجار الذي يصل عدده إلى 0 في الطبقة التالية.
اجعل الطبقة التالية هي الحالية وكرّر.
أعِد عدد الطبقات.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

أخطاء شائعة وحالات حدّية

تأتي الأخطاء هنا من كلمة «بصرامة»، ومن الاستدعاء العودي العميق، ومن عادات انتقلت من مسائل شبكات أخرى.

المقارنة باستخدام >= بدلًا من >. عندما تكون هناك قيمتان متجاورتان تساوي كل منهما 4، تحسب كل واحدة منهما خطوة صعود من الأخرى، فتشكّل الأسهم حلقة، وتتأرجح خوارزمية القوة الغاشمة ذهابًا وإيابًا إلى الأبد، بينما تقرأ عملية بحث مع تخزين النتائج طولًا لا يزال قيد الحساب.
الاستدعاء العودي على مسارات طويلة جدًا. يتعمق البحث العودي بعدد من الاستدعاءات يساوي طول المسار، وتسمح القيود بمسار يمر بكل خلية: فالقيم التي تتعرج ذهابًا وإيابًا عبر شبكة من 100 × 100 خلية تكوّن مسارًا من 10,000 خلية، أي عشرة أضعاف الحد الافتراضي في Python البالغ 1,000 استدعاء متداخل. تحتاج المسارات بهذا الطول إلى بحث تكراري باستخدام مكدس خاص بك، أو إلى رفع حد الاستدعاء العودي (sys.setrecursionlimit في Python)، لكن حتى الحد المرتفع جدًا قد يتسبب في تجاوز سعة مكدس المفسّر نفسه.
تخطّي الخلايا التي زرتها من قبل، كما تفعل خوارزمية ملء المساحة. الوصول إلى خلية مكتملة ليس طريقًا مسدودًا: طولها المخزّن هو بالضبط ما تحتاج إليه الخلية الحالية. اقرأه ولا تتخطّها.
البدء من أصغر قيمة فقط. في المثال الأول، تعطي القيمة 1 مسارًا من 5 خلايا، لكن الإجابة، وهي 7، تبدأ من القيمة 3. يمكن أن يبدأ أطول مسار من أي خلية ليس لها جار أصغر منها، وقد توجد خلايا كثيرة كهذه.
إرجاع 0. كل خلية تشكّل مسارًا من خلية واحدة، لذا تكون الإجابة 1 في شبكة قيمها متساوية أو في شبكة من 1 × 1 خلية. اجعل طول المسار لكل خلية يبدأ من 1، لا من 0.
في أسلوب التقشير، خفض العدد عند وجود جار مساوٍ. الجار الأصغر فقط هو الذي فقد جارًا أكبر منه.

أسئلة شائعة4

ما هو التعقيد الزمني لمسألة أطول مسار متزايد في مصفوفة؟

زمن قدره O(m × n) ومساحة قدرها O(m × n) باستخدام البحث بالعمق أولًا مع التخزين المؤقت أو التقشير الطوبولوجي. تُعالَج كل خلية من الخلايا البالغ عددها m × n مرة واحدة، وتفحص جيرانها الأربعة عددًا ثابتًا من المرات، كما تحتفظ كل طريقة برقم واحد لكل خلية. أما تجربة كل المسارات انطلاقًا من كل خلية فهي أسية بدلًا من ذلك: في شبكة بحجم 100 × 100، حيث تكون قيمة كل خلية مساوية لرقم صفها زائد رقم عمودها، يغادر الزاوية العلوية اليسرى أكثر من 10^58 مسارًا.

لماذا لا تحتاج هذه المسألة إلى مجموعة للعُقد التي تمت زيارتها؟

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

هل تُعدّ مسألة أطول مسار متزايد في مصفوفة مسألة برمجة ديناميكية أم مسألة رسوم بيانية؟

كلاهما. إنها أطول مسار في رسم بياني موجه لا دوري، وهذا يُحل بالبرمجة الديناميكية وفق ترتيب طوبولوجي: إجابة الخلية هي 1 زائد أفضل إجابة بين جيرانها ذوي القيم الأكبر. يملأ البحث بعمق أول مع التخزين المؤقت الجدول بترتيب انتهاء البحث من الخلايا، بينما يملأه التقشير الطوبولوجي طبقةً بعد طبقة بدءًا من القمم. ويؤدي ترتيب الخلايا تنازليًا حسب قيمها إلى ترتيب ثالث صالح، بتكلفة O(m × n × log(m × n)) لعملية الفرز.

ما الفرق بين هذا وأطول تتابع متزايد؟

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

Python

def longestIncreasingPath(matrix):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

المتوقع

Longest Increasing Path in a Matrix

الدالة

القيود

أمثلة

تلميحات

الحل

اتبع كل مسار تصاعدي

البحث بالعمق أولًا مع التخزين المؤقت باستخدام مكدس خاص بك

أزل الشبكة عن قممها

أخطاء شائعة وحالات حدّية

أسئلة شائعة4

مسائل مشابهة