مین‌یابی به ‌روش ساده

فرض کنید ما صفحه‌ای داشته باشیم با مفروضات زیر:

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 ضمیمه شده ‌است. برای دسترسی به آن به لینک زیر بروید:‌

امیربهاالدین سبط‌الشیخ