مسابقه‌ی تصادفی

 
 
 مسیر اسب! (مسابقه‌ي شماره‌ي 10) ويژه‌ي ايام نوروز
مسیر اسب! (مسابقه‌ي شماره‌ي 10) ويژه‌ي ايام نوروزمسابقه كامپيوتر
اگه گفتین چه خوری می‌شه این اسب مهربون رو با توجه به شرایط این مسأله به خونه‌ی مورد نظر برد!

مسير اسب


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

یک اسب در یکی از خانه‌های سفید این صفحه قرار گرفته است. می‌خواهیم در صورت امکان، مسیری بیابیم که اسب با طی آن مسیر به نقطه‌ای مشخص برسد و در حین حرکت نیز از هیچ نقطه‌ی سیاهی عبور نکند.

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

فرض كنيد n تعداد سطر و ستون های صفحه شطرنجی بوده از 30 بزرگ‌تر نیست.

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


مثلاً:

ورودي

خروجي

6

9

(تعداد نقاطی که اسب
طی مسیرش می‌پیماید)

(تعداد سطر و ستون های
صفحه‌ي شطرنجی است)

100100

62

010000

54

001001

35

001010

16

001001

24

000010

32

62

13

26

24

26


مختصات‌ها به‌شکل (y,x) هستند که در آن‌ها y<=n و x>=1 است (x شماره سطر و y شماره ستون است).


 

 

1386/1/6لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 المپیاد کامپیوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  4187
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  4187