Flood Fill

Q: מהי סיבוכיות הזמן של Flood Fill?

O(m × n) עבור תמונה עם m שורות ו־n עמודות. כל פיקסל באזור נדחף למחסנית פעם אחת ובודק ארבעה שכנים, ופיקסלים מחוץ לאזור נבדקים רק כשכנים. המחסנית יכולה להכיל עד m × n פיקסלים כאשר התמונה כולה היא אזור אחד.

Q: האם כדאי להשתמש ב-BFS או ב-DFS למילוי שטחים?

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

Q: למה Flood Fill נכנס ללולאה אינסופית כשהצבע החדש זהה לצבע הישן?

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

Q: האם אפשר לפתור מילוי שטחים רקורסיבית?

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

קלגרפים

+10

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

פונקציה

floodFill(image: integer-2d-array, sr: integer, sc: integer, color: integer) → integer-2d-array

imageinteger-2d-array: התמונה כרשימת שורות, מספר אחד לכל פיקסל
srinteger: השורה של הפיקסל ההתחלתי, כשהספירה מתחילה מ־0
scinteger: העמודה של הפיקסל ההתחלתי, בספירה מ-0
colorinteger: הצבע החדש לאזור
מחזירהinteger-2d-array: התמונה לאחר שהאזור נצבע מחדש

אילוצים

1 ≤ image.length ≤ 80
1 ≤ image[i].length ≤ 80
לכל השורות יש אותו אורך.
0 ≤ image[i][j], color ≤ 65535
0 ≤ sr < image.length וגם 0 ≤ sc < image[0].length

דוגמאות

קלט: image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]sr = 0sc = 0color = 5
פלט: [[5, 5, 0], [5, 0, 5], [5, 5, 5]]
הסבר: בתחילת הלוח נמצא צבע 1. ה־1 שמימינו, ה־1ים לאורך העמודה השמאלית והשורה התחתונה, וה־1 שמעל לפינה הימנית התחתונה — כולם מחוברים אליו, ולכן כל השבעה הופכים ל־5. שני ה־0ים הם בצבע אחר ונשארים כפי שהם.

+18 בדיקות נסתרות בשליחה

שאלת המשך

איך הפתרון שלך היה משתנה אילו גם פיקסלים שנוגעים זה בזה רק בפינה היו נחשבים למחוברים?

פתרון

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

חיפוש עומק רקורסיבי

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

האינטואיציה

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

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

העבודה היא O(m × n), אבל מחסנית הקריאות היא נקודת התורפה. הרקורסיה מגיעה לעומק שאורכו כאורך הנתיב שאחריו היא עוקבת. נחש באורך פיקסל אחד בתוך תמונה בגודל 80 × 80 הוא באורך של כ־3,200 פיקסלים, ולכן הקריאות נערמות לעומק של כ־3,200. Python נעצרת כברירת מחדל ב־1,000 ומעלה שגיאה, ולכן הגישה הזאת לא מסתיימת בבדיקות הגדולות ביותר. שפות אחרות מאפשרות קריאות עמוקות יותר, אבל גם בהן תמונה גדולה יותר תמצה את מחסנית הקריאות.

אלגוריתם

קוראים את old = image[sr][sc]. אם old שווה ל־color, מחזירים את התמונה.
מגדירים את paint(r, c): חוזרים אם (r, c) נמצא מחוץ לתמונה או אם הצבע שלו אינו old.
אחרת, מגדירים image[r][c] = color וקוראים ל־paint עבור הפיקסלים שמעל, מתחת, משמאל ומימין.
קוראים ל־paint(sr, sc) ומחזירים את התמונה.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    if old == color:
        return image
    rows, cols = len(image), len(image[0])

    def paint(r, c):
        # Stop outside the image and at any pixel that is not the old color.
        if r < 0 or r >= rows or c < 0 or c >= cols or image[r][c] != old:
            return
        image[r][c] = color
        paint(r + 1, c)
        paint(r - 1, c)
        paint(r, c + 1)
        paint(r, c - 1)

    paint(sr, sc)
    return image

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

האינטואיציה

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

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

כל פיקסל באזור נדחף פעם אחת ונבדקים ארבעת השכנים שלו, ולכן זמן הריצה הוא O(m × n). המחסנית מכילה לכל היותר את הפיקסלים שבאזור. היא נמצאת בזיכרון הרגיל, ולכן אזור מפותל של 3,200 פיקסלים אינו בעיה, בעוד שבגרסה הרקורסיבית נגמר המקום במחסנית הקריאות.

אלגוריתם

קרא את old = image[sr][sc]. אם old שווה ל־color, החזר את התמונה.
צבע את (sr, sc) ודחוף אותו למחסנית.
הוצא פיקסל מהמחסנית והסתכל על ארבעת השכנים שלו.
עבור כל שכן שנמצא בתוך התמונה וצבעו הוא old, צבע אותו ודחוף אותו למחסנית.
כשהמחסנית ריקה, החזר את התמונה.

def floodFill(image, sr, sc, color):
    old = image[sr][sc]
    # Painting a region its own color changes nothing. Returning here also
    # stops the search from pushing the same cells forever.
    if old == color:
        return image
    rows, cols = len(image), len(image[0])
    image[sr][sc] = color
    stack = [(sr, sc)]
    while stack:
        r, c = stack.pop()
        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 image[nr][nc] == old:
                # Paint on push: a painted cell no longer matches old,
                # so it can never be pushed twice.
                image[nr][nc] = color
                stack.append((nr, nc))
    return image

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

רוב התשובות השגויות נובעות מאותו מקרה של צבע, מיציאה מגבולות התמונה או מרקורסיה באזור ארוך.

שוכחים את המקרה שבו color שווה לצבע ההתחלתי. הצביעה אינה משנה דבר, ולכן חיפוש שמשתמש בצבע כסימון לביקור יוסיף שוב ושוב את אותם פיקסלים לתור.
קוראים את image[sr][sc] אחרי שצובעים אותו. שמרו תחילה את הצבע הישן, אחרת תשוו כל שכן לצבע החדש.
סופרים שכנים אלכסוניים. פיקסלים שנוגעים זה בזה רק בפינה אינם מחוברים.
בודקים את צבעו של שכן לפני שבודקים שהוא נמצא בתוך התמונה. בדקו תחילה את 0 ≤ row < rows וגם את 0 ≤ col < cols.
רקורסיה בתמונה גדולה. מסלול ברוחב פיקסל אחד דרך תמונה בגודל 80 × 80 הוא באורך של כ־3,200 פיקסלים, עומק שמספיק כדי לעבור את מגבלת הרקורסיה של Python.
צובעים כל פיקסל בצבע הישן בכל התמונה. פיקסלים בצבע הזה שמנותקים מנקודת ההתחלה צריכים לשמור על צבעם.

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

מהי סיבוכיות הזמן של Flood Fill?

O(m × n) עבור תמונה עם m שורות ו־n עמודות. כל פיקסל באזור נדחף למחסנית פעם אחת ובודק ארבעה שכנים, ופיקסלים מחוץ לאזור נבדקים רק כשכנים. המחסנית יכולה להכיל עד m × n פיקסלים כאשר התמונה כולה היא אזור אחד.

האם כדאי להשתמש ב-BFS או ב-DFS למילוי שטחים?

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

למה Flood Fill נכנס ללולאה אינסופית כשהצבע החדש זהה לצבע הישן?

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

האם אפשר לפתור מילוי שטחים רקורסיבית?

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

Python

def floodFill(image, sr, sc, color):
    # כתבו כאן את הקוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

image = [[1, 1, 0], [1, 0, 1], [1, 1, 1]]
sr = 0
sc = 0
color = 5

צפוי

[[5, 5, 0], [5, 0, 5], [5, 5, 5]]