المپدیا

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

ابزار کاربر

ابزار سایت


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

شرکا

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

به این دو کمک کنید تا در کم‌ترین زمان، سالم و سرحال به محل نهایی برسند.

ورودی

در سطر اول فایل ورودی $m$ و $n$ آمده و در هر یک از چهار سطر بعدی 2 عدد آمده که به ترتیب مختصات خانه‌ی فعلی شریک اول، خانه‌ی فعلی شریک دوم، خانه‌ی نهایی شریک اول و خانه‌ی نهایی شریک دوم می‌باشند. در هر یک از $m$ سطر بعدی نیز $n$ عدد می‌آید که صفر نشان‌دهنده‌ی خالی بودن آن سلول و یک نشان‌دهنده‌ی وجود یک خانه در آن سلول است.($1 \leq m,n \leq 200$)

خروجی

اگر چنین کاری امکان‌پذیر نیست در تنها سطر آن بنویسید IMPOSSIBLE و الا:

در سطر اول کم‌ترین روزهای لازم برای حرکت و در هر یک از سطرهای بعدی یک حرکت را شرح دهید:

ابتدا شماره‌ی شریکی که حرکت می‌کند را بنویسید و سپس جهت حرکتش را مشخص کنید: $U$ برای بالا، $D$ برای پایین، $L$ برای چپ و $R$ برای راست. در ضمن خانه‌ی $(1,1)$ خانه‌ی بالا و سمت چپ و خانه‌ی $(1,n)$ نیز بلا و سمت راست است.

محدودیت‌ها

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

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

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

ابزار صفحه