נתון מערך דו-ממדי ריבועי המכיל מספרים שלמים חיוביים בלבד (גדולים מאפס).
נגדיר מסלול path במערך כאוסף של תאים סמוכים. תאים סמוכים יכולים להיות שכנים מלמעלה, מלמטה, מימין ומשמאל. לא באלכסון. כל מסלול יכול לבקר בכל תא פעם אחת בלבד.
בהינתן מערך דו-ממדי mat המכיל מספרים שלמים חיוביים ממש (גדולים מאפס), מספר sum שלם חיובי כלשהות ומערך דו-ממדי path באותו גודל של mat.
יש לבדוק אם קיים מסלול במערך שסכום ערכיו הוא sum. אם קיים מסלול כזה יוחזר true. אחרת יוחזר הערך false. המסלול יכול להתחיל בכל תא במערך.
המערך path משמש לסימון המסלול שסכומו sum.
בתחילה, כשהמערך path מועבר כפרמטר, כל תאיו מכילים את הערך 0.
בסיום השיטה, אם יש מסלול במערך mat שסכומו sum, המערך path יכיל 1 בתאים שמשתתפים במסלול ו- 0 בכל שאר התאים. אם אין מסלול כזה במערך mat, המערך path צריך להכיל בכל תאיו את הערך 0.
אם קיים יותר ממסלול אחד שסכומו sum, המערך path יכיל את אחד המסלולים שסכומו sum (באופן שרירותי).
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
אסור לשנות את המערך mat במהלך השיטה, גם אם מחזירים אותו למצבו ההתחלתי בסופה.
mat = [[2, 41, 3, 14], [2, 1, 24, 7], [2, 15, 10, 54], [63, 22, 2, 4]], sum = 4, path = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
[[1, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] true
mat = [[2, 41, 3, 14], [2, 1, 24, 7], [2, 15, 10, 54], [63, 22, 2, 4]], sum = 9, path = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] false
קלט:
mat = [[2, 41, 3, 14], [2, 1, 24, 7], [2, 15, 10, 54], [63, 22, 2, 4]], sum = 4, path = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
הפלט המבוקש:
[[1, 0, 0, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] true