שאלת מבחן במבוא למדעי המחשב - האוניברסיטה הפתוחה 2016 - רקורסיה

נתון מערך דו-ממדי `char[][] minChess` אשר מייצג שולחן מיני-שחמט בגודל ריבועי $k \times k$. - `minChess[i][j]='0'` מייצג תא ריק על שולחן השחמט. - `minChess[i][j]='K'` מייצג מקום בו נמצא המלך (king). - `minChess[i][j]='H'` מייצג מקום בו נמצא הפרש (horse). הפרש נע בתנועה מיוחדת, המשלבת ישר ואלכסון: הוא נע שתי משבצות באחד הכיוונים (אופקי או אנכי) ולאחר מכן משבצת אחת בכיוון ניצב בדיוק כמו במשחק שחמט אמיתי כפי שמתואר למטה. סימני ה-X מסמנים את המקומות אליהם מגיע הפרש. במשחק מיני-שחמט מסויים, נותר שלב אחרון בו הפרש צריך להתמודד מול המלך. עליכם לכתוב שיטה סטטית **רקורסיבית** המקבלת כפרמטרים את המערך `minChess` ואת המיקום של הפרש (שורה i ועמודה j), ומחזירה את אורכו של המסלול הקצר ביותר מהפרש אל המלך. אם אין מסלול כזה, השיטה תחזיר את הערך -1. חתימת השיטה היא: ```java public static int minPath(char[][] minChess, int i, int j) ``` - ניתן להניח כי ערכי המערך הם חוקיים כפי שמתואר, ולא יהיו ערכים אחרים. - ניתן להניח כי הפרש והמלך נמצאים במיקומים שונים במערך. - ערכי המערך אחרי הפעלת השיטה צריכים להיות זהים לערכים ההתחלתיים. השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר שתכתבו (אם תכתבו) לא יכולות להכיל לולאות. אפשר להשתמש בהעמסת-יתר (overloading).

רמז: השתמשו ב-backtracking: סמנו את המקום הנוכחי כמבוקר, נסו את כל 8 המהלכים האפשריים של הפרש, ושחזרו את הסימון לפני החזרה.

פתרון: **רקורסיית Backtracking** על לוח שחמט. הפרש נע במהלכי L (שילובי +/-1, +/-2). ```java public static int minPath(char[][] minChess, int i, int j) { // בסיס: מחוץ ללוח או תא שכבר ביקרנו if (i < 0 || i >= minChess.length || j < 0 || j >= minChess[0].length) return -1; if (minChess[i][j] == 'K') // הגענו למלך return 0; if (minChess[i][j] != '0' && minChess[i][j] != 'H') return -1; // תא מבוקר // סימון התא כמבוקר char saved = minChess[i][j]; minChess[i][j] = 'V'; // visited int min = Integer.MAX_VALUE; // 8 מהלכי פרש אפשריים int[][] moves = {{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}}; for (int[] m : moves) { int result = minPath(minChess, i + m[0], j + m[1]); if (result != -1 && result + 1 < min) min = result + 1; } // שחזור התא minChess[i][j] = saved; return (min == Integer.MAX_VALUE) ? -1 : min; } ``` **הערה:** מכיוון שנדרש ללא לולאות, ניתן לממש עם overloading ופרמטר נוסף של מספר המהלך (0-7), או לכתוב 8 קריאות רקורסיביות מפורשות.