עריסטו
Active member
חידת אלגוריתם
יש לכם תמונה מלבנית שמורכבת מפיקסלים שחורים ולבנים. אתם צריכים לספור כמה גושים שחורים יש בתמונה. גוש שחור מוגדר כקבוצת פיקסלים שחורים שמחוברים זה לזה במאוזן או במאונך. גוש לבן מוגדר באופן דומה. ידוע מראש שאין גוש שחור שבתוכו גוש לבן. כמו כן ידוע שלתמונה יש שוליים לבנים, כלומר כל הפיקסלים הסמוכים לשולי התמונה לבנים. אתם צריכם לפתור בדרך היעילה והפשוטה ביותר.
יש לכם תמונה מלבנית שמורכבת מפיקסלים שחורים ולבנים. אתם צריכים לספור כמה גושים שחורים יש בתמונה. גוש שחור מוגדר כקבוצת פיקסלים שחורים שמחוברים זה לזה במאוזן או במאונך. גוש לבן מוגדר באופן דומה. ידוע מראש שאין גוש שחור שבתוכו גוש לבן. כמו כן ידוע שלתמונה יש שוליים לבנים, כלומר כל הפיקסלים הסמוכים לשולי התמונה לבנים. אתם צריכם לפתור בדרך היעילה והפשוטה ביותר.
, כמובן, כאשר n הוא מספר המשבצות (הרי חייבים לעבור על המשבצות), ובסיבוכיות מקום O(1), כלומר פרט לזכרון הדרוש לאחסון מערך הפיקסלים הוא דורש כמות זכרון קבועה, שאינה גדלה עם גידול מערך הפיקסלים (באלגוריתם שלך זה לא כך). גם מבחינת אורך הקוד ומורכבותו הוא פשוט הרבה יותר מהאלגוריתם שלך. האלגוריתם שלך הוא האלגוריתם הטוב ביותר שיש במקרה הכללי; שים לב שבבעיה שלי יש נתון נוסף - כל המשבצות הלבנות מהוות גוש אחד, כלומר אין גוש שחור המקיף גוש לבן. עובדה זו מאפשרת לכתוב אלגוריתם פשוט יותר. (למעשה יש בבעיה שלי עוד נתון - שהשוליים של מערך המשבצות לבנים, כלומר אין גוש שחור שנוגע בשוליים; זה נתון שהוספתי רק כדי לפשט את האלגוריתם - הרי גם אם לא היה כך אזי היה ניתן להוסיף שולים לבנים כאלה ואז להריץ את האלגוריתם הפשוט.)