מסלולים במערך דו-ממדי

נתון מערך דו-ממדי mat בגודל n×m (n שורות ו-m עמודות) שערכיו הם מספרים שלמים:

  • נגדיר, מסלול (path) במערך הוא אם הוא מקיים את התנאים הבאים:
    1. המסלול מתחיל בתא הראשון במערך - שורה ראשונה ועמודה ראשונה, ומסתיים בתא האחרון במערך - שורה אחרונה ועמודה אחרונה.
    2. אפשר ללכת רק בכיוונים ימינה ולמטה. כלומר, מתא mat[i][j] אפשר ללכת רק לתא mat[i][j+1] (ימינה) או לתא mat[i+1][j] (למטה).
  • נגדיר, פנייה (turn) במסלול אם הולכים ימינה ומיד אחר כך למטה, או למטה ומיד אחר כך ימינה.

לדוגמה, במערך mat מסומנות שתי פניות:

o מהתא (1,0) לתא (2,0) ומשם לתא (2,1)

o מהתא (0,2) לתא (0,3) ומשם לתא (1,3)

 01234
0     
1     
2     

בהינתן מערך דו-ממדי mat, ומספר שלם k כלשהו. יש להחזיר את מספר המסלולים השונים בהם יש בדיוק k פניות.

לדוגמה, במטריצה מסדר 3×3 הבאה, (בתוך כל תא כתובים האינדקסים שלו)

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

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

אילוצים:

מותר לשנות את המערך במהלך השיטה, אבל בסופה הוא צריך לחזור למצבו המקורי.

דוגמה 1:
קלט: 
mat =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]],
k = 1
פלט: 
2

הסבר: ישנם שני מסלולים עם פנייה אחת בלבד.

דוגמה 2:
קלט: 
mat =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]],
k = 2
פלט: 
2

הסבר: ישנם שני מסלולים עם שתי פניות.

דוגמה 3:
קלט: 
mat =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]],
k = 3
פלט: 
2

הסבר: ישנם שני מסלולים עם שלוש פניות.

דוגמה 4:
קלט: 
mat =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]],
k = 4
פלט: 
0

הסבר: אין מסלול עם ארבע פניות.

דוגמה 5:
קלט: 
mat =
[[0, 0],
 [0, 0]],
k = 0
פלט: 
0

הסבר: אין מסלול עם אפס פניות.

דוגמה 6:
קלט: 
mat =
[[0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]],
k = 3
פלט: 
8

הסבר: ישנם 8 מסלולים עם שלוש פניות.

דוגמה 7:
קלט: 
mat =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]],
k = 0
פלט: 
0

הסבר: אין מסלול עם אפס פניות.

דוגמה 8:
קלט: 
mat =
[[0, 0, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]],
k = 2
פלט: 
3

הסבר: ישנם 3 מסלולים עם שתי פניות.

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

קלט:

mat =
[[0, 0, 0],
 [0, 0, 0],
 [0, 0, 0]],
k = 1

הפלט המבוקש:

2