נתון מערך דו-ממדי mat, שערכיו הם המספרים השלמים 1, 0 או -1. מספר השורות לא בהכרח שווה למספר העמודות.
נגדיר, מסלול במערך אם הוא מקיים את התנאים הבאים:
mat[0][0] (שורה ראשונה ועמודה ראשונה)1 או 0.יש להחזיר את סכום הנקודות המקסימלי אליו אפשר להגיע במסלול כלשהו במערך הדו מימדי mat.
לדוגמה, מספר הנקודות המקסימלי במערך הבא הוא 9.
| 0 | 1 | 2 | 3 | 4 | |
| 0 | 1 | 1 | -1 | 1 | 1 |
| 1 | 1 | 0 | 0 | -1 | 1 |
| 2 | 1 | 1 | 1 | 1 | -1 |
| 3 | -1 | -1 | 1 | 1 | 1 |
| 4 | 1 | 1 | -1 | -1 | 1 |
אם בתא [0][0] הערך הוא -1 יוחזר -1.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
מותר לשנות את המערך במהלך השיטה, אבל בסופה הוא צריך לחזור למצבו המקורי.
mat = [[1, 1, -1, 1, 1], [1, 0, 0, -1, 1], [1, 1, 1, 1, -1], [-1, -1, 1, 1, 1], [1, 1, -1, -1, 1]]
9
הסבר: המסלול המקסימלי האפשרי הוא 9, כאשר עוברים בתאים שמכילים 1 או 0 בלבד.
mat = [[1, 0, 1], [0, 1, 0], [1, 0, 1]]
5
הסבר: המסלול המקסימלי האפשרי הוא 5, כאשר עוברים בתאים שמכילים 1 או 0 בלבד.
mat = [[1, -1, 1], [-1, 1, -1], [1, -1, 1]]
1
הסבר: המסלול המקסימלי האפשרי הוא 1, כאשר עוברים בתאים שמכילים 1 בלבד.
mat = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
0
הסבר: המסלול המקסימלי האפשרי הוא 0, כאשר עוברים בתאים שמכילים 0 בלבד.
mat = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
9
הסבר: המסלול המקסימלי האפשרי הוא 9, כאשר עוברים בתאים שמכילים 1 בלבד.
mat = [[1, 0, -1], [1, 0, 1], [-1, 1, 0]]
2
הסבר: המסלול המקסימלי האפשרי הוא 2, כאשר עוברים בתאים שמכילים 1 או 0 בלבד.
mat = [[-1, -1, -1], [-1, -1, -1], [-1, -1, -1]]
-1
הסבר: אין מסלול אפשרי כי כל התאים מכילים -1.
mat = [[1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1]]
8
הסבר: המסלול המקסימלי האפשרי הוא 8, כאשר עוברים בתאים שמכילים 1 או 0 בלבד.
קלט:
mat = [[1, 1, -1, 1, 1], [1, 0, 0, -1, 1], [1, 1, 1, 1, -1], [-1, -1, 1, 1, 1], [1, 1, -1, -1, 1]]
הפלט המבוקש:
9