الگونَوَرد ۸ (حل شد): فاصله نزدیکترین صفر در ماتریس

اگر نمی دانید که الگونوردی چیست، از این لینک بخوانید.

دسترسی و حل سوال از منبع اصلی

پرسش: یک ماتریس از مقادیر صفر و یک داده شده است. برای هر خانه فاصله نزدیکترین صفر به آن را بیابید.

توجه توجه: برای حل مساله در سایت leetcode.com عضو شوید. برنامه شما زمانی درست است که همه تست ها را پاس کند. از دیدگاه الگونوردی، برنامه شما زمانی کامل است که سرعت آن حداقل از ۹۰ درصد راه حل ها سریع تر باشد. سایت leetcode.com سرعت نسبی برنامه شما را نشان خواهد داد.

زمان بندی: ارسال پاسخ ها تا پایان روز 25 می

نکات مهم:

• انتخاب برنده هر هفته بر اساس اولین پاسخ کامل هست که شرح حل مساله را فراهم آورد. بنابر این اگر به پاسخ کامل رسیده اید معطل نکنید و شرح حل خود را زیر پست بنویسید. تنها زبان برنامه نویسی مورد قبول پایتون می باشد.
• طبق روال برنده مسابقه هر هفته پس از انتخاب باید شرح کامل حل مساله را بنویسد. در انتها من شرح مساله نوشته شده را ویرایش و ارسال خواهم کرد.
• لطفا خودتان مسایل را حل کنید و پاسخ را ارسال نمایید. استفاده از پاسخ های دیگر و ارسال آن جهت الگونوردی با اهداف این حرکت مغایرت دارد. لطفا در این زمینه همکاری نمایید. با ارسال پاسخ زیر این پست تایید می کنید که کد متعلق به خودتان هست و آنرا شخصا حل کرده اید.
• بحث های علمی زیر این پست کاملا آزاد است. اگر در مورد نحوه مدیریت این حرکت پیشنهادی دارید به ایمیل من s.h.siadaty@gmail.com ارسال نمایید.

قوانین اهدای جایزه:

• مبلغ جایزه نقدی 50,000 تومان می باشد.
• تنها یک نفر برنده برای هر هفته اعلام خواهد شد که طبق اولین پاسخ درست و شرح خلاصه می باشد.
• جهت ایجاد مشارکت، در هر فرد تنها می تواند یکبار برنده جایزه در طول یک ماه باشد.
• جایزه نقدی تنها در صورت نوشتن شرح کامل مساله تقدیم خواهد شد.

این هفته برنده ای نداشتیم. بنابر این راه حل خودم را اینجا شرح می دهم.

حل:

روش جستجوی کامل برای این مساله به این صورت است:

برای هر خانه غیر صفر، فاصله آن تا تمام خانه های ماتریس با مقدار صفر را بدست آور و کمترین فاصله را به عنوان نتیجه برگردان. در این الگوریتم برای بدست آوردن کمترین فاصله هر خانه غیر صفر همه خانه های ماتریس را باید بررسی کنیم. بنابر این پیچیدگی محاسباتی آن N^4 می باشد.

مشکل این کار آن است که از محاسبات قبلی برای بدست آوردن نتیجه برای خانه های دیگر استفاده نمی شود.

با توجه به اینکه این مساله شباهتهایی با مساله یافتن کوتاهترین مسیر درگراف بین یک راس و تمام راس های دیگر دارد، می توانیم از روش حل دایجکسترا ایده بگیریم. در الگوریتم دایجکسترا از یک گره شروع می کنیم و هر بار مقدار گره های دیگر (که در واقع فاصله آنها تا نقطه شروع را نشان می دهند) را بروز می کنیم. در هر بار یک گره که مقدارآن نهایی نشده است و دارای کمترین مقدار هست را انتخاب می کنیم و مقدار آن را نهایی می کنیم.

در این مساله هر خانه با مقدار صفر یک نقطه شروع است. بنابر این آنها را به یک لیست که شامل خانه های مورد بررسی است قرار می دهیم. با شروع از هر خانه هر بار فاصله خانه های بعدی (بالا-پایین-راست-چپ) را از آن محاسبه و در صورت نیاز بروز می کنیم. در صورتی که مقدار خانه ای بروز شود آن را به لیست خانه های مورد بررسی اضافه می کنیم و این کار را تکرار می کنیم تا جایی که مقدار هیچ خانه ای قابل بروز رسانی نباشد. در این حالت مطمین خواهیم بود که فاصله کمینه برای همه خانه ها را محاسبه کرده ایم.

این راه حل را می توان به عنوان یک پیمایش BFS از هر خانه با مقدار صفر در تصویر نمود با این تفاوت که پیمایش با رسیدن به خانه هایی که مقدار آنها نهایی شده است متوقف می شود. بنابر این پیچیدگی محاسباتی این الگوریتم برابر با اندازه ماتریس یعنی clen*rlen می باشد.

قطعه کد زیر پیاده سازی این الگوریتم را نشان می دهد.