Swim in Rising Water
ניתנת לך רשת n × n של גבהים, שבה מופיע כל מספר מ־0 עד n²-1 בדיוק פעם אחת, כרשימה של שורות. הגשם מתחיל בזמן 0, ובזמן t המים עומדים בגובה t בכל מקום, כך שכל תא שגובהו t או פחות נמצא מתחת למים. את מתחילה בתא השמאלי העליון. אפשר לשחות מתא לתא שחולק איתו צלע כאשר שניהם מתחת למים, והשחייה אינה אורכת זמן. החזירי את הזמן המוקדם ביותר שבו אפשר להגיע לתא הימני התחתון.
פונקציה
- gridinteger-2d-array
- הגבהים, כרשימה של n שורות שכל אחת מהן כוללת n מספרים
- מחזירהinteger
- המועד המוקדם ביותר שבו אפשר להגיע לתא הימני התחתון
אילוצים
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- כל ערך מ־0 עד
n²-1מופיע פעם אחת בדיוק.
דוגמאות
- קלט
- grid = [[0, 2], [3, 1]]
- פלט
- 2
- הסבר
- דרך התא הימני העליון המסלול הוא 0, 2, 1, והתא הגבוה ביותר בו הוא 2. דרך התא השמאלי התחתון המסלול הוא 0, 3, 1, והתא הגבוה ביותר בו הוא 3. בזמן 2 המסלול הראשון נמצא מתחת למים, ולכן התשובה היא 2.
- קלט
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- פלט
- 16
- הסבר
- בזמן 15 אפשר להגיע לשורה העליונה ול־5 שמתחת לקצה שלה, אבל כל דרך החוצה מהאזור הזה עוברת דרך 16 או יותר. ירידה ישרה בצד ימין מובילה ל־16 ואז ל־20. פנייה שמאלה ב־16 והקפה דרך 15, 14, 13, 12, 11 וחזרה לאורך השורה התחתונה לעולם אינה עולה מעל 16, ולכן התשובה היא 16.
- קלט
- grid = [[3, 0], [1, 2]]
- פלט
- 3
- הסבר
- גובה תא ההתחלה הוא 3, ולכן אי אפשר להיות בו ואי אפשר לצאת ממנו לפני זמן 3. עד אז, כל הרשת נמצאת מתחת למים.
+13 בדיקות נסתרות בשליחה
שאלת המשך
אם הגבהים יכולים לחזור על עצמם ולהגיע ל־10^9, איזו מהגישות שלך עדיין עובדת ללא שינוי, ועל מה היית מבצע חיפוש בינארי?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
נניח שידוע לך מפלס המים
t. האם תוכל לומר אם יש דרך לעבור? כיצד התשובה משתנה ככל ש־tגדל?מסלול צריך שהמים יכסו כל תא שבו, ולכן הזמן שנדרש למסלול הוא הזמן שלוקח למים להגיע לתא הגבוה ביותר בו. רוצים לבחור במסלול בין הפינות שהתא הגבוה ביותר בו נמוך ככל האפשר.
אפשר לבצע חיפוש בינארי על
tכאשר מילוי שטח הוא הבדיקה, או להריץ את האלגוריתם של דייקסטרה עם ערימת מינימום, שבה הזמן של תא הוא הגדול מבין זמן ההגעה אליו לבין הגובה שלו. יש לעצור כאשר התא הימני התחתון יוצא מהערימה.
פתרון
הזמן שנדרש למסלול הוא גובה התא הגבוה ביותר בו, כי המים צריכים לכסות כל תא שעוברים בו. לכן המשימה היא למצוא את המסלול בין הפינות שהתא הגבוה ביותר בו נמוך ככל האפשר: מסלול קצר ביותר שבו העלות של מסלול היא הערך המרבי שלו, ולא הסכום שלו. אפשר להעלות את מפלס המים צעד אחר צעד ולבדוק, לבצע חיפוש בינארי על מפלס המים באמצעות אותה בדיקה, או להריץ את האלגוריתם של דייקסטרה כשהעלות היא גובה התא הגבוה ביותר.
העלה את מפלס המים צעד אחד בכל פעם
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
קבעו מפלס מים t. התאים שאפשר להגיע אליהם הם התאים שגובהם לכל היותר t ושמחוברים לנקודת ההתחלה דרך תאים כאלה. סריקת הצפה אחת מהפינה השמאלית העליונה מוצאת אותם: דוחפים את נקודת ההתחלה, שולפים תא, ודוחפים כל שכן שטרם ביקרנו בו וגובהו לכל היותר t. אם מגיעים לפינה הימנית התחתונה, מפלס המים t מספיק.
התשובה היא מפלס t הנמוך ביותר שבו סריקת ההצפה מצליחה להגיע לצד השני. הוא לא יכול להיות נמוך מהפינה הגבוהה יותר, max(grid[0][0], grid[n-1][n-1]), כי שתי הפינות חייבות להיות מתחת למים. התחילו משם והוסיפו 1 עד שהסריקה מצליחה. המפלס הראשון שעובד הוא התשובה, כי עליית מפלס המים רק חושפת תאים ולעולם אינה מסתירה אותם: מפלס שעובד ממשיך לעבוד.
העלות של כל בדיקה היא O(n²), ומפלס המים עשוי לעלות כמעט n² פעמים לפני שמצליחים להגיע לצד השני. בלוח בגודל 100 × 100 מדובר בעד 10^4 מפלסים × 10^4 תאים, כלומר בערך 10^8 ביקורים בתאים. בבדיקות הגדולות הפינות מכילות 0 ו־1 והתשובות נעות בין 4,950 ל־9,998, ולכן אלפי סריקות הצפה מלאות מתבצעות לפני שמוצאים את התשובה.
אלגוריתם
- הגדר את
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חיפוש בינארי בגובה המים
האינטואיציה
לבדיקה מהגישה הראשונה יש צורה שימושית. היא נכשלת בכל רמה שמתחת לתשובה, ומצליחה בכל רמה מהתשובה ומעלה. חיפוש בינארי מוצא שאלה שהתשובה עליה היא כן או לא, ושמתהפכת פעם אחת מלא ללא, במספר ניסיונות לוגריתמי.
חפשו בין lo, הפינה הגבוהה יותר, לבין hi = n²-1, התא הגבוה ביותר, שבו כל הרשת מתחת למים והבדיקה חייבת להצליח. בדקו את הרמה האמצעית. אם אפשר לעבור, התשובה היא לכל היותר mid, ולכן הציבו hi = mid; אם לא, התשובה גבוהה מ־mid, ולכן הציבו lo = mid + 1. כשהם נפגשים, הרמה הזאת היא התשובה.
בדוגמה של 5 × 5, lo = 6 ו־hi = 24. רמה 15 נכשלת, כי האזור העליון סגור, ולכן lo = 16. הרמות 20, 18, 17 ו־16 מצליחות כולן, ומורידות את hi ל־16; החיפוש מסתיים ב־16 לאחר חמש מילויי הצפה.
ברשת של 100 × 100 יש 10^4 רמות, ולכן כ־14 בדיקות מספיקות כדי להכריע, כל אחת בסיבוכיות O(n²): כ־1.4 × 10^5 ביקורים בתאים במקום 10^8. השאירו את מילוי ההצפה איטרטיבי. בדיקה גדולה אחת היא מסדרון מתפתל באורך של כ־5,000 תאים, עמוק בהרבה מהמגבלה של Python, שעומדת על 1,000 קריאות מקוננות.
אלגוריתם
- הגדר את
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 loDijkstra על התא הגבוה ביותר במסלול
האינטואיציה
התייחסו לרשת כאל גרף ותנו לכל מסלול עלות: הגובה של התא הגבוה ביותר במסלול, ולא סכום הצעדים שלו. אלגוריתם דייקסטרה עדיין עובד עם העלות הזאת, כי הארכת מסלול לעולם לא מוזילה אותו. העלות של המסלול הארוך יותר היא max(old cost, new height), והיא לעולם אינה נמוכה מהעלות הקודמת, וזו התכונה היחידה שדייקסטרה צריך.
החזיקו ערימת מינימום של תאים, שמפתחיה הוא הזמן שלהם — התא הגבוה ביותר במסלול הטוב ביותר שנמצא אליהם. התחילו בפינה השמאלית העליונה בזמן grid[0][0]. הוציאו את התא בעל הזמן הקטן ביותר t; לכל שכן שעדיין לא ראיתם, קבעו זמן max(t, its height). כשהתא הימני התחתון יוצא מהערימה, הזמן שלו הוא התשובה.
אפשר לסמן תא כמי שנראה בפעם הראשונה שדוחפים אותו לערימה. תאים יוצאים מהערימה לפי סדר הזמנים, ולכן התא הראשון שמגיע לשכן מגיע בזמן הקטן ביותר מבין כל התאים שאי פעם יגיעו אליו, והזמן שמתקבל עבור השכן ממנו הוא הטוב ביותר האפשרי. מסלול מאוחר יותר יגיע בזמן גדול באותה מידה או יותר. לכן כל תא נכנס לערימה פעם אחת, עם הזמן הסופי שלו.
אלה המים העולים, צעד אחר צעד. הערימה מכילה את קצה האזור שאליו אפשר להגיע, והוצאת התא הנמוך ביותר ממנה היא כמו לתת למים לעלות בדיוק עד שאפשר לצעוד אליו. בדוגמה של 5 × 5, ההוצאות מתרחשות בזמנים 0, 1, 2, 3, 4, 5, ואז מגיע תורו של השער בגובה 16. אחר כך כל תא לאורך העיקוף מקבל זמן 16, והתא הימני התחתון יוצא מהערימה בזמן 16 לפני כל תא גבוה יותר.
כל אחד מ־n² התאים נדחף לערימה ונשלף ממנה לכל היותר פעם אחת, בעלות O(log n) לכל פעולה, ולכן זמן הריצה הוא O(n² log n), והחיפוש נעצר ברגע שהיעד יוצא מהערימה.
אלגוריתם
- סמן את התא השמאלי העליון כנראה ודחוף אותו עם הזמן
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]. עם[[3, 0], [1, 2]]התשובה היא 3. - התעלמות מהגובה של תא היעד. גם הפינה הימנית התחתונה חייבת להיות מתחת למים, ולכן התשובה היא לפחות
grid[n-1][n-1]. - הליכה חמדנית אל השכן הנמוך ביותר של התא הנוכחי. המסלול הטוב ביותר עשוי לטפס אל שער ואז להקיף בדרך ארוכה, כמו בדוגמה של 5 × 5. רק חיפוש לאורך כל גבול האזור שאליו הגעת יכול למצוא אותו.
- חיבור הגבהים לאורך המסלול, כמו במסלול קצר ביותר רגיל. הזמן החדש הוא
max(t, height), ולאt + height. - שימוש ברקורסיה למילוי ההצפה. מסלול מפותל יכול להיות באורך של אלפי תאים, מה שחרוג מהמגבלה של Python, המאפשרת 1,000 קריאות מקוננות.
- תנועה באלכסון. אפשר לשחות רק לתא שחולק צלע עם התא שלך.
שאלות נפוצות4
מהי סיבוכיות הזמן של Swim in Rising Water?
O(n² log n) עם האלגוריתם של Dijkstra: כל אחת מ-n² התאים נדחפת ונשלפת לכל היותר פעם אחת מערימה של עד n² איברים. לחיפוש בינארי של מפלס המים יש אותו חסם, בערך log2(n²) מילויי שטח של O(n²) כל אחד. בשתי השיטות נעשה שימוש ב-O(n²) זיכרון עבור הסימונים של התאים שבהם ביקרנו ועבור הערימה או המחסנית.
למה האלגוריתם של דייקסטרה עובד כשהעלות היא של התא בעל הערך הגבוה ביותר?
ל-Dijkstra נדרשת תכונה אחת: הארכת מסלול לעולם אינה מפחיתה את העלות שלו. כאן העלות החדשה היא max(t, height), והיא לעולם אינה נמוכה מ-t, ולכן התכונה מתקיימת. זו הסיבה שבפעם הראשונה שתא יוצא מהערימה, הזמן שלו סופי, ואפשר לעצור ביעד.
האם אפשר לפתור את «שחייה במים עולים» באמצעות חיפוש בינארי?
כן. השאלה אם אפשר לעבור לצד השני ברמה t מקבלת תשובה שקרית בכל רמה שמתחת לתשובה, ואמיתית החל מהתשובה ואילך. חיפוש בינארי על t, כאשר מילוי שטח משמש כמבחן, מוצא את התשובה בכ־log2(n²) בדיקות: 14 עבור רשת בגודל 100 × 100.
האם Union-Find יכול לפתור את בעיית השחייה במים עולים?
כן. פתח את התאים לפי סדר הגובה, חבר כל תא חדש לשכניו הפתוחים, ועצור ברגע שהתא השמאלי העליון והתא הימני התחתון נמצאים באותה קבוצה. גובה התא שפתחת אחרון הוא התשובה. מכיוון שהרשת מכילה כל ערך מ־0 עד n²-1 פעם אחת, טבלה שממפה גובה לתא נותנת את סדר הפתיחה ללא מיון.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def swimInWater(grid):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
grid = [[0, 2], [3, 1]]
צפוי
2