בעיית המסלול המיוחד

נתונה מטריצה (מערך דו-ממדי) mat המכילה אך ורק את הערכים 0 או 1.

נגדיר מסלול (path) במטריצה, אם הוא מקיים את התנאים הבאים:

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

כתבו את השיטה:

checkPath הבודקת האם קיימים מסלולים במטריצה (כפי שהוגדר לעיל). אם קיים לפחות מסלול אחד, יש להחזיר true, אחרת להחזיר false.

כתבו את השיטה:

countPathsThroughOnes המחזירה את מספר המסלולים שיש במערך, אם אין מסלולים כאלו, יוחזר 0.

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

אילוצים:
  • מותר לשנות את המטריצה הנתונה, אך עם סיום הריצה, על המטריצה להיות במצבה במקורי. אסור ליצור מטריצה נוספת.
  • המטריצה הנשלחת כפרמטר לשיטה אינה null.
דוגמה 1:
קלט: 
mat =
[[1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 1]]
פלט: 
true
4

הסבר: קיימים ארבעה מסלולים אפשריים לתא (3,4)

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

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

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

הסבר: לא ניתן להגיע לכל האחדים במסלול חוקי

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

הסבר: קיים מסלול אחד העובר בכל האחדים

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

הסבר: לא ניתן לעבור בכל האחדים במסלול חוקי

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

הסבר: לא ניתן לעבור בכל האחדים במסלול חוקי

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

הסבר: מטריצה 1x2 עם מסלול חוקי

דוגמה 8:
קלט: 
mat =
[[1]]
פלט: 
true
1

הסבר: מטריצה 1x1 היא מסלול חוקי בעצמה

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

קלט:

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

הפלט המבוקש:

true
4