נתון מערך דו-ממדי mat, המכיל מספרים שלמים ומספר שלם number.
אנחנו מעוניינים לעבור במסלול במערך שמתחיל בתא האחרון שהוא התא (mat.length-1, mat[0].length-1) עד לתא הראשון (0, 0), כאשר אפשר לעבור מתא (i,j) אך ורק שורה אחת למעלה או עמודה אחת שמאלה, כלומר לתא (i-1, j) או לתא (i, j-1).
בכל ביקור בתא, המספר שנמצא בתא מתווסף (בין אם המספר הוא חיובי או שלילי) למספר number. אפשר לבקר בתא רק אם המספר number הוא חיובי ממש (לפני ואחרי שהתא מתווסף למספר). שימו לב, בכל ביקור בתא - כולל בתאים הראשון והאחרון.
יש להחזיר את ערכו של המספר המינימלי שצריך להיות בהתחלה במספר number כדי להצליח לעבור מהתא האחרון לתא הראשון במערך.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
mat = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
6
הסבר: המספר המינימלי ההתחלתי של number צריך להיות 6 שכן אז אפשר ללכת במסלול: (2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0) אם בהתחלה number = 6, לאחר ביקור בתא (2,2) ערכו של number יהיה 1, לאחר ביקור בתא (2,1) ערכו יהיה 31, לאחר ביקור בתא (2,0) ערכו יהיה 41, לאחר ביקור בתא (1,0) ערכו יהיה 36 ולאחר ביקור בתא (0,0) ערכו יהיה 34. כלומר, הערך של number היה חיובי לכל אורך המסלול.
mat = [[7, -12, -3], [2, 6, -10], [-10, -5, 1]]
5
הסבר: השיטה תחזיר 5.
mat = [[-2, -3, 3, -4, 5, -6, 7, -8, 9, -10], [-11, 12, -13, 14, -15, 16, -17, 18, -19, 20], [21, -22, 23, -24, 25, -26, 27, -28, 29, -30], [-31, 32, -33, 34, -35, 36, -37, 38, -39, 40], [41, -42, 43, -44, 45, -46, 47, -48, 49, -50], [-51, 52, -53, 54, -55, 56, -57, 58, -59, 60], [61, -62, 63, -64, 65, -66, 67, -68, 69, -70], [-71, 72, -73, 74, -75, 76, -77, 78, -79, 80], [81, -82, 83, -84, 85, -86, 87, -88, 89, -90], [-91, 92, -93, 94, -95, 96, -97, 98, -99, 100]]
1
הסבר: השיטה תחזיר 1.
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 תאים: (1,1) -> (0,1) -> (0,0). לכן, כדי שnumber יישאר חיובי בכל התאים, הוא חייב להתחיל בלפחות 301.
mat = [[100]]
1
הסבר: במקרה זה יש רק תא אחד עם הערך 100. כדי שnumber יהיה חיובי לפני ואחרי הביקור בתא, מספיק להתחיל עם 1.
mat = [[-5,-3], [-11,2]]
7
הסבר: המסלול המיטבי יהיה (1,1) -> (0,1) -> (0,0). אם נתחיל עם number = 7, אז לאחר ביקור בתא (1,1) יהיה number = 9, לאחר ביקור בתא (0,1) יהיה number = 6, ולאחר ביקור בתא (0,0) יהיה number = 1, כך שnumber נשאר חיובי לאורך כל המסלול.
mat = [[10, -15], [-20, 5]]
11
הסבר: המסלול המיטבי יהיה (1,1) -> (0,1) -> (0,0). אם נתחיל עם number = 11, אז לאחר ביקור בתא (1,1) יהיה number = 16, לאחר ביקור בתא (0,1) יהיה number = 1, ולאחר ביקור בתא (0,0) יהיה number = 11, כך שnumber נשאר חיובי לאורך כל המסלול.
קלט:
mat = [[-2, -3, 3], [-5, -10, 1], [10, 30, -5]]
הפלט המבוקש:
6