Soul, אני אומר את האמת- פספסתי לגמרי את התגובה שלך
אני אריץ את זה בטסטים של הקורס במהלך היום, נראה אם זה משפר משהו או שאני נשאר עם הקוד הנוכחי (שאולי לא עובד ב100% מהמקרים, אבל הוא עובד בצורה מספקת סה"כ).
בלי קשר שאני צריך להכניס אולי לmain שלי בדיקה שתגיד שאם המרחק הוא 0 שלא יסדר בכלל (לחסוך עבודה)...
תומריקו פתר נכון. אם הבעיה שלך היא במימוש, אז תגיד. כמו כן, יהיה לך יותר קל לדבג את הקוד אם תכתוב טסט פשוט שמריץ על מערך בגודל קטן, ובודק כל מני שיפטים ותוסיף הדפסות מקוד החיפוש שלך. פשוט ברפרוף על קוד החיפוש הוא מסובך מדי, וזו לרוב בעיה.
נא לא לשלוח לי יותר מה"פ אחת בכל פעם. לפני השליחה, מומלץ לעיין בחוקי הפורום ובשיטת האימות אם עוד לא קראתם אותם.
Soul, שיפרת אותי ל8 טסטים עוברים מתוך 9. אחלה אתה!
הנה השאלה בbacktracking:
מהלך שאינו חותך את עצמו מתואר כסדרה של קטעים במישור היוצרים מסלול רציף כך שכל קטע הוא אופקי או
אנכי ובאורך 1 והמסלול מבקר בכל נקודה לכל היותר פעם אחת. לדוגמא, בציור למטה מופיעים כל המהלכים
שאינם חותכים את עצמם שמתחילים בנקודה השמאלית התחתונה ומסתיימים בנקודה הימנית העליונה עבור
:3 x 3 בגודל סריג
)http://mathworld.wolfram.com/Self-AvoidingWalk.htmlמתוך לקוח(
מהלך שחותך את עצמו פעם אחת הוא מהלך עבורו קיימת לכל היותר נקודה אחת בה הוא עובר פעמיים )ראה
דוגמא למטה(. כתוב תוכנית המקבלת שני מספרים טבעיים )גדולים מאפס( n ו- המייצגים את גודל הסריג.
התכנית תדפיס כתוצאה את מספר המהלכים שחותכים את עצמם פעם אחת על סריג בגודל המתחילים
בנקודה השמאלית התחתונה ונגמרים בנקודה השמאלית העליונה. שים לב! לפי ההגדרה, למסלול אסור לחזור
על אותו קטע פעמיים.
חובה להשתמש ב-backtracking על מנת לפתור את הבעיה! אין להשתמש במשתנים סטטים וגלובלים! בשאלה
זו אין דרישות סיבוכיות, אולם כמקובל בBACKTRACKING, יש לוודא שלא מתבצעות קריאות רקורסיביות
מיותרות עם פתרונות שאינם חוקיים.
ניתן להקצות מראש מערך בגודל 100x100 על מנת להימנע מהקצאה דינמית של מערך דו מימדי.
