Sokoban#3111
Soko-ban, yapon dilində anbarda işləyən işçi mənasını verir və 1980-ci illərdə yaradılmış klassik bir kompüter oyununun adıdır. Bu, bir nəfərlik oyundur və bu qaydada oynanılır: bir işçi qapalı anbarda bir və ya bir neçə qutu ilə birlikdədir. Məqsəd həmin qutuları hədəf yerlərinə çəkməkdir; hədəflərin sayı qutuların sayı ilə eyni olmalıdır. Oyunçu işçinin hərəkət istiqamətini ox düymələri ilə (yuxarı, aşağı, sola, sağa) göstərir, aşağıdakı qaydalara əsasən:
Əgər işçi üçün göstərilən hərəkət istiqaməti boş bir yerə (yəni, orada nə qutu, nə də divar olmayan yerə) aparırsa, işçi həmin istiqamətdə bir addım irəli gedir.
Əgər göstərilən hərəkət istiqaməti işçinin bir qutunun üstünə çıxmasına səbəb olursa və qutunun o biri tərəfindən yer boşdursa, həm işçi, həm də qutu bir addım həmin istiqamətdə irəliləyir (yəni işçi qutunu itələyir).
Əgər göstərilən hərəkət istiqaməti işçinin divara doğru hərəkət etməsinə və ya işçinin bir qutunun üzərinə çıxmasına, amma o qutunun o biri tərəfində başqa qutu və ya divar olmasına səbəb olursa, həmin düymə basıldıqda heç bir hərəkət baş vermir.
Məqsəd bütün qutuların eyni anda hədəf yerlərində yerləşməsidir. Belə olduqda, oyunçu uğurlu sayılır (və formal olaraq, növbəti düymə basılması artıq nəzərə alınmır).
Bu oyun informatika alimləri tərəfindən araşdırılıb (bir aspirant Soko-ban analizinə həsr olunmuş bir elmi iş belə yazıb). Təəssüf ki, bu oyunun həllini tapmaq çox çətindir, çünki bu problem həm NP-çətin, həm də PSPACE-complete-dir. Buna görə, sizin tapşırığınız daha asandır: oyunçunun klaviaturada yazılmış ardıcıllığına əsaslanaraq oyunun gedişini simulyasiya edəcəksiniz. Giriş və çıxış formatı üçün oyunun vəziyyətini aşağıdakı simvollarla təsvir edirik:
Məsələn, bu məsələnin əvvəlində olan ilkin vəziyyət aşağıdakı kimi birinci giriş nümunəsində verilib.
Hər oyun iki tam ədədlə — və — başlayır, burada 4 \le R \le 15 sətirlərin, 4 \le C \le 15 sütunların sayıdır. Sonra, yuxarıdan aşağıya sıralanmış sətir verilir, hər sətirdə soldan sağa simvol var. Nəhayət, oyunçunun düymə basmalarını təsvir edən ən çoxu simvoldan ibarət bir sətir verilir və burada hərəkətlər , , , simvolları ilə yuxarı, aşağı, sola, sağa işarə olunur. Oyunçunun tam ardıcıllığını oxumalısınız, hətta oyun sətirlər bitməzdən əvvəl başa çatmış olsa belə. Məlumatların sonu sətiri ilə verilir.
Zəmanət verilir ki, hər oyunda dəqiq bir işçi, bərabər sayda qutu və hədəf yeri, ən azı bir yanlış qoyulmuş qutu və ən xarici sərhəd tamamilə divarlardan ibarət olacaq.
Hər oyun üçün əvvəlcə oyun nömrəsini (-dən başlayaraq), sonra isə complete və ya incomplete sözünü çıxışa verin; bu, oyunçunun oyunu uğurla bitirib-bitirmədiyini göstərir. Sonra isə oyunun son vəziyyətini olduğu kimi çap edin.
Nümunə 1