المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۳۱:سوال ۴

سوال ۴

ﺩﺭشکل ﺯﯾﺮ میﺧﻮﺍﻫﯿﻢ ﺍﺯ ﺧﺎﻧﻪﯼ A ﺑﻪ ﺧﺎﻧﻪﯼ B ﺑﺮﻭﯾﻢ. ﺩﺭ ﻫﺮ ﻣﺮﺣﻠﻪ میﺗﻮﺍﻧﯿﻢ ﺑﻪ یک ﺧﺎﻧﻪﯼ ﻣﺠﺎﻭﺭ (ﺩﺍﺭﺍﯼ ﺿﻠﻊ ﻣﺸﺘﺮﮎ ﺑﺎ ﺧﺎﻧﻪﯼ ﮐﻨﻮنی) ﺑﺮﻭﯾﻢ.ﺑﺮﺍﯼ ﻋﺒﻮﺭ ﺍﺯ ﻫﺮ ﺧﺎﻧﻪ، ﺑﺎﯾﺪ ﺑﻪ ﻣﻘﺪﺍﺭ ﻋﺪﺩ ﺩﺭﻭﻥ ﺁﻥ ﺧﺎﻧﻪ ﻫﺰﯾﻨﻪ ﺑﺪﻫﯿﻢ. ﮐﻤﯿﻨﻪﯼ ﻫﺰﯾﻨﻪﯼ ﻻﺯﻡ ﺑﺮﺍﯼ ﺭﺳﯿﺪﻥ ﺍﺯ A ﺑﻪ B ﭼﯿﺴﺖ؟

  1. ۳۸
  2. ۳۲
  3. ۲۴
  4. ۳۶
  5. ۱۶

راهنمایی

سعی کنید به شکل منظمی مسیر‌ها را بررسی کنید تا از پیچیدگی بپرهیزید.

راهنمایی

از الگوریتم‌های یافتن کوتاه‌ترین مسیر در گراف‌ها استفاده کنید.


ابزار صفحه