SCANF.IR

current date=2024-04-24 11:56:30  start-date=0

پازل هشت

در این مساله از شما خواسته می‌شود تا الگوریتمی برای حل پازل-۸ بنویسید. ورودی این مساله یک حالت از پازل ۸ می‌باشد و الگوریتم بایستی حرکات مورد نیاز برای حل مساله به ترکیب مورد نظر از اعداد را در خروجی چاپ کند. در هر مرحله چهار حرکت ممکن وجود دارد که عبارتند از بالا، پایین، چپ و راست (UP, DOWN, LEFT, RIGHT) که منجر به حرکت فضای خالی جدول و جابجایی آن با یکی از خانه‌ها با توجه به حرکت مورد نظر می‌شود. به عنوان مثال فرض کنید حالتی از پازل به صورت زیر باشد:

3	2	1
4		7
6	5	8

در این حالت همه چهار حرکت قابل انجام است مثلا با انجام حرکت (UP) جدول به صورت زیر در خواهد آمد.

3		1
4	2	7
6	5	8

الگوریتم بایستی حرکات مورد نیاز برای رسیدن به جدول هدف که به صورت زیر است را محاسبه و در خروجی نمایش دهد و در صورتی که پاسخی برای مساله وجود نداشت پیام ERROR را نماش دهد.

3	2	1
6	5	4
	8	7

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

ورودی نمونه

1 2 3 
4 5 6 
7 0 8

خروجی نمونه

RIGHT

ورودی نمونه

4 1 3 
7 2 0 
8 6 5

خروجی نمونه

DOWN
LEFT
LEFT
UP
UP
RIGHT
DOWN
RIGHT
DOWN