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