Rotting Oranges

+10

تحصل على شبكة على شكل قائمة من الصفوف متساوية الطول. كل خلية تكون 0 (فارغة)، أو 1 (برتقالة طازجة)، أو 2 (برتقالة متعفنة). في كل دقيقة، تتعفن كل برتقالة طازجة تشترك في ضلع مع برتقالة متعفنة، سواء كان ذلك من الأعلى أو الأسفل أو اليسار أو اليمين. أعد عدد الدقائق حتى لا تبقى أي برتقالة طازجة، أو -1 إذا تعذّر تعفّن بعض البرتقالات الطازجة. تحتاج الشبكة التي لا تحتوي على برتقالات طازجة في البداية إلى 0 دقيقة.

الدالة

orangesRotting(grid: integer-2d-array) → integer

gridinteger-2d-array: الشبكة، قائمة واحدة من 0 و1 و2 لكل صف
تُرجعinteger: عدد الدقائق حتى لا تبقى أي برتقالة طازجة، أو -1 إذا لم يحدث ذلك مطلقًا

القيود

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
كل صف له الطول نفسه.
كل عنصر grid[i][j] يساوي 0 أو 1 أو 2.

أمثلة

المدخلات: grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
المخرجات: 6
الشرح: بكتابة الخلايا بالشكل (صف، عمود)، يبدأ التعفّن من (0,0) ويتبع المسار الوحيد: (0,1) عند الدقيقة 1، و(0,2) و(1,1) عند الدقيقة 2، و(2,1) عند الدقيقة 3، و(2,0) و(2,2) عند الدقيقة 4، و(2,3) عند الدقيقة 5. البرتقالة عند (1,3) تلامس (2,3) فقط، لذا فهي آخر ما يتعفّن، عند الدقيقة 6.

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

سؤال إضافي

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

الحل

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

حاكِ دقيقةً بدقيقة

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

الفكرة

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

حدّد البرتقالات أولًا، ثم أفسدها. إذا أفسدت برتقالة أثناء الفحص، فستراها خلية لاحقة في الفحص نفسه فاسدةً، وستفسد هي أيضًا؛ وهكذا ينتشر العفن عبر عدة خلايا في دقيقة واحدة، وتكون قيمة الساعة أقل مما ينبغي.

هذه الطريقة صحيحة، لكن كل دقيقة تتطلب فحصًا كاملًا لخلايا الصفوف × الأعمدة، وقد يقترب عدد الدقائق من عدد الخلايا. في شبكة بحجم 150 × 150، حيث تشكّل البرتقالات الطازجة مسارًا متعرّجًا واحدًا والعفن عند بدايته، يحتاج العفن إلى 11,324 دقيقة: أي 11,324 فحصًا لـ 22,500 خلية، ونحو 2.5 × 10^8 عملية فحص للخلايا، معظمها تقريبًا على خلايا لا يمكن أن تتغير.

الخوارزمية

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

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    while True:
        # Find every fresh orange that touches a rotten one right now.
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != 1:
                    continue
                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 grid[nr][nc] == 2:
                        to_rot.append((r, c))
                        break
        if not to_rot:
            break
        # Rot them only after the scan, so the rot moves one step a minute.
        for r, c in to_rot:
            grid[r][c] = 2
        minutes += 1
    for row in grid:
        if 1 in row:
            return -1
    return minutes

بحث العرض أولاً متعدد المصادر حسب المستويات

الفكرة

يهدر المسح وقته على خلايا بعيدة عن موضع النشاط. البرتقالات الوحيدة التي يمكن أن تتعفن عند الدقيقة t+1 هي البرتقالات الطازجة المجاورة للبرتقالات التي تعفنت عند الدقيقة t. لذا احتفظ بهذه البرتقالات وحدها في قائمة انتظار: جبهة التعفّن.

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

بعد ذلك، عالِج الخلايا على مستويات. في بداية الدقيقة، تحتوي قائمة الانتظار على k برتقالات، وهي البرتقالات التي تعفنت في الدقيقة الماضية. أخرج بالضبط k برتقالات من المقدمة؛ ولكل واحدة منها، عفّن جيرانها الطازجين وأضفهم إلى المؤخرة. بعد معالجة البرتقالات k، تكون دقيقة قد مرّت، وتحتوي قائمة الانتظار على الجبهة التالية. في المثال الأول، تكون المستويات {(0,0)}, {(0,1)}, {(0,2), (1,1)}, {(2,1)}, {(2,0), (2,2)}, {(2,3)}, {(1,3)}: ست خطوات بعد البداية، أي ست دقائق.

احسب عدد البرتقالات الطازجة مرة واحدة في البداية، وأنقص العدد كلما تعفنت برتقالة. توقّف فور وصول العدد إلى 0، وإلا فسيضيف المستوى الأخير دقيقة لا تتعفن فيها أي برتقالة، وأعِد -1 إذا فرغت قائمة الانتظار بينما لا يزال العدد أكبر من 0. تدخل كل خلية إلى قائمة الانتظار مرة واحدة على الأكثر، وتُفحَص جيرانها الأربعة، لذا يكون العمل O(rows × cols).

الخوارزمية

ضع كل برتقالة فاسدة في طابور، واحسب عدد البرتقالات الطازجة.
اضبط minutes على 0. طالما أن الطابور غير فارغ وما زالت هناك برتقالات طازجة، أضف 1 إلى minutes وسجّل حجم الطابور k.
خذ k برتقالات من المقدمة. لكل برتقالة مجاورة طازجة داخل الشبكة، اجعلها فاسدة، وقلّل عدد البرتقالات الطازجة، ثم أضفها إلى المؤخرة.
عند انتهاء الحلقة، أعد minutes إذا كان عدد البرتقالات الطازجة 0، وإلا else -1.

from collections import deque


def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    # Every orange that is rotten at minute 0 starts in the queue.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        minutes += 1
        # The queue holds exactly the oranges that went rotten last minute.
        # Rot their fresh neighbours; those become the next minute's queue.
        for _ in range(len(queue)):
            r, c = queue.popleft()
            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 grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
    return minutes if fresh == 0 else -1

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

معظم الإجابات الخاطئة هنا يكون فيها فرق دقيقة واحدة، أو تنتج عن بدء البحث من المكان الخطأ.

احتساب دقيقة للمستوى الأخير. إذا استمرت الحلقة حتى يصبح الطابور فارغًا، فلن يؤدي تكرارها الأخير إلى تعفّن أي برتقالة، ومع ذلك سيضيف دقيقة واحدة. توقّف فور عدم بقاء أي برتقالة طازجة.
البحث انطلاقًا من كل برتقالة متعفّنة على حدة. يستحوذ البحث الأول على كل برتقالة يصل إليها وفق ساعته الخاصة، لذا فإن مصدرين يُفترض أن يلتقيا في المنتصف يعطيان زمنًا أطول من اللازم: تستغرق [[2, 1, 1, 1, 1, 1, 1, 2]] 3 دقائق، لا 6.
جعل البرتقال يتعفّن أثناء المسح في الطريقة التي تحسب دقيقةً بدقيقة. عندئذٍ ترى خليةٌ تأتي لاحقًا في المسح نفسه الخلاياَ على أنها متعفّنة، فينتشر التعفّن عبر عدة خلايا في دقيقة واحدة.
إرجاع -1 لعدم وجود برتقالة متعفّنة. إذا لم توجد برتقالة طازجة أيضًا، فلا شيء يحتاج إلى الحدوث: تُرجع [[0]] القيمة 0. فقط البرتقالات الطازجة التي لا تتعفّن أبدًا تجعل الإجابة -1.
وضع علامة على البرتقالة بأنها متعفّنة عند إخراجها من الطابور بدلًا من إدخالها إليه. عندها تُضاف البرتقالة المجاورة لبرتقالتين متعفّنتين إلى الطابور مرتين، وينخفض عدد البرتقالات الطازجة إلى ما دون الصفر.
البحث بالعمق أولًا. فهو يتبع مسارًا واحدًا إلى أقصى عمق ممكن، لذا فإن وصوله إلى برتقالة للمرة الأولى لا يخبرنا بشيء عن الدقيقة التي تتعفّن فيها تلك البرتقالة.

أسئلة شائعة4

ما التعقيد الزمني لمسألة تعفّن البرتقال؟

‏O(rows × cols) باستخدام البحث بعرض أول. يفحص المرور الأول كل خلية مرة واحدة، ويدخل كل برتقالة برتقالية إلى قائمة الانتظار مرة واحدة على الأكثر، وتفحص أربعة جيران. تستهلك قائمة الانتظار مساحة O(rows × cols) في أسوأ الحالات، عندما تكون الشبكة ممتلئة بالبرتقال الفاسد.

لماذا نستخدم البحث بالعرض أولًا (BFS) وليس البحث بالعمق أولًا (DFS) في مسألة تعفّن البرتقال؟

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

ما هو البحث بالعرض متعدد المصادر؟

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

هل يمكنك حل مسألة البرتقال المتعفّن دون تغيير الشبكة؟

نعم. احتفظ بمصفوفة منفصلة للعناصر التي تمت زيارتها، وتحقّق منها بدلًا من كتابة 2 في الشبكة. يتطلب ذلك ذاكرة إضافية بحجم O(rows × cols)، وهي ذاكرة قد يحتاج إليها الطابور على أي حال. في اللغات التي تمرّر الشبكة بالمرجع، تؤدي الكتابة فيها أيضًا إلى تغيير شبكة المستدعي، وقد يسألك المحاور عن ذلك.

Python

def orangesRotting(grid):
    # اكتب الشيفرة هنا

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

الحالة 1

الحالة 2

الحالة 3

المدخلات

grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]

المتوقع