המסלול הגדול ביותר

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

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

סדר המסלולים בהדפסה הינו: למטה -> שמאלה -> ימינה -> למעלה

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

אילוצים:
  • מותר לשנות את המטריצה במהלך השיטה, אבל המטריצה צריכה לחזור לקדמותה לאחר ביצוע השיטה.
  • במטריצה יש רק ספרות (מספרים שלמים בין 0 ל-9) ובתא היעד נמצאת הספרה 1.
  • המטריצה לא בהכרח ריבועית. כלומר, מספר השורות אינו שווה בהכרח למספר העמודות (אבל מספר העמודות זהה בכל שורה).
  • קיימת תשובה חוקית אחת ויש חשיבות לסדר המסלולים בהדפסה.
דוגמה 1:
קלט: 
matrix = 
[[2, 3],
 [4, 1]]
פלט: 
(0,0) --> (1,0) --> (1,1) = 7
(0,0) --> (1,0) --> (0,0) --> (1,0) --> (1,1) = 13
(0,0) --> (1,0) --> (0,0) --> (0,1) --> (1,1) = 12
(0,0) --> (0,1) --> (1,1) = 6
(0,0) --> (0,1) --> (0,0) --> (1,0) --> (1,1) = 12
(0,0) --> (0,1) --> (0,0) --> (0,1) --> (1,1) = 11
13

הסבר: הנה הסבר קצר לאחד מהמסלולים לעיל: 12 = (1,1) <-- (1,0) <-- (0,0) <-- (0,1) <-- (0,0) התחלנו בתא (0,0) שערכו 2, ולכן מותר לבקר בו פעמיים בלבד, ונשארה לנו פעם אחת לבקר בו. עברנו לתא (1,0) שערכו 4, משם חזרנו לתא (0,0), ואי אפשר לבקר בו יותר. משם ערבנו לבקר בתא (0,1) שערכו 3. אנחנו לא יכולים לחזור לתא (0,0) כי כבר ביקרנו בו פעמיים, אי אפשר לחזור לתא (1,0) כי הוא באלכסון, ולכן משם עברנו לתא היעד (1,1). כיוון שערכו 1, ואנחנו מבקרים בו, אנחנו לא יכולים לחזור לשום תא אחר, כי לא נוכל להגיע שוב לתא (1,1). לכן סכום המסלול שלנו הוא 12=.2+4+2+3+1 עבור המטריצה זאת תחזיר השיטה את הערך 13 שהוא סך הערכים המקסימלי אשר מתקבל במסלול חוקי כלשהו במטריצה הנתונה.

דוגמה 2:
קלט: 
matrix = 
[[1, 1, 1],
 [1, 9, 1],
 [1, 1, 1]]
פלט: 
(0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) = 5
(0,0) --> (1,0) --> (2,0) --> (2,1) --> (1,1) --> (1,2) --> (2,2) = 15
(0,0) --> (1,0) --> (2,0) --> (2,1) --> (1,1) --> (0,1) --> (1,1) --> (1,2) --> (2,2) = 25
(0,0) --> (1,0) --> (2,0) --> (2,1) --> (1,1) --> (0,1) --> (0,2) --> (1,2) --> (2,2) = 17
(0,0) --> (1,0) --> (1,1) --> (2,1) --> (2,2) = 13
(0,0) --> (1,0) --> (1,1) --> (2,1) --> (1,1) --> (1,2) --> (2,2) = 23
(0,0) --> (1,0) --> (1,1) --> (2,1) --> (1,1) --> (0,1) --> (1,1) --> (1,2) --> (2,2) = 33
(0,0) --> (1,0) --> (1,1) --> (2,1) --> (1,1) --> (0,1) --> (0,2) --> (1,2) --> (2,2) = 25
(0,0) --> (1,0) --> (1,1) --> (1,2) --> (2,2) = 13
(0,0) --> (1,0) --> (1,1) --> (1,2) --> (1,1) --> (2,1) --> (2,2) = 23
(0,0) --> (1,0) --> (1,1) --> (1,2) --> (1,1) --> (0,1) --> (1,1) --> (2,1) --> (2,2) = 33
(0,0) --> (1,0) --> (1,1) --> (1,2) --> (0,2) --> (0,1) --> (1,1) --> (2,1) --> (2,2) = 25
(0,0) --> (1,0) --> (1,1) --> (0,1) --> (1,1) --> (2,1) --> (2,2) = 23
(0,0) --> (1,0) --> (1,1) --> (0,1) --> (1,1) --> (2,1) --> (1,1) --> (1,2) --> (2,2) = 33
(0,0) --> (1,0) --> (1,1) --> (0,1) --> (1,1) --> (1,2) --> (2,2) = 23
(0,0) --> (1,0) --> (1,1) --> (0,1) --> (1,1) --> (1,2) --> (1,1) --> (2,1) --> (2,2) = 33
(0,0) --> (1,0) --> (1,1) --> (0,1) --> (0,2) --> (1,2) --> (2,2) = 15
(0,0) --> (1,0) --> (1,1) --> (0,1) --> (0,2) --> (1,2) --> (1,1) --> (2,1) --> (2,2) = 25
(0,0) --> (0,1) --> (1,1) --> (2,1) --> (2,0) --> (1,0) --> (1,1) --> (1,2) --> (2,2) = 25
(0,0) --> (0,1) --> (1,1) --> (2,1) --> (2,2) = 13
(0,0) --> (0,1) --> (1,1) --> (2,1) --> (1,1) --> (1,0) --> (1,1) --> (1,2) --> (2,2) = 33
(0,0) --> (0,1) --> (1,1) --> (2,1) --> (1,1) --> (1,2) --> (2,2) = 23
(0,0) --> (0,1) --> (1,1) --> (1,0) --> (2,0) --> (2,1) --> (2,2) = 15
(0,0) --> (0,1) --> (1,1) --> (1,0) --> (2,0) --> (2,1) --> (1,1) --> (1,2) --> (2,2) = 25
(0,0) --> (0,1) --> (1,1) --> (1,0) --> (1,1) --> (2,1) --> (2,2) = 23
(0,0) --> (0,1) --> (1,1) --> (1,0) --> (1,1) --> (2,1) --> (1,1) --> (1,2) --> (2,2) = 33
(0,0) --> (0,1) --> (1,1) --> (1,0) --> (1,1) --> (1,2) --> (2,2) = 23
(0,0) --> (0,1) --> (1,1) --> (1,0) --> (1,1) --> (1,2) --> (1,1) --> (2,1) --> (2,2) = 33
(0,0) --> (0,1) --> (1,1) --> (1,2) --> (2,2) = 13
(0,0) --> (0,1) --> (1,1) --> (1,2) --> (1,1) --> (2,1) --> (2,2) = 23
(0,0) --> (0,1) --> (1,1) --> (1,2) --> (1,1) --> (1,0) --> (2,0) --> (2,1) --> (2,2) = 25
(0,0) --> (0,1) --> (1,1) --> (1,2) --> (1,1) --> (1,0) --> (1,1) --> (2,1) --> (2,2) = 33
(0,0) --> (0,1) --> (0,2) --> (1,2) --> (2,2) = 5
(0,0) --> (0,1) --> (0,2) --> (1,2) --> (1,1) --> (2,1) --> (2,2) = 15
(0,0) --> (0,1) --> (0,2) --> (1,2) --> (1,1) --> (1,0) --> (2,0) --> (2,1) --> (2,2) = 17
(0,0) --> (0,1) --> (0,2) --> (1,2) --> (1,1) --> (1,0) --> (1,1) --> (2,1) --> (2,2) = 25
33

הסבר: במטריצה זו התא האמצעי עם ערך 9 מאפשר מספר רב של ביקורים. המסלול המקסימלי יבקר בתא זה מספר פעמים כדי למקסם את הסכום, עם סכום כולל של 33.

דוגמה 3:
קלט: 
matrix = 
[[2, 2],
 [2, 1]]
פלט: 
(0,0) --> (1,0) --> (1,1) = 5
(0,0) --> (1,0) --> (0,0) --> (1,0) --> (1,1) = 9
(0,0) --> (1,0) --> (0,0) --> (0,1) --> (1,1) = 9
(0,0) --> (0,1) --> (1,1) = 5
(0,0) --> (0,1) --> (0,0) --> (1,0) --> (1,1) = 9
(0,0) --> (0,1) --> (0,0) --> (0,1) --> (1,1) = 9
9

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

דוגמה 4:
קלט: 
matrix = 
[[3, 0, 1],
 [2, 0, 4],
 [1, 2, 1]]
פלט: 
(0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) = 9
(0,0) --> (1,0) --> (0,0) --> (1,0) --> (2,0) --> (2,1) --> (2,2) = 14
14

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

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

קלט:

matrix = 
[[2, 3],
 [4, 1]]

הפלט המבוקש:

(0,0) --> (1,0) --> (1,1) = 7
(0,0) --> (1,0) --> (0,0) --> (1,0) --> (1,1) = 13
(0,0) --> (1,0) --> (0,0) --> (0,1) --> (1,1) = 12
(0,0) --> (0,1) --> (1,1) = 6
(0,0) --> (0,1) --> (0,0) --> (1,0) --> (1,1) = 12
(0,0) --> (0,1) --> (0,0) --> (0,1) --> (1,1) = 11
13