מסלול פרש מינימלי בלוח שחמט

נתון מערך דו-ממדי minChess אשר מייצג שולחן מיני-שחמט בגודל ריבועי k × k.

  • minChess[i][j] = '0' - מייצג תא ריק על שולחן השחמט.
  • minChess[i][j] = 'K' - מייצג מקום בו נמצא המלך (king).
  • minChess[i][j] = 'H' - מייצג מקום בו נמצא הפרש (horse).

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

סימני ה-X מסמנים את המיקום אליהם מגיע הפרש.

 01234567
0    X X 
1   X   X
2     ♞  
3   X   X
4    X X 
5 X      
6  X     
7♞       

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

בהינתן המערך minChess והמיקום של הפרש (שורה i ועמודה j), יש להחזיר את אורכו של המסלול הקצר ביותר מהפרש אל המלך, אם אין מסלול כזה, יוחזר הערך -1.

השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.

אילוצים:
  • ערכי המערך הם חוקיים כפי שמתואר, ולא יהיו ערכים אחרים.
  • הפרש והמלך נמצאים במיקומים שונים במערך.
  • ערכי המערך לאחר הפעלת השיטה צריכים להיות זהים לערכים ההתחלתיים.
דוגמה 1:
קלט: 
minChess =
[['0','0','0','0'],
 ['0','0','0','0'],
 ['0','0','K','0'],
 ['H','0','0','0']],
i = 3,
j = 0
פלט: 
1

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 1

דוגמה 2:
קלט: 
minChess =
[['0','0','0','0'],
 ['0','0','K','0'],
 ['0','0','0','0'],
 ['H','0','0','0']],
i = 3,
j = 0
פלט: 
4

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 4

דוגמה 3:
קלט: 
minChess =
[['0','0','K','0'],
 ['0','0','0','0'],
 ['0','0','0','0'],
 ['H','0','0','0']],
i = 3,
j = 0
פלט: 
3

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 3

דוגמה 4:
קלט: 
minChess =
[['K','0','0'],
 ['0','0','0'],
 ['0','0','H']],
i = 2,
j = 2
פלט: 
4

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 4

דוגמה 5:
קלט: 
minChess =
[['0','0','K'],
 ['H','0','0'],
 ['0','0','0']],
i = 1,
j = 0
פלט: 
1

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 1

דוגמה 6:
קלט: 
minChess =
[['0','0','0','K'],
 ['0','0','0','0'],
 ['0','0','0','0'],
 ['H','0','0','0']],
i = 3,
j = 0
פלט: 
2

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 2

דוגמה 7:
קלט: 
minChess =
[['H','K'],
 ['0','0']],
i = 0,
j = 0
פלט: 
-1

הסבר: לא קיים מסלול כי הלוח קטן מדי

דוגמה 8:
קלט: 
minChess =
[['0','0','0','0'],
 ['0','0','0','0'],
 ['0','0','0','0'],
 ['H','K','0','0']],
i = 3,
j = 0
פלט: 
3

הסבר: המסלול המינימלי מנקודת ההתחלה הוא באורך 3

Loading...
נשמרLn 1, Col 1

קלט:

minChess =
[['0','0','0','0'],
 ['0','0','0','0'],
 ['0','0','K','0'],
 ['H','0','0','0']],
i = 3,
j = 0

הפלט המבוקש:

1