Number of Islands
ניתנת לך מפה כרשימה של מחרוזות באורך שווה, שבה '1' הוא משבצת של אדמה ו-'0' הוא משבצת של מים. שתי משבצות אדמה שייכות לאותו אי כאשר הן חולקות צלע: למעלה, למטה, שמאלה או ימינה. משבצות שנוגעות זו בזו רק בפינה אינן מחוברות. החזר את מספר האיים.
פונקציה
- gridstring-array
- המפה, מחרוזת אחת בכל שורה
- מחזירהinteger
- מספר האיים
אילוצים
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- לכל שורה יש אותו אורך.
- כל תו הוא
'0'או'1'.
דוגמאות
- קלט
- grid = ["11000", "11000", "00100", "00011"]
- פלט
- 3
- הסבר
- ארבעת הריבועים בפינה השמאלית העליונה יוצרים אי אחד. הריבוע האמצעי בשורה השלישית נוגע בהם רק בפינה, ולכן הוא אי שני. הזוג בפינה הימנית התחתונה הוא השלישי.
- קלט
- grid = ["01110", "01000", "00011", "11001"]
- פלט
- 3
- הסבר
- שלושת הריבועים בשורה העליונה והריבוע שמתחת לקצה השמאלי שלה יוצרים אי אחד. הזוג הימני בשורה השלישית מתחבר כלפי מטה לריבוע הימני התחתון ויוצר אי שני. הזוג השמאלי התחתון הוא האי השלישי.
שאלת המשך
כעת היבשה מופיעה ריבוע אחד בכל פעם על מפת מים. האם תוכל לדווח על מספר האיים אחרי כל ריבוע חדש, בלי לסרוק שוב את כל המפה?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
סרוק את המפה ריבוע אחר ריבוע. כשאתה מגיע לריבוע יבשה שאף אי קודם לא תפס, כמה איים חדשים מצאת?
לאחר שתמצא אי חדש, בקר בכל משבצת יבשה המחוברת אליו וסמן כל אחת מהן ככזו שנראתה, כדי שהסריקה לא תספור את אותו האי שוב.
חקור באמצעות תור (חיפוש לרוחב) או מחסנית מפורשת (חיפוש לעומק) של משבצות שעדיין צריך לבקר בהן. חיפוש רקורסיבי עלול למצות את מחסנית הקריאות במפה שהיא אי ענקי אחד, בעוד שלולאה שעוברת על התור או המחסנית שלך לא יכולה.
פתרון
התייחסו לכל משבצת יבשה כאל צומת המחוברת למשבצות היבשה שלצדה: אי הוא אזור אחד מחובר. סרקו את המפה, ובכל פעם שתגיעו ליבשה שטרם ראיתם, ספרו אי חדש ומלאו אותו בהצפה, תוך סימון כל המשבצות שלו כדי שהסריקה לא תספור אותו שוב.
מילוי שטח באמצעות מחסנית מפורשת (DFS)
האינטואיציה
משבצת יבשה שלא סומנה לא יכולה להשתייך לאי שכבר ספרת, כי ספירת אי מסמנת את כולו. לכן היא מתחילה אי חדש. מחסנית שמנהלים בעצמכם מסמנת את השאר: כל משבצת שמוציאים מהמחסנית מוסיפה אליה את שכנותיה היבשות שלא סומנו, וכשהמחסנית ריקה כל האי מסומן.
המחסנית שלכם חשובה, כי מילוי רקורסיבי יכול להגיע לעומק של 22,500 קריאות במפה בגודל 150 × 150 שכולה יבשה. כל משבצת נדחפת לכל היותר פעם אחת, ונבדקות ארבע שכנות, ולכן זמן הריצה הוא O(rows × cols). הסימונים והמחסנית דורשים O(rows × cols) מקום כשהמפה כולה יבשה.
אלגוריתם
- צרו סימון ביקור לכל משבצת והגדירו את המונה ל-0.
- סרקו כל משבצת, תוך דילוג על מים ועל משבצות שכבר סומנו.
- ביבשה שלא סומנה, הוסיפו 1 למונה, סמנו את המשבצת ודחפו אותה למחסנית.
- כל עוד המחסנית אינה ריקה, שלפו משבצת ודחפו למחסנית כל משבצת שכנה שנמצאת בתוך המפה והיא יבשה ולא סומנה, תוך סימונה לפני הדחיפה.
- החזירו את המונה כשהסריקה מסתיימת.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return countמילוי שטחים באמצעות תור (BFS)
האינטואיציה
הספירה פועלת באותה דרך; רק סדר הביקור משתנה. תור מוציא ריבועים מהחזית ומוסיף מאחור שכנים של יבשה שלא סומנו, כך שהוא מבקר באי בטבעות: הריבוע הראשון, אחר כך כל ריבוע במרחק צעד אחד, ואז שני צעדים. עדיין מבקרים בכל ריבוע פעם אחת, בזמן ובזיכרון O(rows × cols).
סדר הטבעות נותן את המרחק של כל ריבוע מנקודת ההתחלה, ולכן אותה לולאה עונה על שאלות של המסלול הקצר ביותר ברשת, עם מספר נוסף אחד לכל ריבוע.
אלגוריתם
- צור סימון ביקור עבור כל משבצת וקבע את המונה ל־0.
- סרוק כל משבצת, תוך דילוג על מים ועל משבצות שכבר סומנו.
- ביבשה שטרם סומנה, הוסף 1 למונה, סמן את המשבצת והכנס אותה לתור ריק.
- כל עוד יש משבצות בתור, הוצא אחת מהראש והוסף לסוף התור כל שכן שנמצא בתוך המפה, הוא יבשה שטרם סומנה, תוך סימונו בעת ההוספה.
- החזר את המונה כשהסריקה מסתיימת.
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
מלכודות ומקרי קצה
- סימון של משבצת כשמוציאים אותה מהמחסנית או מהתור במקום כשמכניסים אותה. כך אותה משבצת נכנסת כמה פעמים.
- השוואה של משבצת למספר 1 במקום לתו
'1'. כל שורה היא מחרוזת, ולכן כל משבצת היא תו. - קריאה של משבצת שכנה לפני בדיקת
0 ≤ row < rowsו-0 ≤ col < cols. כך קריאה של משבצת יבשה בקצה יוצאת מגבולות המפה. - כתיבת המילוי באופן רקורסיבי. כברירת מחדל, Python נעצרת אחרי 1,000 קריאות, ושפות אחרות עלולות לחרוג מגבולות המחסנית באי גדול אחד.
- שליפת האיבר הראשון מרשימת Python באמצעות
pop(0), שעלותה גדלה ביחס ישר לאורך הרשימה. השתמשו ב-collections.dequeוב-popleft().
שאלות נפוצות4
מהי סיבוכיות הזמן של Number of Islands?
O(rows × cols). הסריקה בודקת כל משבצת פעם אחת, וכל משבצת יבשה נכנסת למחסנית או לתור פעם אחת ובודקת ארבעה שכנים. הסימונים של המשבצות שכבר נבדקו והמחסנית או התור משתמשים בזיכרון בנפח O(rows × cols) במפה שכולה יבשה.
האם כדאי להשתמש ב-BFS או ב-DFS עבור בעיית מספר האיים?
שתיהן נכונות באותה מידה מבחינת זמן ומקום, כי בספירה צריך רק לסמן כל משבצת באי. BFS עם תור לעולם לא משתמש ברקורסיה; DFS בטוח באותה מידה כשהוא משתמש במחסנית מפורשת.
האם תוכל לפתור את בעיית Number of Islands באמצעות מבנה Union-Find?
כן. שים כל משבצת יבשה בקבוצה משלה והתחל את הספירה במספר משבצות היבשה. חבר כל זוג של משבצות יבשה סמוכות, והפחת את הספירה באחד בכל פעם שחיבור מאחד שתי קבוצות שונות. עם דחיסת נתיבים, זמן הריצה קרוב ל־O(rows × cols).
האם אפשר לספור איים בלי מערך נפרד למעקב אחר האיים שכבר ביקרנו בהם?
כן, אם מותר לך לשנות את המפה: הפוך כל משבצת יבשה למים ברגע שתגיע אליה. בשפות רבות אי אפשר לשנות מחרוזות במקום, ולכן קודם מעתיקים את השורות לרשת של תווים, שתופסת אותו נפח כמו סימוני המקומות שכבר נבדקו.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def numIslands(grid):
# כתבו כאן קודבדיקה #1
בדיקה #2
ארגומנט
grid = ["11000", "11000", "00100", "00011"]
הפלט הצפוי
3