المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۱۳:j

Bacteria

برای ساده کردن مطالعه روی باکتری ها، اغلب پیکربندی آنها را با مدل کردن تصویر میکروسکوپی آنها به صورت یک جدول دوبعدی ساده میکنند.همانطور که میتوانید در شکل یک ساده سازی جدولی تصویری از یک باکتری معروف را، که به نام $DilBactrium$ شناخته میشود، ببینید، برخی از خانه های جدول به عنوان بدن باکتری اشغال شده اند، در حالی که دیگر خانه ها خالی هستند.

تعدادی از خانه‌های خالی جدول از قبل با دیگر ماده‌های مرده اشغال شده‌اند و بنابراین نمی‌توانند توسط باکتری اشغال شوند. فرض می‌کنیم $G$ مجموعه کل خانه‌های جدول باشد که توسط ماده‌های مرده اشغال نشده‌اند.

دو خانه از جدول همسایه نامیده می‌شوند اگر یک ضلع مشترک داشته باشند و ترتیب $L$ از خانه‌های جدول یک مسیر نامیده می‌شود اگر خانه‌های آن به صورت متوالی همسایه یک‌دیگر باشند. همچنین مجموعه‌ای از خانه‌های جدول مانند $S$ همبند نامیده می‌شود که به ازای هر دو خانه موجود در آن مانند $c_1$ و $c_2$، مسیری شامل این دو خانه وجود داشته باشد که تنها شامل اعضای $S$ باشد (به عبارت دیگر بین هر دو عضو آن مسیری وجود داشته باشد که تنها از اعضای $S$ گذر می‌کند). با در نظر گرفتن این تعاریف یک ساده‌سازی جدولی باکتری (که با $GSB$ آن را نمایش می‌دهیم) درواقع یک زیر مجموعه با سایز ثابت و همبند از $G$ است.

از آنجا که یک باکتری زنده حرکت می‌کند، حرکت آن‌ها نیز باید در این ساده‌سازی، پیش بینی و مدل‌سازی شود. یک حرکت باکتری که آن را با زیرمجموعه همبند $S$ مدل می‌کنیم، در این ساده سازی به این صورت تعریف میشود که یکی از خانه های عضو $S$ مانند $c_1$ از آن حذف و یکی از خانه های $G$ که تا کنون در $S$ نبوده است به آن اضافه میشود طوریکه زیر مجموعه $(S – {c_1}) \cup {c_2}$ کماکان همبند باشد. این زیر مجموعه معرف پیکربندی جدید باکتری بعد از این حرکت است (منظور از پیکربندی در واقع در نظر گرفتن توامان مکان و ظاهر باکتری است).

یک $GSB$ می‌تواند بعد از انجام تعدادی حرکت به وضعیتی کاملا متفاوت با وضعیت اولیه برسد و به وضوح برای یک $GSB$ راه های مختلف زیادی برای رسیدن به وضعیت نهایی گفته شده وجود دارد. با داشتن پیکربندی اولیه و نهایی یک $GSB$، وظیفه شما یافتن کم‌ترین تعداد حرکت مورد نیاز برای رسیدن $GSB$ از پیکربندی اولیه به پیکربندی نهایی است. می‌توانید فرض کنید که پیکربندی‌های اولیه و نهایی هیچ خانه‌ی مشترکی ندارند.

ورودی

خروجی

محدودیت‌ها

  • محدودیت زمان: ۱۰ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
2 3

x#o
2 3
x.o
x#o
2 3
#..
x#o
9 9
.xxx…..
.xxx…#.
########.
…….#.
.#####.#.
.#.oo#.#.
.#oooo.#.
.#######.
………
0 0
4
3
No solution
41

ابزار صفحه