الگوریتمستان

نوشته‌های یک علاقه‌مند به حوزه‌های برنامه‌نویسی، الگوریتم، حل مسئله و ریاضیات دوست داشتنی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
مسئله‌ی آتش‌سوزی در برره - الگوریتمستان
الگوریتمستان
آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی آتش‌سوزی در برره
       »  مسئله
       »  ورودی برنامه
       »  حل مسئله

مسئله

  [برگرد بالا]

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

روستا را به صورت شبکه‌ای با ابعاد $ 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

  

منبع: مسابقه‌ی برنامه‌نویسی ACM-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 ساده از محل استقرار خرزو خان حرکت کرده و تنها خانه‌هایی را به صف اضافه می‌کنیم که زمان ورود به آنها قبل از زمان آتش گرفتنشان باشد. اگر با چنین پیمایشی به محل هلیکوپتر رسیدیم، طول این مسیر میزان زمان لازم برای رسیدن به هلیکوپتر است که به عنوان نتیچه چاپ می‌شود.

◄  پیوندها برای مطالعه‌ی بیشتر
مسعود اقدسی‌فام

مسعود اقدسی‌فام هستم.

یک معلم علاقه‌مند به تحقیق، تدریس و نوشتن در حوزه‌های برنامه‌نویسی، الگوریتم و حل مسئله :)

اشتراک‌گذاری نوشته
algs.ir/sp21t84     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram     ارسال با WhatsApp
امتیاز به نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک:

وب‌سایت:

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14


• پیمان رشیدی
یکشنبه، ۲۹ مهر ماه ۱۳۹۷، ساعت ۰۶:۲۴

آقا خیلی سخت بود 14


کمی آمار
  • عمر نوشته:  ۱۴۴۷ روز
  • تعداد امتیاز ثبت شده:  ۵ امتیاز
  • میانگین امتیازها:  ۴.۰۰ از ۵.۰۰
  • بازدید امروز:  ۳ بازدید
  • بازدید ۲۴ ساعت گذشته:  ۱۱ بازدید
  • بازدید ۷ روز گذشته:  ۶۰ بازدید
  • بازدید ۳۰ روز گذشته:  ۲۴۹ بازدید
  • بازدید ۱ سال گذشته: ۲۷۹۷ بازدید
  • کل بازدیدها: ۶۲۵۸ بازدید
برچسب‌ها
#آمادگی مسابقه برنامه‌نویسی  #آموزش الگوریتم  #مسئله‌های الگوریتمی  #برنامه‌نویسی ++C  #الگوریتم  #نمونه سوالات مسابقه برنامه‌نویسی  #حل مسئله‌‌ی الگوریتمی  #برنامه‌نویسی  #منبع آموزشی  #حل سوالات مسابقات برنامه‌نویسی  #الگوریتم‌های تقسیم و غلبه  #نمونه سوال مسابقه ACM  #الگوریتم‌های برنامه‌نویسی پویا  #الگوریتم‌های بازگشتی  #کتاب الکترونیکی  #آموزش ساختمان داده‌ها  #تکنیک‌های طراحی الگوریتم  #محاسبات ریاضی  #گراف  #دانلود کتاب  #حل سوالات ACM-ICPC  #الگوریتم‌های مرتب‌سازی  #سوالات مسابقات ACM-ICPC  #Python  #پیمایش گراف  #ساختمان داده  #کتاب مسابقات برنامه‌نویسی  #الگوریتم‌های گراف  #حل سوالات UVa Online Judge  #الگوریتم‌های مسیریابی  #الگوریتم‌های حریصانه  #درخت‌ها  #سوالات UVa Online Judge  #جستجوی اول سطح  #ماتریس  #الگوریتم‌های کوتاهترین مسیر  #درخت پوشا  #الگوریتم دایکسترا  #ویدئوی آموزشی  #معرفی وب‌سایت  #الگوریتم فلوید-وارشال  #مسئله‌ی کوله‌پشتی  #جستجوی اول عمق  #کتابخانه قالب استاندارد ++C  #صف  #سوالات مسابقات برنامه‌نویسی بیان  #الگوریتم‌های عقبگرد  #حل سوالات Timus Online Judge