المپدیا

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

ابزار کاربر

ابزار سایت


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

ملخ

یک جدول $n\times n$ داریم که خانه‌ی ردیف $i$ام و ستون $j$ ام آن را با $(i,j)$ نشان می‌دهیم. یک ملخ داریم که از خانه‌ی $(a,b)$ شروع می‌کند و می‌خواهد به خانه‌ی $(c,d)$ برسد. اما عبور از برخی از خانه‌های جدول غیر مجاز می‌باشد. حرکت ملخ بدین صورت است که در هر حرکت، می‌تواند به اولین خانه‌ی مجاز چپ٬ راست، بالا و پایین خود (در صورت وجود) بپرد. هدف این است که ملخ با کم‌ترین تعداد چرخش(تغییر جهت) به هدف برسد. فرض کنید که خانه‌های مبدا و مقصد مجاز هستند.

ورودی

در سطر اول فایل ورودی اعداد $c،b،a،n$ و $d$ به ترتیب آمده‌اند. سپس در $n$ سطر بعد، در هر سطر $n$ عدد آمده است که عدد $j$ام سطر $i$ام این $n$ سطر، اگر $(i,j)$ مجاز باشد ۱ است و در غیر این صورت ۰ می‌باشد.$(n \leq 1000)$

خروجی

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

در صورتی که مسئله جواب نداشته باشد٬ در یک سطر بنویسید $No Solution$.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
4 1 1 3 4
1 1 1 0
0 1 0 1
0 1 0 1
1 1 1 0
5
1 1
1 2
2 2
3 2
3 4

ابزار صفحه