Rikoşet Robotlar#7916
Dörd robotdan ibarət bir briqada istehsal sexinə detalları çatdıracaq. Sex düzbucaqlı bir şəbəkə şəklində təşkil olunub və hər robot bir kvadrat hüceyrəni tutur. Hər bir robot 1-dən 4-ə qədər tam ədədlə təmsil olunur və dörd ortoqonal istiqamətdə (sola, sağa, yuxarı, aşağı) hərəkət edə bilər. Lakin, hərəkətə başladıqdan sonra robot yalnız qonşu maneəni (məsələn, divarlar, fabrikin kənarları və ya digər hərəkətsiz robotlar) aşkar etdikdə dayanacaq. Robotlar eyni anda hərəkət etmir, yəni hər an yalnız bir robot hərəkət edir.
Məqsəd, robot 1-in müəyyən edilmiş hədəfə çatması üçün effektiv bir hərəkət ardıcıllığını tapmaqdır; bunun üçün digər robotları yoldan çıxarmaq və ya onları "rikoset" hərəkətləri üçün maneə kimi istifadə etmək lazım ola bilər.
Yuxarıda göstərilən nümunəni nəzərdən keçirək, burada boz hüceyrələr divarları, X hədəf yerini, 1 və 2 isə iki robotun başlanğıc mövqelərini göstərir. Altı hərəkətdən ibarət optimal həll aşağıda təsvir edilmişdir.
Qeyd edək ki, hərəkət ardıcıllığı robot 1-i müəyyən edilmiş yerdə saxlamalıdır, sadəcə onun üzərindən keçmək kifayət deyil (məqsəd robotları dayandırmır - yalnız divarlar, kənarlar və digər robotlar dayandırır).
İstehsal planının təsviri, robotun başlanğıc mövqeyi və hədəf mövqeyi verildikdə, robot 1-in hədəfə çatması üçün lazım olan minimal ümumi hərəkət sayını hesablayın.
Birinci sətir robotların sayı n (1 ≤ n ≤ 4), istehsal mərtəbəsinin eni w və hündürlüyü h (w, h ≥ 1, max(w, h) ≤ 10) və həll axtarışı üçün hərəkətlərin yuxarı həddi l (1 ≤ l ≤ 10) olan hüceyrələrdə verilir. Qalan h sətir mətn istehsal sexinin w simvolla təmsil olunan sətirləridir, hər biri hüceyrə mövqeyini təmsil edir:
W divarla dolu hüceyrə;
X (bir) hədəf hüceyrə;
1, 2, 3, 4 robotların başlanğıc mövqeləri;
’.’ boş hüceyrə.
Robot 1-in hədəf yerinə çatması üçün lazım olan minimal hərəkət sayını çıxarın, ya da NO SOLUTION əgər verilmiş yuxarı həddə bərabər və ya az olan hərəkət sayı ilə həll mövcud deyilsə.
Nümunə 1
Nümunə 2