المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۱۲

شطرنج

یک جدول $n\times n$ داده شده است و $m$ اسب روی این جدول قرار دارند. می‌خواهیم وضعیت این اسب‌ها را به یک وضعیت ثانویه تبدیل کنیم در هر حرکت می‌‌توانیم یکی از اسب‌ها را مثل یک اسب شطرنج حرکت داده به یک خانه‌ی خالی ببریم. می‌خواهیم با کم‌ترین تعداد حرکت این کار را انجام دهیم.

ورودی

در سطر اول فایل ورودی دو عدد $n$ و $m$ آمده است سپس در $m$ سطر مختصات مکان اولیه اسب‌ها داده شده است (در هر سطر دو عدد). بعد از آن در $m$ سطر بعدی مختصات مکان ثانویه اسب‌ها داده شده است. در ضمن می‌توانید فرض کنید که $1\leq m \leq 40$ و $1\leq n \leq 1000$.

خروجی

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

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
3 1
3 1
3 3
2

ابزار صفحه