همه ما با بازي Minesweeper آشنا هستيم و حداقل يک‌بار
آن‌را در کامپيوتر خود بازي کرده‌ايم. اين هفته مي‌خواهيم ببينيم که اين
بازي چگونه حل مي‌شود و وقتي ما روي صفحه کليک مي‌کنيم اعداد ظاهر شده
چگونه به‌وجود مي‌آيند؟ براي پيدا کردن جواب مساله آن‌را به‌صورت معکوس حل
مي‌کنيم.
فرض کنيد ما صفحه‌اي
داشته باشيم با مفروضات زير:
000*0
0**00
0*00*
00000
کليدهاي
*
نشان‌دهنده بمب و کليدهاي
0
خانه
خالي هستند و ما بايد آنها را با توجه به مکان بمب‌ها پر کنيم. در واقع
اعداد در اين خانه‌ها شما را براي رسيدن به بمب‌ها راهنمايي مي‌کنند.
کاري که ما بايد بکنيم
اين است که جاي
0
ها عدد مناسب قرار دهيم.
عدد مناسب چيست؟
فرض کنيد سه خانه کنار
هم به شکل زير باشد،
*0*
،
بايد جاي
0
چه عددي قرار بگيرد؟ جواب
2
است، چون قرار است با عدد دو متوجه شويم که دو بمب در کنار
اين خانه است که با توجه به صورت سوال همين‌طور است. پس ما بايد روشي ارائه
دهيم که اعدادي که در اطراف بمب‌ها هستند، ما را براي رسيدن به بمب‌ها
راهنمايي کنند و اعداد درستي به‌دست بيايد.
خب، راه اول را بررسي
مي‌کنيم. بهتر است شکل را به‌صورت يک ماتريس يا آرايه دوبعدي در نظر بگيريم
و سپس در هر سطر خانه‌ها را تک‌تک بررسي کنيم. اگر بمب بودند خانه‌هاي
پشتي و بعدي آنها و اگر بمب نبود، يکي اضافه شود. مثلا براي
0**0
مي‌شود
1**1
بسيار خب، ما با همين
روش سوال را حل کرديم؟ اما مشکل ديگري وجود دارد آن هم اين‌که اگر خانه‌ها
به‌صورت عمودي بودند چه؟ يعني اين‌گونه:
0
*
*
0
پس
بايد يک‌بار هم آرايه را براي ستون‌هاي آن بررسي کنيم. يعني فرض کنيم
ماتريس ما 90 درجه چرخيده و ما دوباره بايد همان روش قبلي را پي بگيريم، خب
حالا به جواب رسيديم. آيا اين روش، روش درستي است؟
پاسخ خير است، چون شما
در هر بار خواندن ماتريس بايد دو حلقه تودرتو داشته باشيد. اگر صفحه بازي
شما 4*3 باشد شما بايد دو حلقه که هر کدام به ميزان 4*3 اجرا مي‌شوند را
اجرا کنيد. و اين از لحاظ زماني خيلي مقرون‌به‌‌صرفه نيست چون بايد دو حلقه
تودرتو به‌صورت 4*3 يكي براي خواندن و يکي هم براي نوشتن در خروجي استفاده
کنيم، يعني کلا ?حلقه.
قصد داريم روشي پيشنهاد
کنيم که اين امر به‌سادگي و با کمترين هزينه اجرا شود. در اين روش ما يک
حلقه را حذف کرده و به‌جاي آن صفحه ورودي را 2 سطر و 2 ستون اضافه مي‌کنيم.
مثلا فرض کنيد که ورودي
ما يک صفحه 4*3 باشد، ما در برنامه، يک صفحه ورودي 6*5 تعريف مي‌کنيم. روش
حل تقريبا شبيه به روش قبلي است. البته با يک سري تفاوت، ما ورودي‌ها را در
آرايه دوبعدي ذخيره مي‌کنيم. البته بايد دقت داشته باشيم که دو سطر و دو
ستوني که اضافه شدند خالي باشند و حلقه‌هاي ما به اندازه همان 4*3 باشند.
بسيار خب، مانند روش
قبلي آرايه يا همان ماتريس خود را سطر به سطر بررسي مي‌کنيم و اگر خانه‌اي
برابر بمب بود، تمام خانه‌هاي اطراف آن‌را يکي اضافه مي‌کنيم.
بعد از اتمام حلقه،
ماتريس را در خروجي چاپ مي‌کنيم.
خب، سوالي که ممکن است
پيش بيايد اين است که چرا در روش قبلي اين کار را نکرديم؟ جواب
ساده‌‌است، فرض کنيد ما خانه‌هاي مرزي مثل
0,0
را مي‌خواهيم بررسي بکنيم، فقط سه‌تا خانه را مي‌توانيم
بررسي کنيم و براي سه خانه بعدي که وجود خارجي ندارند بايد يک شرط کنترلي
بگذاريم و به‌طبع اين شرط کنترلي بايد با هر بار اجرا شدن حلقه اجرا شود.
اين منطقي به‌نظر نمي‌رسد چون هر شرط، يک مرتبه زماني به‌حساب مي‌آيد.
اما در روش دوم که ارائه
شد هيچ شرطي بررسي نشد فقط ما يک مقدار حافظه مصرفي را بيشتر در نظر
گرفتيم.
پس از محاسبات به اين
نتيجه مي‌رسيم که روش دوم بسيار ساده‌تر و سريع‌تر از روش قبلي اجرا
مي‌شود.
کد اين روش به زبان #C
ضميمه شده است. براي دسترسي به آن به لينک زير برويد:
http://bit.ly/96xwJQ
اميربهاالدين
سبط‌الشيخ
