אתגר תכנותי: זרימת מים לאוקיינוס השקט והאטלנטי

LeetCode 417: Pacific Atlantic Water Flow

תיאור האתגר:

נתונה רשת דו-ממדית heights שממדיה m x n, בה כל תא מייצג את גובה פני הקרקע בתא. הרשת מתארת אי אשר גובל באוקיינוס השקט בצפון ובמערב (שורות עליונות ועמודות שמאליות), ובאוקיינוס האטלנטי בדרום ובמזרח (שורות תחתונות ועמודות ימניות).

מים יכולים לזרום מתא לתא סמוך (למעלה, למטה, שמאלה, ימינה) אם הגובה בתא השכן נמוך או שווה לגובה בתא הנוכחי.

עליך להחזיר את רשימת הקואורדינטות של כל התאים שמהם מים יכולים לזרום גם לאוקיינוס השקט וגם לאוקיינוס האטלנטי.

אינטואיציה לפתרון

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

כך נקבל שתי קבוצות של תאים:

• תאים שמהם ניתן להגיע לאוקיינוס השקט.

• תאים שמהם ניתן להגיע לאוקיינוס האטלנטי.

התאים המשותפים לשתי הקבוצות הם אלו שמהם מים יכולים לזרום לשני האוקיינוסים.

מימוש בקוד

# Pacific atlantic water flow (leetcode 417)

def can_flow(heights):
    res = []

    height, width = len(heights), len(heights[0])

    pacific = [[False]*width for _ in range(height)]
    atlantic = [[False]*width for _ in range(height)]

    steps = [(-1,0), (0,1), (1,0), (0,-1)]

    def traverse(y, x, can_visit):
        can_visit[y][x] = True
        for dy, dx in steps:
            if 0 <= y+dy < height and 0 <= x+dx < width:
                if not can_visit[y+dy][x+dx] and heights[y+dy][x+dx] >= heights[y][x]:
                    traverse(y+dy, x+dx, can_visit)

    for y in range(height):
        traverse(y, 0, pacific)
        traverse(y, width-1, atlantic)

    for x in range(width):
        traverse(0, x, pacific)
        traverse(height-1, x, atlantic)

    for y in range(height):
        for x in range(width):
            if pacific[y][x] and atlantic[y][x]:
                res.append((y, x))
    
    # print(pacific)
    # print(atlantic)
    return res


heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
print(can_flow(heights))
# Solution: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

heights = [[1]]
print(can_flow(heights))
# Solution and actual result agree: [[0, 0]]

# Time and space complexities: O(M*N)

דוגמאות:

דוגמה 1:

heights = [ [1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4] ] 
print(pacific_atlantic(heights)) 
# Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

דוגמה 2:

heights = [[1]] print(pacific_atlantic(heights)) # Output: [[0, 0]]

ניתוח סיבוכיות:

• סיבוכיות זמן: O(m * n) — כל תא נבדק לכל היותר פעמיים (אחד לכל אוקיינוס).

• סיבוכיות מקום: O(m * n) — עבור מטריצות הסימון של כל אוקיינוס.

לסיכום:

הפתרון מבוסס על סריקה הפוכה (reverse DFS) מהאוקיינוסים פנימה, ומאפשר לזהות ביעילות את כל התאים שמהם מים יכולים לזרום לשני האוקיינוסים. גישה זו יעילה יותר מאשר לבדוק עבור כל תא האם ניתן להגיע ממנו לשני האוקיינוסים.

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

אלגוריתם חיפוש לעומק DFS

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

אתגר תכנותי : איך לשבט גרף

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים