שלום לכולם,

ברשותי מטריצה בינארית כלשהי (לצורך העניין 10 על 10 אבל זה לא באמת משנה) אשר מייצגת מבוך.

0 - זה מקום שבו מותר לי להתקדם ו1 - זה מכשול/קיר שבו אסור לי לדרוך.

אני שובר את הראש כבר למעלה משבוע ולא מוצא אלגוריתם מסויים, כיצד אפשר לבנות עץ, אשר ממפה את כל הדרכים האפשרויות שבהם אפשר ללכת מנקודה מסויימת מבלי לחזור על אותה נקודה פעמיים.

אני יודע שאני אמור להשתמש במבנים אך לא במערכים נוספים מלבד המערך הדו מימדי שמכיל את המטריצה שלי.

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

תודה מראש לעוזרים!

לא ברור לי מה הכוונה בשורה "

אני אמור להשתמש במבנים אך לא במערכים נוספים". באיזה מן מבנים כן מותר לך להשתמש? בסופו של דבר כמעט כל מבנה מתבסס על מערכים...

ומה הכוונה ב"ממפה את כל הדרכים"? איך עץ אמור לייצג דבר כזה?

typedef struct points

}

;int x

;int data

;struct points *left

;struct points *right

;struct points *up

;struct points *down

{

point;

אני אמור לממש מין מבנה שכזה רק שאין לי מושג איך... ולהשתמש בו כדי לבנות עץ שממפה את כל הדרכים האפשרויות שבהם אפשר ללכת בתוך המטריצה

לשאלתך בקשר למערך, מותר לי להשתמש רק במערך שבתוכו נמצאת המטריצה

אגב זאת שפת C.

עץ (לא בינארי) פשוט. השורש מחזיק את המיקום הנוכחי ויש לו בן לכל תא אחר שאפשר להגיע אליו וכן הלאה.

השאלה היא איך אתה מסתדר עם "בלי לחזור על נקודה פעמיים"? מימוש נאיבי פשוט יכיל מפה של כל התאים במטריצה וכל פעם שהגעת לתא מסוים, תסמן אותו (אם הוא מסומן, אל תוסיף את הבן הזה לאותו צומת). הבעיה נעוצה בכך שלא כל מסלול מגיע לנקודה המבוקשת.

נניח שהתקדמתי כך : מתא 1 לתא 3 לתא 4 לתא 6, אז לא לחזור ולדרוך אחר כך איכשהו על תא 3 לדוגמא (או על כל תא אחר שכבר היית בו במסלול הנוכחי)

בקשר לעץ, לכל איבר אמורים להיות 3 בנים (או 4 רק אם זה השורש - התא הראשון)

מה משמעות השדה x?

שוב.. זוהי דוגמה למבנה שאני אמור להשתמש בו, רק שאני לא יודע איך ליישם אותו, אין לי רעיון, בגלל זה אני מחפש אלגוריתם לדבר..

אני יודע שבDATA אני אמור לקבל את קואורדינטות התא במטריצה, לגביי X יכול להיות שהוא מיותר שם, אני לא יודע להגיד..

אתה מכיר את האלגוריתם BFS? עם כמה שינויים קטנים אתה יכול להשיג את כל המסלולים.

מכיר את האלגוריתם אבל נראה שהוא מדבר על עץ בינארי ולא עץ עם יותר משני בנים לכל אב

ממש לא.

BFS הוא אלגוריתם גרפים כללי, לא קשור ספציפית לעצים.

קרא עוד כאן: http://ldc.usb.ve/~gabro/teaching/CI2693/lecture11.pdf ותראה אם צץ לך רעיון.