בלוח דו-ממדי בגודל m * n, אשר כל אחת ממשבצותיו יכולה להיות ריקה או מלאה, נקרא כתם לרצף משבצות מלאות בעלות צלע משותפת או קדקוד משותף.

גודל הכתם הוא מספר המשבצות המרכיבות את הכתם.

ייתכנו מספר כתמים בלוח.

דוגמה:

נסמן משבצת מלאה באמצעות התו  ומשבצת ריקה באמצעות תו רווח.

הלוח צורף בקובץ למטה

מכיל 3 כתמים:

כתם המורכב ממשבצות (1, 0), (0, 1) וגודלו 2.

כתם המורכב ממשבצות (3, 2), (2, 2), (4, 1), (3, 1), (4, 0) וגודלו 5.

כתם המורכב ממשבצות (2, 4), (1, 4), (0, 4), (0, 3) וגודלו 4.

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

חתימת השיטה תהיה:

public static int stain (char [][] mat, int row, int col)

לדוגמה: עבור המערך מהדוגמה הקודמת וזוג המספרים (3, 1) יוחזר 5, ועבור זוג המספרים (4, 4) יוחזר אפס.

זה הקוד שלי שמשום מה מחזיר 1 כל הזמן:

{
int counter = 0;
int col_len = mat.length;
int row_len = mat[0].length;

if (row < 0 || col < 0 || row >= row_len || col >= col_len
|| mat[row][col] != 'x')
return 0;

else
{
counter += 1;
// Mark the current cell in order to prevent check this cell again
mat[col][row] = '2';

if (mat[col][row] != '2')
{
counter = counter + stain(mat, col_len + 1, row_len);
counter = counter + stain(mat, col_len + 1, row_len + 1);
counter = counter + stain(mat, col_len, row_len + 1);
counter = counter + stain(mat, col_len - 1, row_len + 1);
counter = counter + stain(mat, col_len - 1, row_len);
counter = counter + stain(mat, col_len - 1, row_len - 1);
counter = counter + stain(mat, col_len, row_len - 1);
counter = counter + stain(mat, col_len - 1, row_len - 1);
}
}

return counter;

[RIGHT] }[COLOR=#333333]

[/COLOR]    public static int stain (char[][] mat, int row, int col)[/RIGHT]

ניסית לדבג את הקוד לפני ששאלת אותנו?

ניסיתי ולצערי לא מצאתי את הבעיה

מה ניסית לעשות?

שמת breakpoint לפני הכניסה לפונקציה?

עברת step by step, כולל כניסה לכל קריאה נוספת לפונקציה?

וידאת מה הערכים של הפרמטרים שהועברו לפונקציה?

בנית לך מערך פשוט לדוגמה (נגיד בגודל 3 על 3), הרצת בראש (או בדף ועט) מה אמור לקרות?

כן

כשיצרתי את המערך הבא:

char[][] arr =

{

{'x' , 'x' , ' '},

{'x' , ' ' , ' '},

{' ' , ' ' , 'x'}

};

אני מקבל StackOverflowError יחד עם הערכים 0, 0

שמת breakpoint לפני הכניסה לפונקציה?

עברת step by step, כולל כניסה לכל קריאה נוספת לפונקציה?

וידאת מה הערכים של הפרמטרים שהועברו לפונקציה?

כן אבל יש המון המון קריאות וזה מה שגומר לי את הזיכרון

- - - תגובה אוחדה: - - -

יכול להיות בגלל שלא סימנתי תאיך שכבר ביקרתי בהם ?

איך אני יכול לסמן תאים ?

לא יודע, זה לבחירתך. מותר לך לשנות את המערך?

אין איזכור לגבי זה אלא רק מה להחזיר

אפשר בלי לשנות ?

תנסה קודם עם לשנות את המערך, אחר כך נסתדר.

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

תראה את העידכון שלי בהודעה הראשונה

תחשוב שנייה על ההגיון בשינוי והבדיקה שעשית...

(ושוב: משהו לא עובד? אל תקפוץ מיד לפרסם הודעה בפורום. תנסה לדבג ולראות איפה הבעיה)

בתוך ב-else שמתי את זה:

    		if (mat[col][row] != '2')			{
        		counter += 1;    		
                counter = counter + stain(mat, col_len + 1, row_len);    
                mat[col_len + 1][row_len] = '2';
                counter = counter + stain(mat, col_len + 1, row_len + 1);
                mat[col_len + 1][row_len + 1] = '2';
                counter = counter + stain(mat, col_len, row_len + 1);
                mat[col_len][row_len + 1] = '2';
                counter = counter + stain(mat, col_len - 1, row_len + 1);
                mat[col_len - 1][row_len + 1] = '2';
                counter = counter + stain(mat, col_len - 1, row_len);
                mat[col_len - 1][row_len] = '2';
                counter = counter + stain(mat, col_len - 1, row_len - 1);
                mat[col_len - 1][row_len - 1] = '2';
                counter = counter + stain(mat, col_len, row_len - 1);
                mat[col_len][row_len - 1] = '2';
                counter = counter + stain(mat, col_len - 1, row_len - 1);
                mat[col_len - 1][row_len - 1] = '2';
			}

ועדיין לא שינוי ואני לא מבין למה

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

אוקיי פתרתי את זה בסופו של דבר ע"י זה ששיניתי את המערך (מותר לי לעשות את זה) - יש אפשרות לפתור את זה מבלי לשנות את המערך או מבלי ליצור מערך עזר ?