מסלול עם סכום חיובי מינימלי מהתא הראשון לתא האחרון
נתון מערך דו-ממדי mat, המכיל מספרים שלמים (חיוביים, שליליים ואפסים) ומספר שלם number.
אנחנו מעוניינים לעבור במסלול במערך שמתחיל בתא הראשון (0, 0) ומסתיים בתא האחרון (mat.length-1, mat[0].length-1), כאשר אפשר לעבור מתא (i,j) אך ורק שורה אחת למטה או עמודה אחת ימינה, כלומר לתא (i+1, j) או לתא (i, j+1).
בכל ביקור בתא, המספר שנמצא בתא מתווסף (בין אם המספר הוא חיובי או שלילי) למספר number. אפשר לבקר בתא רק אם המספר number הוא חיובי ממש (לפני ואחרי שהתא מתווסף למספר). שימו לב, בכל ביקור בתא - כולל בתאים הראשון והאחרון.
יש להחזיר את ערכו של המספר המינימלי שצריך להיות בהתחלה במספר number כדי להצליח לעבור מהתא הראשון לתא האחרון במערך.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
- מותר לשנות את המטריצה במהלך השיטה, אבל המטריצה צריכה לחזור לקדמותה לאחר ביצוע השיטה.
- המטריצה לא בהכרח ריבועית. כלומר, מספר השורות אינו שווה בהכרח למספר העמודות (אבל מספר העמודות זהה בכל שורה).
mat = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
7
הסבר: המספר ההתחלתי המינימלי הוא 7. המסלול המיטבי: (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2). אם בהתחלה number = 7, לאחר ביקור בתא (0,0) ערכו יהיה 5, לאחר (0,1) יהיה 2, לאחר (0,2) יהיה 5, לאחר (1,2) יהיה 6 ולאחר (2,2) יהיה 1. כלומר number חיובי לאורך כל המסלול. במסלול (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) היה צורך ב-8 לפחות.
mat = [[-5, -3], [-11, 2]]
9
הסבר: המסלול המיטבי הוא (0,0) -> (0,1) -> (1,1). אם נתחיל עם number = 9, אז לאחר ביקור בתא (0,0) יהיה number = 4, לאחר ביקור בתא (0,1) יהיה number = 1, ולאחר ביקור בתא (1,1) יהיה number = 3. כלומר number נשאר חיובי לאורך כל המסלול.
mat = [[10, -15], [-20, 5]]
6
הסבר: המסלול המיטבי הוא (0,0) -> (0,1) -> (1,1). אם נתחיל עם number = 6, אז לאחר ביקור בתא (0,0) יהיה number = 16, לאחר ביקור בתא (0,1) יהיה number = 1, ולאחר ביקור בתא (1,1) יהיה number = 6. כלומר number נשאר חיובי לאורך כל המסלול.
mat = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
1
הסבר: כל התאים מכילים 1, ולכן בכל תא הערך של number יגדל ב-1. לכן מספיק להתחיל עם number = 1 כדי שהוא יישאר חיובי לאורך כל המסלול.
mat = [[-100, -100], [-100, -100]]
301
הסבר: כל התאים מכילים -100, ולכן number יקטן ב-100 בכל תא. כל מסלול עובר דרך 3 תאים, ולכן כדי ש-number יישאר חיובי בכל התאים הוא חייב להתחיל בלפחות 301 (301 -> 201 -> 101 -> 1).
mat = [[100]]
1
הסבר: יש רק תא אחד עם הערך 100. כדי ש-number יהיה חיובי לפני ואחרי הביקור בתא, מספיק להתחיל עם 1.
mat = [[-5]]
6
הסבר: יש רק תא אחד עם הערך -5. כדי ש-number יישאר חיובי גם אחרי הביקור בתא, צריך להתחיל עם 6 (6 -> 1).
mat = [[-1, -2, -3]]
7
הסבר: במערך שורה אחת יש מסלול יחיד. אם נתחיל עם number = 7, לאחר ביקור בתא (0,0) יהיה 6, לאחר (0,1) יהיה 4, ולאחר (0,2) יהיה 1. כלומר number נשאר חיובי לאורך כל המסלול.
mat = [[0, 0], [0, 0]]
1
הסבר: כל התאים מכילים 0, ולכן ערכו של number לא משתנה. מספיק להתחיל עם number = 1.