المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۷:تئوری نهایی اول:سوال ۳

ایلیچ و مملی

یک جدول $m \times n$ داریم که برخی از خانه‌های آن سفید و بقیه‌ی آن‌ها سیاه هستند. می‌دانیم به ازای هر دو خانه‌ی سفید، می‌توان از یکی شروع کرده، در هر مرحله به یک خانه‌ی مجاور (دارای ضلع مشترک) رفته و پس از تعدادی مرحله به دیگری رسید. ایلیچ و مملی، هر کدام روی یک خانه‌ی سفید از جدول قرار گرفته‌اند. این دو حق ندارند روی خانه‌های سیاه رفته یا از جدول خارج شوند. هر یک از این دو با دریافت یکی از دستورهای چپ، راست، بالا یا پایین، در صورتی که بتوانند، طبق آن دستور یک واحد جابه‌جا می‌شوند، در غیر این صورت سر جای خود می‌مانند.

سلطان می‌خواهد ایلیچ و مملی را به هم برساند. او در هر مرحله می‌تواند یک دستور صادر کرده و هر دو نفر (ایلیچ و مملی) طبق آن عمل کنند. ثابت کنید سلطان می‌تواند با دنباله‌ای از دستورها به هدف‌ش برسد.


ابزار صفحه