Swim in Rising Water

Q: מהי סיבוכיות הזמן של Swim in Rising Water?

O(n² log n) באמצעות האלגוריתם של Dijkstra: כל אחד מ־n² התאים נדחף ונשלף לכל היותר פעם אחת מערימה. לחיפוש בינארי של מפלס המים יש חסם זהה, בערך log2(n²) הצפות, שכל אחת מהן היא O(n²). בשתי השיטות משתמשים בזיכרון של O(n²).

Q: האם אפשר לפתור את Can Swim in Rising Water באמצעות חיפוש בינארי?

כן. היכולת שלך להגיע לצד השני ברמה t משתנה פעם אחת בלבד, מ-false ל-true, בערך התשובה. חיפוש בינארי על t עם מילוי הצפה כבדיקה דורש בערך log2(n²) פעולות מילוי, כלומר 14 עבור רשת בגודל 100 × 100.

Q: האם Union-Find יכול לפתור את Swim in Rising Water?

כן. פתח את התאים לפי סדר הגובה, חבר כל תא חדש לשכנים הפתוחים שלו, ועצור ברגע ששתי הפינות נמצאות באותה קבוצה. הגובה של התא האחרון שפתחת הוא התשובה. מכיוון שכל ערך מ־0 עד n²-1 מופיע פעם אחת, טבלה מגובה לתא מספקת את הסדר בלי למיין.

קשהמסלולים קצרים ביותר ערימה חיפוש בינארי

+10

נתונה לך רשת n × n של גבהים, שבה כל מספר מ-0 עד n²-1 מופיע בדיוק פעם אחת. בזמן t מפלס המים עומד בגובה t בכל מקום, ולכן כל תא שגובהו t או פחות נמצא מתחת למים. מתחילים בתא השמאלי העליון. אפשר לשחות, בלי שיחלוף זמן, לתא שחולק צלע עם התא שלך, כאשר שני התאים מתחת למים. החזר את הזמן המוקדם ביותר שבו אפשר להגיע לתא הימני התחתון.

פונקציה

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

gridinteger-2d-array: הגבהים, כרשימה של n שורות של n מספרים
מחזירהinteger: המועד המוקדם ביותר שבו אפשר להגיע לתא הימני התחתון

אילוצים

n == grid.length == grid[i].length
1 ≤ n ≤ 100
0 ≤ grid[i][j] ≤ n²-1
כל ערך מ־0 עד n²-1 מופיע פעם אחת בדיוק.

דוגמאות

קלט: grid = [[0, 2], [3, 1]]
פלט: 2
הסבר: דרך התא הימני העליון המסלול הוא 0, 2, 1, כשהתא הגבוה ביותר הוא 2. דרך התא השמאלי התחתון המסלול הוא 0, 3, 1, כשהתא הגבוה ביותר הוא 3. בזמן 2 המסלול הראשון נמצא מתחת למים.

שאלת המשך

אם הגבהים יכולים לחזור על עצמם ולהגיע עד 10^9, איזו מהגישות שלך עדיין עובדת ללא שינוי, ועל מה היית מבצע חיפוש בינארי?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

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

העלה את המים צעד אחד בכל פעם

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

קבעו מפלס מים t. מילוי הצפה אחד מהפינה השמאלית העליונה, דרך תאים שגובהם לכל היותר t, יגיד לכם אם אפשר להגיע לפינה הימנית התחתונה. התחילו את t בפינה הגבוהה יותר, max(grid[0][0], grid[n-1][n-1]), מכיוון ששתי הפינות חייבות להיות מתחת למים, והוסיפו 1 עד שהמילוי מצליח לעבור. עליית מפלס המים רק פותחת תאים, לכן המפלס הראשון שבו זה מצליח הוא התשובה.

כל מילוי עולה O(n²), ומפלס המים עשוי לעלות כמעט n² פעמים: ברשת בגודל 100 × 100, עד 10^4 מפלסים × 10^4 תאים, כלומר כ-10^8 ביקורים בתאים.

אלגוריתם

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

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # You cannot finish before the water covers both corners.
    t = max(grid[0][0], grid[n - 1][n - 1])
    # Raise the water one step at a time until a way through opens.
    while not canReach(grid, t):
        t += 1
    return t

חיפוש בינארי בגובה המים

האינטואיציה

בדיקת מילוי ההצפה נכשלת בכל רמה שמתחת לתשובה ומצליחה בכל רמה מהתשובה ואילך. חיפוש בינארי מוצא את נקודת המעבר הזו, בין הפינה העליונה לבין n²-1, שבה כל הרשת נמצאת מתחת למים.

בדוגמה של 5 × 5, lo = 6 ו-hi = 24. רמה 15 נכשלת, ולכן lo = 16. רמות 20, 18, 17 ו-16 מצליחות כולן, והחיפוש מסתיים ב-16 לאחר חמש בדיקות מילוי.

ברשת בגודל 100 × 100 יש 10^4 רמות, ולכן מספיקות בערך 14 בדיקות מילוי כדי להכריע: כ-1.4 × 10^5 ביקורים בתאים במקום 10^8.

אלגוריתם

הגדר את lo לגובה הפינה הגבוהה יותר ואת hi ל־n²-1.
כל עוד lo < hi, חשב את mid = (lo + hi) / 2, בעיגול כלפי מטה.
בצע מילוי הצפה בגובה mid. אם הוא מגיע לפינה הימנית התחתונה, הגדר hi = mid; אחרת הגדר lo = mid + 1.
החזר את lo.

def canReach(grid, t):
    # True when you can swim from the top left to the bottom right with the water at height t.
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    stack = [(0, 0)]
    while stack:
        r, c = stack.pop()
        if r == n - 1 and c == n - 1:
            return True
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
                seen[nr][nc] = True
                stack.append((nr, nc))
    return False


def swimInWater(grid):
    n = len(grid)
    # The answer lies between the higher corner and the highest cell.
    lo = max(grid[0][0], grid[n - 1][n - 1])
    hi = n * n - 1
    # canReach is false below the answer and true from it on: find the first true.
    while lo < hi:
        mid = (lo + hi) // 2
        if canReach(grid, mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

דייקסטרה על התא הגבוה ביותר במסלול

האינטואיציה

תן לכל מסלול עלות: הגובה של התא הגבוה ביותר בו. האלגוריתם של דייקסטרה עדיין עובד, כי הרחבת מסלול לתא בגובה h עולה max(old cost, h), ולעולם לא פחות מהעלות הקודמת. החזק ערימת מינימום של תאים, שממוינת לפי הזמן הזה, והתחל בפינה השמאלית העליונה ב-grid[0][0]. כשהפינה הימנית התחתונה יוצאת מהערימה, הזמן שלה הוא התשובה.

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

הערימה מכילה את גבול האזור שאליו אפשר להגיע, וכל הוצאה מהערימה מעלה את מפלס המים בדיוק במידה הנדרשת כדי להגיע לשם. בדוגמה של 5 × 5, ההוצאות מהערימה הן 0, 1, 2, 3, 4, 5, ואז השער בגובה 16, והפינה הימנית התחתונה יוצאת עם 16.

אלגוריתם

סמן את התא השמאלי העליון ככזה שנראה והכנס אותו לתור עם הזמן grid[0][0].
הוצא מהתור את התא עם הזמן הקטן ביותר t. אם הוא התא הימני התחתון, החזר את t.
עבור כל שכן שעדיין לא נראה, סמן אותו ככזה שנראה והכנס אותו לתור עם הזמן max(t, its height).
חזור משלב 2.

import heapq


def swimInWater(grid):
    n = len(grid)
    seen = [[False] * n for _ in range(n)]
    seen[0][0] = True
    # (time, row, col): the time is the highest cell on the best path found to that cell.
    heap = [(grid[0][0], 0, 0)]
    while True:
        t, r, c = heapq.heappop(heap)
        # Cells leave the heap in order of time, so this is the earliest you can be here.
        if r == n - 1 and c == n - 1:
            return t
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
                # Reached for the first time from the cell with the smallest time:
                # no later route can arrive earlier, so mark it now.
                seen[nr][nc] = True
                heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))

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

התעלמות מהגובה של הפינה עצמה. התשובה היא לפחות grid[0][0] ו־grid[n-1][n-1]: עבור [[3, 0], [1, 2]] היא 3.
הליכה חמדנית אל השכן הנמוך ביותר. המסלול הטוב ביותר עשוי לטפס אל שער ואז להקיף בדרך הארוכה, כמו בדוגמה של 5 × 5.
חיבור הגבהים לאורך המסלול, כמו במסלול קצר ביותר רגיל. הזמן החדש הוא max(t, height), ולא t + height.
שימוש ברקורסיה למילוי הצפה. מסלול מפותל יכול להיות באורך של אלפי תאים, וכך לחרוג מהמגבלה של Python, שהיא 1,000 קריאות מקוננות.

שאלות נפוצות3

מהי סיבוכיות הזמן של Swim in Rising Water?

O(n² log n) באמצעות האלגוריתם של Dijkstra: כל אחד מ־n² התאים נדחף ונשלף לכל היותר פעם אחת מערימה. לחיפוש בינארי של מפלס המים יש חסם זהה, בערך log2(n²) הצפות, שכל אחת מהן היא O(n²). בשתי השיטות משתמשים בזיכרון של O(n²).

האם אפשר לפתור את Can Swim in Rising Water באמצעות חיפוש בינארי?

כן. היכולת שלך להגיע לצד השני ברמה t משתנה פעם אחת בלבד, מ-false ל-true, בערך התשובה. חיפוש בינארי על t עם מילוי הצפה כבדיקה דורש בערך log2(n²) פעולות מילוי, כלומר 14 עבור רשת בגודל 100 × 100.

האם Union-Find יכול לפתור את Swim in Rising Water?

כן. פתח את התאים לפי סדר הגובה, חבר כל תא חדש לשכנים הפתוחים שלו, ועצור ברגע ששתי הפינות נמצאות באותה קבוצה. הגובה של התא האחרון שפתחת הוא התשובה. מכיוון שכל ערך מ־0 עד n²-1 מופיע פעם אחת, טבלה מגובה לתא מספקת את הסדר בלי למיין.

def swimInWater(grid):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

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

הפלט הצפוי

Swim in Rising Water

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

העלה את המים צעד אחד בכל פעם

חיפוש בינארי בגובה המים

דייקסטרה על התא הגבוה ביותר במסלול

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

שאלות נפוצות3

בעיות דומות