- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک مهره‌ی اسب در خانه‌ی مرکزی یک جدول که از هر طرف نامتناهی است، قرار دارد. این مهره یک خانه را به عنوان مقصد خود انتخاب کرده است و می‌خواهد به سریع‌ترین روش ممکن به آن خانه برسد. شما باید این کمترین تعداد حرکت ممکن را پیدا کنید.
به طور دقیق‌تر، در ابتدا اسب در خانه‌ی $(0,0)$ جدول قرار دارد شما باید حداقل تعداد حرکت مورد نیاز برای رفتن اسب به خانه‌ی $(x,y)$ را پیدا کنید.
مهره‌ی اسب در هر حرکت می‌تواند در یکی از جهت‌های عمودی یا افقی دو خانه به پیش برود و در جهت دیگر یک خانه به جلو برود. این هشت خانه در شکل زیر با رنگ قرمز مشخص شده‌اند.
ورودی
در سطر اول ورودی، عدد طبیعی $t$ داده می‌شود. $$1\leq t \leq 3000$$
در سطر $i$ام از $t$ سطر بعدی، دو عدد $x_i$ و $y_i$ آمده است. $$0\leq x_i,y_i \leq 10^9$$
خروجی
پاسخ شما باید شامل $t$ خط باشد. در خط $i$ام باید حداقل حرکت مورد نیاز اسب برای رسیدن به $(x_i,y_i)$ با شروع از $(0,0)$ را چاپ کنید.
مثال‌ها
ورودی نمونه ۱
6
1 1
2 1
2 2
3 3
3 1
2000 0
خروجی نمونه ۱
2
1
4
2
2
1000
- مسیر رسیدن اسب به خانه‌ی $(1,1)$ را می‌توانید در شکل زیر با توجه به اعداد صورتی پیدا کنید.
- مسیر رسیدن اسب به خانه‌ی $(2,1)$ را می‌توانید در شکل زیر با توجه به عدد قهوه‌ای پیدا کنید.
- مسیر رسیدن اسب به خانه‌ی $(2,2)$ را می‌توانید در شکل زیر با توجه به اعداد سیاه پیدا کنید.
- مسیر رسیدن اسب به خانه‌ی $(3,3)$ را می‌توانید در شکل زیر با توجه به اعداد بنفش پیدا کنید.
- مسیر رسیدن اسب به خانه‌ی $(3,1)$ را می‌توانید در شکل زیر با توجه به اعداد صورتی آبی پیدا کنید.
ارسال پاسخ برای این سؤال