این مقاله در ادامه کد کاتای قبل هست که ببینیم مسیری از ابتدا به انتهای maze وجود داره یا نه. اگر دوست داشتید، مقاله قبل رو میتونید اینجا بخوانید.
بعد از اینکه کد کاتای اول maze رو حل کردم، مرحله دومش که پیدا کردن کوتاه ترین مسیر بود، از ذهنم بیرون نمیرفت. ایده رسیدن از بهترین الگوریتم کاتای اول به این الگوریتم، تو ذهنم میچرخید. بالاخره خسته شدم و اومدم حلش کنم. بهترین الگوریتم کاتای قبل به صورت زیر بود:
برای تبدیل الگوریتم بالا به الگوریتم پیدا کردن کوتاه ترین مسیر، چند تا ایده به ذهنم رسید و کمتر از 5 دقیقه به جواب مدنظر رسیدم.
اول به ذهنم رسید که در حین گشتن در maze علاوه بر مختصات x و y، وزن مسیر (پارامتر weight) رو هم ارسال کنم و از هرخانه ای که به خانه مجاور میروم، یک واحد به وزن دریافت شده اضافه کنم.
همچنین بجای ذخیره کاراکتر 'x' در هر خانه، اگر خانه خالی بود یا قبلا با وزن بیشتری به این خانه رسیده بودم، وزن بهینه تر رو براش ذخیره کنم.
شرط return false رو هم فقط به ازای خانه های غیرمجاز (مختصات غلط و دیوارها) گذاشتم:
و بررسی خانه های مجاور رو برای بازگشت نتیجه تابع move برداشتم و اجازه دادم به ازای هر خانه خالی یا خانه ای که مسیر بهینه تری برای آن پیدا شده است، خانه های مجاور آن بررسی شود.
و در نهایت چنانچه مقدار خانه آخر همچنان '.' باقی مانده بود مقدار false و در غیر اینصورت وزن ذخیره شده در آن را برگردانم. و با انجام این تغییرات به الگوریتم زیر رسیدم و با همون اجرای اول، مسئله حل شد:
فکر کنم سریع ترین کاتایی بود که حل کردم :))
