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

برنامه‌نویسی، طراحی الگوریتم و حل مسئله‌های الگوریتمی

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

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

        بررسی مسئله‌ی آتش در برره، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی آتش‌سوزی در برره
       »  مسئله
       »  ورودی برنامه
       »  حل مسئله

مسئله

  [بازگشت به فهرست]

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

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

به اشتراک‌گذاری نوشته
اشتراک‌گذاری در LinkedIn     Cloob     اشتراک‌گذاری در Twitter     اشتراک‌گذاری در Facebook     ارسال با Telegram     Google Plus
پیوندها برای مطالعه‌ی بیشتر
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

وبگاه:

متن پیام: *

01 02 03 04 05 06 07 08 09 10 11 12 13 14

 


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

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


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

   

   

پیوند کوتاه: عمر نوشته:  ۳۵۹ روز
تعداد بازدید:  ۳۴۸۷ بازدید
تعداد امتیاز:  ۳ امتیاز
میانگین امتیاز:  ۵.۰۰  از  ۵.۰۰
»  سوالات تمرینی مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018 (سری دوم)
        سری دوم سوالات تمرینی برای شرکت کنندگان مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018
»  سوالات تمرینی مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018 (سری اول)
        سری اول سوالات تمرینی برای شرکت کنندگان مسابقه‌ی برنامه‌نویسی ACM-ICPC 2018
»  مسئله‌ی Column Addition
        بررسی مسئله‌ی Column Addition، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2017 سایت تهران
»  مسئله‌ی حداکثر مجموع
        بررسی مسئله‌ی حداکثر مجموع، از سوالات آمادگی مسابقات برنامه‌نویسی
»  کتاب راهنمای برنامه‌نویسان رقابتی
        معرفی کتاب Competitive Programmer's Handbook (راهنمای برنامه‌نویسان رقابتی) برای علاقه‌مندان به مباحث الگوریتم‌ها و شرکت‌کنندگان در مسابقات برنامه‌نویسی با امکان دانلود
»  مسئله‌ی Turn the Lights Off
        متن فارسی و روش حل مسئله‌ی Turn the Lights Off از سوالات وبسایت UVa Online Judge
»  مسئله‌ی Jolly Jumpers
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد
        مستندات دوره‌ی Introduction to Programming Contests دانشگاه استنفورد با موضوع ریاضیات، ساختمان داده‌ها و الگوریتم‌های مورد نیاز برای شرکت در مسابقات برنامه‌نویسی
»  مسئله‌ی The Trip
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی 3n+1 Problem
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
»  مسئله‌ی Encrypted SMS
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
»  مسئله‌ی Gholam's Simple Game
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
»  راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
        راه حل سوالات مسابقه‌ی جهانی ACM-ICPC 2016
»  مسئله‌ی What Base Is This
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی