Halloween-dan Sonrakı Səhər#5832
Siz bir əyləncə parkında obakeyashiki, yəni qonaqların dar və qaranlıq dəhlizlərdən keçdiyi bir qorxulu evin operatoru kimi çalışırsınız. Ev, əslində operator tərəfindən uzaqdan idarə olunan robotlar olan canlı ruhları ilə fəxr edir, dəhlizlərdə burada və orada gizlənirlər. Bir səhər, ruhların olması lazım olan mövqelərdə olmadığını gördünüz. Ah, dünən Halloween idi. İnanın ya inanmayın, paranormal ruhlar gecə onları dəhlizlərdə hərəkət etdirdilər. Qonaqlar gəlməzdən əvvəl onları düzgün mövqelərinə qaytarmalısınız. Meneceriniz ruhların bərpasının nə qədər vaxt apardığını bilmək istəyir.
Bu məsələdə, sizdən evin döşəmə xəritəsi verildikdə, bütün ruhları olması lazım olan mövqelərə köçürmək üçün ən az addım sayını tapacaq bir proqram yazmağınız tələb olunur.
Döşəmə kvadrat hüceyrələrdən ibarət bir matrisdən ibarətdir. Bir hüceyrə, ruhların içəriyə hərəkət edə bilmədiyi bir divar hüceyrəsi və ya hərəkət edə bildikləri bir dəhliz hüceyrəsi ola bilər.
Hər addımda, eyni anda istənilən sayda ruhu hərəkət etdirə bilərsiniz. Hər bir ruh ya cari hüceyrədə qala bilər, ya da 4 qonşuluğundakı (yəni dərhal sol, sağ, yuxarı və ya aşağı) dəhliz hüceyrələrindən birinə hərəkət edə bilər, əgər ruhlar aşağıdakı şərtlərə cavab verirsə:
Hər addımın sonunda bir mövqedə bir ruhdan çoxu yerləşmir.
Heç bir ruh cütü bir-birinin mövqeyini dəyişmir.
Məsələn, ruhların aşağıdakı (qismən) xəritədə göstərildiyi kimi yerləşdiyini fərz edək, burada bir kəskin işarə ('#') divar hüceyrəsini və 'a', 'b' və 'c' ruhlarını təmsil edir.
Aşağıdakı dörd xəritə, bir addımdan sonra ruhların mümkün olan yeganə mövqelərini göstərir.
Giriş, hər biri bir evin döşəmə xəritəsini təmsil edən ən çox 10 datasetdən ibarətdir. Bir datasetin formatı aşağıdakı kimidir.
w h n
c_11 c_12 ... c_1w
c_21 c_22 ... c_2w
... ... ... ...
c_{h1 }c_h2 ... c_hw
Birinci sətirdəki w, h və n boşluqla ayrılmış tam ədədlərdir. w və h evin döşəmə eni və hündürlüyüdür. n ruhların sayıdır. Onlar aşağıdakı məhdudiyyətlərə cavab verir.
4 ≤ w ≤ 16, 4 ≤ h ≤ 16, 1 ≤ n ≤ 3
Sonrakı h sətir w simvoldan ibarət döşəmə xəritəsidir. Hər bir c_ij ya:
bir '#' divar hüceyrəsini təmsil edir,
bir kiçik hərf bir ruhun ilkin mövqeyini təmsil edir,
a_n böyük hərf, kiçik hərfə uyğun gələn ruhun olması lazım olan mövqeyini təmsil edir, və ya
yuxarıda göstərilənlərdən heç biri olmayan bir dəhliz hüceyrəsini təmsil edən bir boşluq.
Hər bir xəritədə, ilk n hərf və A hərflərindən ilk n hərfi bir dəfə və yalnız bir dəfə görünür. Xəritənin ən kənar hüceyrələri divarlardır; yəni ilk və son sətirlərin bütün simvolları kəskin işarələrdir; və hər sətirin ilk və son simvolları da kəskin işarələrdir. Xəritədəki bütün dəhliz hüceyrələri birləşdirilib; yəni bir dəhliz hüceyrəsi verildikdə, 4-qonşuluqlardakı dəhliz hüceyrələrini izləyərək istənilən digər dəhliz hüceyrəsinə çata bilərsiniz. Eyni şəkildə, bütün divar hüceyrələri birləşdirilib. Hər hansı bir xəritədə hər hansı bir 2×2 sahədə ən azı bir kəskin işarə var. Hər xəritənin, bütün ruhları olması lazım olan mövqelərə qaytaran bir hərəkət ardıcıllığı olduğunu qəbul edə bilərsiniz.
Son dataset boşluqla ayrılmış üç sıfırdan ibarət bir sətirlə izlənilir.
Girişdəki hər bir dataset üçün, ruhları olması lazım olan mövqelərə qaytarmaq üçün ən az addım sayını ehtiva edən bir sətir çıxış edilməlidir. Çıxış sətirində boşluq kimi əlavə simvollar olmamalıdır.
Nümunə 1