השאלה הבאה מדמה משחק "תפזורת".
נתון מערך דו-ממדי ריבועי המלא בתווים (char). נגדיר שמחרוזת תווים קיימת במערך אם כל תווי המחרוזת נמצאים כסדרם במערך, ואפשר להגיע מתו אחד לתו שאחריו בסדרה על-ידי מעבר מתא לאחד מארבעת שכניו שמאל, ימין, למעלה, למטה). לא באלכסון.
לדוגמה, אם המערך הוא זה:
| 0 | 1 | 2 | 3 | 4 | |
| 0 | t | z | x | c | d |
| 1 | s | h | a | z | x |
| 2 | h | w | l | o | m |
| 3 | o | r | n | t | n |
| 4 | a | b | r | i | n |
המחרוזת "shalom" קיימת ומסומנת במערך. מתחילה בתא (1,0) ומסתיימת בתא (2, 4).
בהינתן מערך שכזה וכן מחרוזת המייצגת מילה. יש לבדוק אם המילה קיימת במערך או לא. אם המילה קיימת במערך, יש להדפיס את "הנתיב" שלה. ההדפסה תיעשה בעזרת מטריצת מעקב שתגדירו, שהיא בגודלה של המטריצה המקורית, ובתאים שלה יהיו מספרים שלמים. (בהמשך השאלה יש הסבר מדויק לגבי ההדפסה). בסוף השיטה, במטריצת המעקב צריכים להיות בתאים של המחרוזת, מספרי התווים המרכיבים את המחרוזות, ובתאים שאין בהם תווים של המחרוזת יהיו אפסים. לדוגמה, עבור המערך שלעיל והמחרוזת "shalom" מטריצת המעקב תהיה:
| 0 | 1 | 2 | 3 | 4 | |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 2 | 3 | 0 | 0 |
| 2 | 0 | 0 | 4 | 5 | 6 |
| 3 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 |
אם המילה אינה קיימת יודפס "No Such Word". אם המילה מופיעה יותר מפעם אחת, יודפס המופע הראשון בלבד. אם מצאת אותה, אין להשתמש באותו תא יותר מפעם אחת. במילים אחרות, תו לא יכול להופיע יותר מפעם אחת.
השיטה צריכה להיות רקורסיבית ללא שימוש בלולאות כלל. כך גם כל שיטות העזר (אם תכתבו) לא יכולות להכיל לולאות.
המערך מכיל אותיות קטנות בלבד וגם במחרוזת יש אותיות קטנות בלבד.
לגבי הדפסת הנתיב – עליכם ליצור את מטריצת המעקב, ואז לקרוא לשיטה בשם printArr המקבלת כפרמטר מערך דו-מימדי ומדפיסה אותו.
מותר לשנות את המערך במהלך השיטה, אבל בסופה הוא צריך לחזור למצבו המקורי.
arr = [['t', 'z', 'x', 'c', 'd'], ['s', 'h', 'a', 'z', 'x'], ['h', 'w', 'l', 'o', 'm'], ['o', 'r', 'n', 't', 'n'], ['a', 'b', 'r', 'i', 'n']], word = "shalom"
0 0 0 0 0 1 2 3 0 0 0 0 4 5 6 0 0 0 0 0 0 0 0 0 0
הסבר: המחרוזת "shalom" נמצאת במערך ומסומנת בסדר המספרים כפי שמופיעים.
arr = [['t', 'z', 'x', 'c', 'd'], ['a', 'h', 's', 'h', 'w'], ['a', 'b', 'r', 'i', 'n'], ['a', 'm', 'o', 'b', 'n']], word = "hello"
No Such Word
הסבר: המחרוזת "hello" אינה קיימת במערך.
arr = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']], word = "abc"
1 2 3 0 0 0 0 0 0
הסבר: המחרוזת "abc" נמצאת במערך בשורה הראשונה.
arr = [['l', 'b', 'c'], ['o', 'd', 'f'], ['l', 'h', 'i']], word = "lol"
1 0 0 2 0 0 3 0 0
הסבר: המחרוזת "lol" נמצאת במערך באלכסון.
arr = [['a', 'b', 'c'], ['d', 'e', 'f'], ['g', 'h', 'i']], word = "ghi"
0 0 0 0 0 0 1 2 3
הסבר: המחרוזת "ghi" נמצאת במערך בשורה האחרונה.
arr = [['a', 'b'], ['d', 'c']], word = "abcd"
1 2 4 3
הסבר: המחרוזת "abcd" נמצאת במערך בצורה רציפה.
arr = [['a', 'b'], ['c', 'd']], word = "ac"
1 0 2 0
הסבר: המחרוזת "ac" נמצאת במערך בצורה אנכית.
arr = [['x', 'y', 'z'], ['a', 'z', 'c'], ['d', 'e', 'f']], word = "xyz"
1 2 3 0 3 0 0 0 0
הסבר: המחרוזת "xyz" נמצאת במערך בשורה הראשונה וגם מסתיימת בשורה השנייה
קלט:
arr = [['t', 'z', 'x', 'c', 'd'], ['s', 'h', 'a', 'z', 'x'], ['h', 'w', 'l', 'o', 'm'], ['o', 'r', 'n', 't', 'n'], ['a', 'b', 'r', 'i', 'n']], word = "shalom"
הפלט המבוקש:
0 0 0 0 0 1 2 3 0 0 0 0 4 5 6 0 0 0 0 0 0 0 0 0 0