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.

רשמו קודם, הרקיבו אחר כך. אם תרקיבו תפוז באמצע סריקה, תא מאוחר יותר באותה סריקה יראה אותו כרקוב וגם יירקב, כך שהריקבון יתקדם בכמה תאים בתוך דקה אחת והשעון יראה זמן נמוך מדי.

זה נכון, אבל כל דקה דורשת סריקה מלאה של rows × cols תאים, ומספר הדקות עשוי להתקרב למספר התאים. ברשת בגודל 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).

אלגוריתם

הכניסו כל תפוז רקוב לתור וספרו את התפוזים הטריים.
הגדירו את מספר הדקות כ־0. כל עוד התור אינו ריק ונשארו תפוזים טריים, הוסיפו 1 למספר הדקות ורשמו את גודל התור k.
הוציאו k תפוזים מהחזית. עבור כל שכן טרי בתוך הרשת, סמנו אותו כרקוב, הפחיתו את מספר התפוזים הטריים והוסיפו אותו לסוף התור.
כשהלולאה מסתיימת, החזירו את מספר הדקות אם מספר התפוזים הטריים הוא 0, אחרת החזירו ‎-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

מלכודות ומקרי קצה

רוב התשובות השגויות כאן סוטות בדקה אחת, או נובעות מהתחלת החיפוש במקום הלא נכון.

סופרים דקה עבור הרמה האחרונה. אם הלולאה ממשיכה עד שהתור מתרוקן, המעבר האחרון שלה לא מרקיב שום דבר ועדיין מוסיף 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. חיפוש לעומק עשוי להגיע לתא במסלול עוקף ארוך לפני שהוא מוצא את המסלול הקצר, ולכן יהיה עליו לבקר מחדש בתאים בכל פעם שהוא מוצא מסלול קצר יותר.

מהו BFS מרובה מקורות?

חיפוש לרוחב שמתחיל עם כמה תאים בתור במרחק 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]]

צפוי