המסלול הארוך ביותר שקיים במערך דו-ממדי

נתון מערך דו-ממדי mat המכיל את המספרים השלמים 0, 1 ו--1 בלבד. המספר -1 מסמן תא חסום. אנחנו מחפשים מסלול שמתחיל בתא הראשון במערך (שורה ראשונה ועמודה ראשונה) mat[0][0]. המסלול צריך לעבור אך ורק דרך תאים שאינם חסומים (כלומר, רק אם הערך שלהם הוא 0 או 1). המעבר מתא אחד לשני במסלול הוא לפי התנאים הבאים:

  • אם הערך בתא (i, j) הוא 0, אפשר לעבור לאחד מארבעת התאים מימין (שורה i ועמודה j+1), משמאל (שורה i ועמודה j-1), למעלה (שורה i-1 ועמודה j) או למטה (שורה i+1 ועמודה j).
  • אם הערך בתא (i, j) הוא 1, אפשר לעבור לאחד מארבעת התאים באלכסונים: (שורה i+1 ועמודה j+1), (שורה i+1 ועמודה j-1), (שורה i-1 ועמודה j+1) או (שורה i-1 ועמודה j-1).

המסלול יכול לבקר בכל תא במערך פעם אחת בלבד.

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

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

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

לדוגמה, עבור המערך הימני, נקבל שאורך המסלול הוא 7.

במערך הבא ניתן לראות את המסלול באורך המקסימלי (המסלול המודגש).

 0123
01101
1100-1
21-11-1
 0123
01101
1100-1
21-11-1

המסלולים האפשריים במערך הם אלו (אנו סופרים את התאים שמבקרים בהם):

  1. (0,0) → (1,1) → (0,1) → (1,2) → (0,2) → (0,3) - אורך 6
  2. (0,0) → (1,1) → (0,1) → (1,2) → (2,2) - אורך 5
  3. (0,0) → (1,1) → (1,2) → (0,2) → (0,3) - אורך 5
  4. (0,0) → (1,1) → (1,2) → (2,2) - אורך 4
  5. (0,0) → (1,1) → (1,0) → (0,1) → (1,2) → (0,2) → (0,3) - אורך 7
  6. (0,0) → (1,1) → (1,0) → (0,1) → (1,2) → (2,2) - אורך 6

אפשר לראות שהמסלול הארוך ביותר נתקע בשורה 0 עמודה 3, ולא הגיע לסוף המערך.

למעשה אף מסלול לא הגיע לתא האחרון במערך (שורה אחרונה ועמודה אחרונה), שכן הערך בתא זה הוא -1 ולכן אינו יכול להשתתף באף מסלול.

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

אילוצים:
  • מותר לשנות את המערך במהלך השיטה, אבל המערך צריך לחזור לקדמותו לאחר ביצוע השיטה.
  • אסור ליצור מערך נוסף!
דוגמה 1:
קלט: 
mat = 
[[1, 1, 0, 1],
 [1, 0, 0, -1],
 [1, -1, 1, -1]]
פלט: 
7

הסבר: אורך המסלול הארוך ביותר שקיים במערך הוא 7

דוגמה 2:
קלט: 
mat =
[[0, 1, 0],
 [1, 0, 1],
 [0, 1, 0]]
פלט: 
5
Loading...
נשמרLn 1, Col 1

קלט:

mat = 
[[1, 1, 0, 1],
 [1, 0, 0, -1],
 [1, -1, 1, -1]]

הפלט המבוקש:

7