مسئله آتش‌سوزی در برره

برخی از نقاط روستای برره در حمله دشمن فرضی آتش گرفته‌اند! این آتش رفته رفته گسترش پیدا کرده و به نقاط دیگر نیز سرایت می‌کند. خرزو خان که تنها بازمانده روستا در نبرد با دشمن فرضی است، تلاش می‌کند خود را برای نجات به تنها هلیکوپتر روستا برساند.

روستا را به صورت شبکه‌ای با ابعاد $ n \times m $ در نظر بگیرد که برخی خانه‌های آن در آغاز آتش گرفته‌اند و اگر خانه‌ای در زمان $x$ آتش گرفته باشد، هشت خانه مجاور آن در زمان $ x + k$ آتش خواهند گرفت و هرگز خاموش نمی‌شوند. حال اگر خرزو خان در نقطه $s$ شبکه باشد، می‌تواند در هر ثانیه به یکی از چهار خانه مجاور بالا، پایین، راست یا چپ خود برود و تلاش کند به نقطه $t$ که هلیکوپتر در آن قرار دارد برسد.

برنامه‌ای بنویسید که کوتاهترین مسیر ممکن برای حرکت امن و بدون درگیری با آتش خرزو خان از نقطه $s$ به نقطه $t$ را مشخص کند.

  

ورودی برنامه

  [برگرد بالا]

هر دسته ورودی برنامه با سه عدد مثبت $n$، $m$ و $k$ (نابیشتر از $100$) آغاز می‌شود که $n$ و $m$ ابعاد شبکه و $k$ نرخ رشد آتش‌سوزی را مشخص می‌کنند. در ادامه $n$ سطر هر کدام به طول $m$ آمده است که هر سطر وضعیت خانه‌های یک سطر از شبکه را مشخص می‌کند. در این نمایش خانه‌هایی از شبکه که در ابتدا آتش گرفته‌اند با کاراکتر 'f'، محل خرزو خان با کاراکتر 's'، محل هلیکوپتر با کاراکتر 't' و سایر خانه‌ها با کاراکتر '-' مشخص شده‌اند. شبکه ورودی ممکن است بدون کاراکتر 'f' باشد.

برنامه زمانی خاتمه پیدا می‌کند مقدار صفر برای $n$، $m$ و $k$ به عنوان ورودی ارسال شوند.

  

2 7 2

f------

-f---f-

----f--

-------

------f

---s---

t----f-

3 4 1

t--f

--s-

----

2 2 1

st

f-

2 2 2

st

f-

0 0 0

  

خروجی برنامه

به ازای هر دسته ورودی یک سطر در خروجی چاپ می‌شود که نمایشگر حداقل زمان ممکن برای رسیدن خرزو خان به هلیکوپتر است. اگر این امر ممکن نباشد، عبارت Impossible چاپ شود.

  

4

Impossible

Impossible

1

  

منبع: مسابقه برنامه‌نویسی ICPC منطقه‌ای سایت تهران 2017 - مسئله Barareh on Fire

  

حل مسئله

  [برگرد بالا]

برای آنکه بدانیم بهترین مسیر خرزو خان برای حرکت به سمت هلیکوپتر کدام است، ابتدا باید بدانیم هر محل چه زمانی آتش می‌گیرد و در ادامه بررسی کنیم آیا امکان گذر از آن محل قبل از آتش‌سوزی وجود دارد یا نه؟

در مورد بخش اول، بدیهی است حریق به هر خانه از نزدیکترین محل شروع آتش‌سوزی می‌رسد. برای ورودی اول مثال‌های بالا، ماتریس زمان آتش‌سوزی هر خانه به این ترتیب خواهد شد:

  

0 2 2 4 2 2 2

2 0 2 2 2 0 2

2 2 2 2 0 2 2

4 4 4 2 2 2 2

6 6 4 4 4 2 0

8 6 6 4 2 2 2

8 8 6 4 2 0 2

  

برای تشخیص این فاصله دو راهکار ساده وجود دارد. اول آنکه هر خانه از شبکه را مبدا گرفته و با استفاده از الگوریتم‌های مسیریابی، نزدیکترین محل شروع حریق را برای آن تشخیص دهیم. حالت دوم آن است که هر کدام از محل‌های شروع آتش‌سوزی را مبدا قرار داده و زمان گسترش آن به سایر خانه‌ها را محاسبه کرده و در نهایت برای هر خانه کمترین مقدار از بین این زمان‌ها را محاسبه کنیم. راهکار اول زمانی که محل شروع آتش کمی داشته باشیم چندان کارا نیست و ممکن است به ازای هر کدام از خانه‌ها نیاز باشد تمام شبکه را برای یافتن نزدیکترین 'f' جستجو کنیم. راهکار دوم نیز زمانی که محل شروع آتش بسیار زیاد باشد کارایی مناسبی ندارد. چرا که به ازای هر کدام از این محل‌ها باید زمان رسیدن آتش آن به تمام خانه‌های دیگر شبکه محاسبه شود.

در هر دو روش فوق الگوریتم جستجوی اول عمق (BFS) ابزار مناسبی برای یافتن نزدیکترین هدف است (چرا؟). اما می‌توانیم از این ابزار به صورت بهتر از راهکارهای قبلی نیز استفاده کنیم. به این ترتیب که به ازای هر خانه شروع آتش، یک صف برای آغاز الگوریتم BFS می‌سازیم و هر گام تکرار این الگوریتم را برای همه این صف‌ها به صورت همزمان انجام می‌دهیم. به این ترتیب بعد از اولین گام، همسایه‌های مجاور هر کدام از محل‌های شروع آتش‌سوزی مشخص می‌شوند و مطمئن هستیم که برای این نقاط نزدیکترین محل آتش مشخص شده است. در گام دوم برای همسایه این همسایه‌ها نزدیکترین آتش مشخص می‌شود و همینطور تا آخر پیش می‌رود. مزیت این روش آن است که وقتی پیمایش دو یا چند صف مختلف به یک نقطه می‌رسند، درچ نقاط همسایه در صف متوقف می‌شود. چرا که این همسایه‌ها قبلا توسط صف دیگری پردازش شده‌اند و نزدیکترین محل آتش‌سوزی به آنها مشخص شده است. به این ترتیب هر خانه از شبکه تنها یک بار توسط یکی از صف‌ها پردازش می‌شود و در زمان اجرا صرفه‌جویی قابل ملاحظه‌ای صورت می‌گیرد.

در مورد بخش دوم حل مسئله، پس از مشخص شدن زمان آتش سوزی هر خانه، با یک الگوریتم BFS ساده از محل استقرار خرزو خان حرکت کرده و تنها خانه‌هایی را به صف اضافه می‌کنیم که زمان ورود به آنها قبل از زمان آتش گرفتنشان باشد. اگر با چنین پیمایشی به محل هلیکوپتر رسیدیم، طول این مسیر میزان زمان لازم برای رسیدن به هلیکوپتر است که به عنوان نتیچه چاپ می‌شود.