موضوع maze از اون موضوع هاییه که همیشه جذابه و چند مسئله مختلف برای حل کردن داره. دیروز کد کاتای مسیریابی maze رو حل کردم. جریان از این قراره که به شما یک رشته کاراکتر میدن به عنوان maze و شما باید ببینی مسیری از خانه 0,0 به خونه n,n هست یا نه. یعنی ورودی تابع یک رشته معادل maze و خروجی تابع true/false هست.
خانه های خالی maze با کاراکتر دات (.) و خانه های پر maze با کاراکتر دابلیو (W) پر شده اند. فرض هم بر اینه که خانه های اول (0,0) و آخر (n,n) همیشه خالی هستند.
اول بریم نمونه مدل های موفق رو ببینیم. یک maze(3x3) که دیواره چپ و پایینش برای عبور بازه و یک maze(6x6) که کلا باز هست و مانعی نداره.
حالا بریم سراغ نمونه هایی که مسیر موفقی ندارند. یک maze(3x3) که یک قطرش کاملا دیواره و یک maze(6x6) که هر دو خانه ماقبل آخرش دیواره و راه رسیدن به خانه آخر بسته شده.
راه حلی که اول به ذهنم رسید؛ این بود که از recursive استفاده کنم و از هر خانه ، چهار طرفش رو چک کنم که مسیر هست یا نه. مسیرهای تکراری رو هم بررسی کنم. اما فکر کردم recursive برای maze های بزرگ ممکنه دردسرساز بشه. برای همین از حلقه بینهایت استفاده کردم. در نهایت راه حلم اینطوری شد که برای هر خانه یک x و یک y در نظر گرفتم و یک moves که شامل جهت های بررسی نشده اون خانه هست. یک آرایه بنام trace رو برای خانه های موجود در نظر بگیرم. اولین عنصر آرایه همیشه خانه ایه که میخوام تستش کنم. به ازای هر خانه جدید، طرف های باقیمونده رو چک میکنم و هر طرف که همسایه خالی باشه، به آرایه trace اضافه میکنم.
البته خورده ریزه هایی هم در این الگوریتم هست. اگر برای خانه فعلی جهتی نمونده باشه، در واقع به بن بست رسیدم و برمیگردم و عنصر قبلی رو چک میکنم. اگر از عنصر صفرم برگردم به عقب، یعنی کلا راهی پیدا نکردم. همینطور از یک Set بنام tracedList هم برای بررسی خانه های قبلا چک شده استفاده کردم که جلوی loop های بزرگ رو بگیرم.
اینطوری شد که در نهایت به راه حل زیر رسیدم ( t همون اشاره گر به خانه فعلی در آرایه trace هست):
و مورد قبول واقع شد. خوشحال بودم که رد نشده، ولی وقتی رفتم و راه حل های دیگه رو دیدم، این راه حل رو دیدم که همون recursive بود و به مراتب ساده تر:
یک حرکت هوشمندانه و قشنگ کرده. خانه ای که بررسی میکنه رو با کاراکتر 'x' پر میکنه و مثل من از یک دیتاست جدا به نام tracedList استفاده نکرده. واقعا هم از حلش لذت بردم و هم از دیدن این راه حل عالی. و امیدوارم در مورد راه حل های recursive ، بهتر شرایط رو بررسی کنم.
:)
