المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی اول:دوره ی ۸:سوال ۳۶

سوال ۳۶

در جدول روبه‌رو٬ یک نفر در ابتدا در خانه‌ی ۱ است. حرکت کردن در این جدول براساس قواعد زیر است:(منظور از یک حرکت٬ رفتن از یک خانه به خانه‌ی مجاورش است.)

  • اگر به خانه‌ای که در آن $R$ نوشته شده است وارد شود٬ باید در حرکت بعد به سمت راست بپیچد.(سمت راست و چپ نسبت به مسیر خودش محاسبه می‌شود.)
  • اگر به خانه‌ای که در آن $L$ نوشته شده است وارد شود٬ باید در حرکت بعد به سمت چپ بپیچد.
  • اگر به خانه‌ای که در آن $S$ نوشته شده است وارد شود٬ باید در حرکت بعد مستقیم به حرکت خود ادامه دهد.
  • اگر به خانه‌ای خالی وارد شود٬ در حرکت بعد می‌تواند به هر یک از چار خانه‌ی مجاورش برود.

توجه کنید که این فرد هیچ‌گاه نباید از جدول خارج شود. حداقل تعداد حرکات لازم برای رسیدن به خانه‌ي ۲ چندتاست؟

  1. ۷
  2. ۹
  3. ۱۱
  4. ۱۳
  5. ممکن نیست

پاسخ

گزینه (؟) درست است.

در جدول مقابل برای رسیدن به خانه‌ی $b$ اگر خانه‌ی ۱۳ وارد شویم لازم است به خانه‌ی ۱۳ از خانه‌ی ۱۴ وارد شویم. برای وارد شدن به خانه‌ی ۱۳ از ۱۴ به‌طوری که به راست بپیچیم باید از خانه‌ی ۱۹ وارد شویم. برای این که با گردش به چپ از ۱۹ به ۱۴ وارد شویم باید از خانه‌ی ۱۸ به خانه‌ی ۱۹ وارد شویم و اگر به همین ترتیب ادامه دهیم دنباله‌ی حرکت به شکل زیر خواهد بود که ۱۳ حرکت می‌باشد:

$$1\rightarrow2\rightarrow76\rightarrow5\rightarrow12\rightarrow11\rightarrow14\rightarrow15\rightarrow18\rightarrow19\rightarrow14\rightarrow13\rightarrow20$$

اگر برای ورود به خانه‌ی $b$ از خانه‌ی ۱۹ وارد شویم آن‌گاه دنباله‌ی حرکت به شکل زیر خواهد بود که ۱۱ حرکت می‌باشد:

$$1\rightarrow2\rightarrow7\rightarrow6\rightarrow5\rightarrow6\rightarrow7\rightarrow10\rightarrow15\rightarrow14\rightarrow19\rightarrow20$$


ابزار صفحه