שלום רב,

קיבלתי תרגיל לכתוב פונקציית fill כמו ה-paint bucket בצייר. תמונה מוגדרת כמערך דו מימדי של מספרים שלמים המייצגים את הצבעים השונים. אני אכתוב את הקוד, ואח"כ אצרף הסברים.

public static boolean isInside (int[][] pic, int row, int col){
		return (row<pic.length)&(row>=0)&((col<pic[0].length)&(col>=0));
	}


public static boolean legalNeighbor(int[][] pic, int x1,int y1, int x2,int y2) {
	boolean ans=false;
	if (isInside(pic,x1,y1)&isInside(pic,x2,y2))
		if (((Math.abs(x1-x2) == 1)&(y1==y2))|((Math.abs(y1-y2) == 1)&(x1==x2)))
			ans = (pic[x1][y1]==pic[x2][y2]);		
	return ans;
}

public static void fill(int[][] pic, int row, int col, int newColor){
	if (isInside(pic,row,col)){
		boolean top=legalNeighbor(pic,row,col,row-1,col);
		boolean btm=legalNeighbor(pic,row,col,row+1,col);
		boolean left=legalNeighbor(pic,row,col,row,col-1);
		boolean right=legalNeighbor(pic,row,col,row,col+1);
		pic[row][col]= newColor;
		if (top)
			fill(pic,row-1,col,newColor);
		if (btm)
			fill(pic,row+1,col,newColor);
		if (left)
			fill(pic,row,col-1,newColor);
		if (right)
			fill(pic,row,col+1,newColor);
	}	
}

אוקיי. הפונקציה isInside בודקת האם נקודה (row,col) נמצאת בגבולות המערך - כלומר האם היא נקודה בתמונה.

הפונקציה legalNeighbor בודקת האם נקודה היא שכנה של נקודה אחרת. אם נתנונה נקודה (x,y), השכנות שלה הן הנקודה שמעליה, מתחתיה, מימינה ומשמאלה, כמובן רק אלו אשר צבען זהה.

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

בהרצת הפונקציה fill על התמונה הבאה בנקודה הבאה אני מקבל שגיאת stack overflow. חשבתי וחשבתי ולא הצלחתי למצוא פגם לוגי. אנא עזרו למצוא פתרון.

התמונה:

public static int [][] house2={
			 {0,0,0,0,0,0,0,0,0},
			 {0,0,0,0,6,0,0,0,0},
			 {0,0,0,6,6,6,0,0,0},
			 {0,0,6,6,6,6,6,0,0},
			 {0,6,6,6,6,6,6,6,0},
			 {0,1,1,1,1,1,1,1,0},
			 {0,1,0,0,0,0,0,1,0},
			 {0,1,0,9,9,0,0,1,0},
			 {0,1,0,9,9,0,0,1,0},
			 {0,1,0,0,0,0,0,1,0}};

והזימון הוא

fill(house2,0,0,7);

שניה.

ההבדל בין & ל-&& (ובין | ל-||) הוא רק בסדר החישוב של הערכים, ובהאם הקומפיילר ימשיך לבדוק גם אחרי שנמצא true ב-or או false ב-and. כך שלפי מיטב הבנתי זה לא משנה במקרה הזה.

טעות שלי (מתלמד JAVA ). זה אמור לעבוד:

public class fill {

public static boolean isInside (int[][] pic, int row, int col){

return (row<pic.length)&&(row>=0)&&((col<pic[0].length)&&(col>=0));

}

public static boolean legalNeighbor(int[][] pic, int x1,int y1, int x2,int y2) {

boolean ans=false;

if (isInside(pic,x1,y1)&&isInside(pic,x2,y2))

if (((Math.abs(x1-x2) == 1)&&(y1==y2))||((Math.abs(y1-y2) == 1)&&(x1==x2)))

ans = (pic[x1][y1]==pic[x2][y2]);

return ans;

}

public static void fillit(int[][] pic, int row, int col, int oldColor, int newColor){

if (isInside(pic,row,col) && pic[row][col] == oldColor){

boolean top=legalNeighbor(pic,row,col,row-1,col);

boolean btm=legalNeighbor(pic,row,col,row+1,col);

boolean left=legalNeighbor(pic,row,col,row,col-1);

boolean right=legalNeighbor(pic,row,col,row,col+1);

pic[row][col]= newColor;

if (top)

fillit(pic,row-1,col,oldColor,newColor);

if (btm)

fillit(pic,row+1,col,oldColor,newColor);

if (left)

fillit(pic,row,col-1,oldColor,newColor);

if (right)

fillit(pic,row,col+1,oldColor,newColor);

}

}

public static int [][] house2={

{0,0,0,0,0,0,0,0,0},

{0,0,0,0,6,0,0,0,0},

{0,0,0,6,6,6,0,0,0},

{0,0,6,6,6,6,6,0,0},

{0,6,6,6,6,6,6,6,0},

{0,1,1,1,1,1,1,1,0},

{0,1,0,0,0,0,0,1,0},

{0,1,0,9,9,0,0,1,0},

{0,1,0,9,9,0,0,1,0},

{0,1,0,0,0,0,0,1,0}};

public static int [][] house0={

{0,0},

{0,0}};

public static void main(String[] args) {

fillit(house2,0,0,house2[0][0],7);

fillit(house0,0,0,house0[0][0],7);

}

}

יש לי בעיה מעצבנת שאני לא יכול ללחוץ על האופציות של הפורומים משום מה...

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

באיזה סביבת JAVA אתה עובד ?

--------------------

אני הולך לישון.

בכל מקרה, מה שעשיתי לפתרון הבעיה הוא:

1. עד כה עשיתי תוכנית אחת ב JAVA, אז נזכרתי איך מכניסים MAIN ל CLASS וכו'.

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

3. התחלתי להריץ DEBUG שורה שורה, בגלל שהקלט קטן והאלגוריתם לא ארוך הנחתי שאני אמצע את הפגם די מהר (בהתחלה עשיתי על הרוב STEP OVER רק כדי לגלות איפה הלוגיקה משתבשת, ואז עשיתי STEP IN במקומות הנ"ל, עד שמצאתי את הבעיה).

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

5. אמרתי שאם אני יבדוק כל הזמן מול הצבע המקורי בטוח לא יהיו בעיות

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

אני לא מכיר כל כך גאווה אבל אני מניח שיש שם אפשרות לערך דיפולטי. את הOLDCOLOR הייתי שם עם DEFAULT של הערך בנקודה x,yבמטריצה אם הוא לא נשלח(למען פשטות).

נראה אם שווה לעבור לJAVA אזה כמו בC++.

קודם כל תודה רבה לשניכם על העזרה! :-*

נראה לי שמצאתי פתרון אלגנטי:

	public static void fill(int[][] pic, int row, int col, int newColor){
		if ((isInside(pic,row,col))&&(pic[row][col]!=newColor)){
			boolean top=legalNeighbor(pic,row,col,row-1,col);
			boolean btm=legalNeighbor(pic,row,col,row+1,col);
			boolean left=legalNeighbor(pic,row,col,row,col-1);
			boolean right=legalNeighbor(pic,row,col,row,col+1);
			pic[row][col]= newColor;
			if (top)
				fill(pic,row-1,col,newColor);
			if (btm)
				fill(pic,row+1,col,newColor);
			if (left)
				fill(pic,row,col-1,newColor);
			if (right)
				fill(pic,row,col+1,newColor);
		}	
	}

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

שוב תודה!

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

אתה משתמש ב ECLIPSE או JBUILDER ?

אלו קומפיילרים או IDE?

אני משתמש ב-IDE בשם J Creator (דיי נוחה), וכנראה ב-SDK של Sun (אני עושה את כל העבודה במחשבים של האוניברסיטה).

הבנתי, לגבי ה COMPILER הרוב משתמשים ב SDK של SUN, אבל לגבי הסביבה שאלתי, כי עכשיו יש לי קורס ב JAVA. בכל מקרה, אני משתמש ב ECLIPSE, סביבה מעולה, הגרסא החדשה אף יותר טובה מ VISUAL STUDIO (רק ב JAVA כמובן).

אין לי מושג אם אפשר בכלל לעצב GUI ב-JCreator (אני לא מבין גדול, אבל אני מדבר על משהו בסגנון של דלפי). מבחינת נוחות הכתיבה של הקוד הוא סבבה לגמרי. איזה קורס?

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

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

בפועל אצלנו משתמשים או ב ECLIPSE או ב JBUILDER...

זה באוניברסטיה או מה? אני התחלתי ללמוד הנדסת תוכנה, לומד עכשיו "יסודות מדעי המחשב" - java.

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