מילוי שטחים

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

אוקי, אני אתחיל מדוגמא.

הדוגמא שלי תהיה מטריצה בגודל 3X3 בשני צבעים – 1 ייצג צבע שחור ו-0 ייצג צבע לבן.

A = 1 1 1 1 0 0 1 0 0

נניח שאני רוצה לצבוע את הריבוע הקטן בצבע כחול, שיסומן במספר 2.

אני אפעיל את הפונקציה שלי על הנקודה (1,1) בתת מטריצה שעכשיו מלאה אפסים, ואקבל את התוצאה –

B = 1 1 1 1 2 2 1 2 2

איך עשיתי את זה?

התחלתי מנקודה (1,1) במטריצה, ושמרתי את הצבע שלה – לבן. הגבולות של השטח שאני ממלאה הוא כל פיקסל שאני יכולה להגיע אליו שהוא שונה מהצבע ההתחלתי שלי.

מהנקודה (1,1) התפשטתי לכל כיוון שבו היה לי צבע לבן, צבעתי אותו לכחול והמשכתי הלאה ממנו.

התיאור למעלה נשמע כמו אלגוריתם רקורסיבי מאוד פשוט.

def paint_and_fill_recur(A, pos, new_color, old_color):
	if A.get_color(pos) == old_color:
		A.set_color(pos,new_color)
		neighbours = A.get_neighbours(pos)
		for neighbour in neighbours:
			paint_and_fill_recur(A,neighbour,new_color,old_color)

הנחות שביצעתי באלגוריתם לשם הנוחות:

1. אני מניחה שאני מקבלת את המשתנה old_color מבחוץ, מפונקציה שבודקת את הצבע של הנקודה הראשונה, וקוראת לאלגוריתם הרקורסיבי.
2. אני מניחה שלמטריצה A יש פונקציות get_color, set_color, get_neighbours שאני יכולה להשתמש בהם, ואני אממש אותן מאוחר יותר.

אני אריץ את האלגוריתם שלי על הדוגמא למעלה –

A = 1 1 1 1 0 0 1 0 0

paint_and_fill_recur(A, (1,1), 2, 0): A.set_color((1,1),2) neighbours = [(1,2),(2,1)] call paint_and_fill_recur(A, (1,2), 2, 0) A = 1 1 1 1 2 0 1 0 0 paint_and_fill_recur(A, (1,2), 2, 0): A.set_color((1,2),2) neighbours = [(2,2)] call paint_and_fill_recur(A, (2,2), 2, 0) A = 1 1 1 1 2 2 1 0 0 paint_and_fill_recur(A, (2,2), 2, 0): A.set_color((2,2),2) neighbours = [(2,1)] call paint_and_fill_recur(A, (2,1), 2, 0) A = 1 1 1 1 2 2 1 0 2 paint_and_fill_recur(A, (2,1), 2, 0): A.set_color((2,1),2) neighbours = [] A = 1 1 1 1 2 2 1 2 2 paint_and_fill_recur(A, (1,1), 2, 0): A.set_color((1,1),2) neighbours = [(1,2),(2,1)] call paint_and_fill_recur(A, (2,1), 2, 0) paint_and_fill_recur(A, (2,1), 2, 0): A.get_color(pos) != old_color

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

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

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

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

def paint_and_fill_recur(A, pos, new_color, old_color):
	A.set_color(pos,new_color)
	next_neighbour = A.get_neighbour(pos, old_color)
	while next_neighbour:
		paint_and_fill_recur(A, next_neighbour, new_color,old_color)
		next_neighbour = A.get_neighbour(pos, old_color)

מגניב.

עכשיו לרוץ על קצת מקרי קצה.

מטריצה של תא אחד –

A = 0 paint_and_fill_recur(A, (0,0), 2, 0): A.set_color((0,0),2) next_neighbour = [] A = 2

נראה טוב.

האם יש עוד דוגמאות שאני יכולה לחשוב עליהן?

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

הדבר האחרון שנותר לדון בו הוא הסיבוכיות.

סיבוכיות הזמן של האלגוריתם היא (O(N – בכל תא אני דורכת בדיוק פעם אחת, אני מביאה את השכנים שלו בזמן קבוע, וממשיכה לרוץ רק על תאים שלא נגע בהם.

מה הסיבוכיות מקום?

במקרה הכי גרוע (שכל המטריצה היא צבע אחד וצריך לצבוע אותה בצבע אחר) עומק הרקורסיה שלי יהיה (O(N.

קול, אפשר לעבור לקודד.

קוד בגיט – https://github.com/mgershovitz/maya_solves/blob/master/paint_and_fill.py

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