Sürüşən Blok Tapmacası
Sürüşən blok tapmacalarında, parçaları (blokları) çərçivə daxilindəki boş yerlərə sürüşdürərək parçaların məqsədli yerləşdirilməsini təmin edirik.
Bir tapmaca yaradıcısı sürüşən blok tapmacaları və labirintlərin ideyalarını birləşdirərək yeni bir tapmaca hazırlayıb. Tapmaca, vahid kvadratlara bölünmüş düzbucaqlı çərçivədə oynanılır. Bəzi kvadratlar maneələrlə əvvəlcədən tutulub. Çərçivədə bir neçə parça yerləşdirilib: bir 2×2 kral parçası və bir neçə 1×1 piyada parçaları var. Məhz iki 1×1 kvadrat boş qalıb. Əgər piyada parçası boş kvadrata bitişikdirsə, parçanı ora sürüşdürə bilərik. Əgər kral parçasının bütün bir kənarı iki boş kvadrata bitişikdirsə, kral parçasını sürüşdürə bilərik. Maneələri hərəkət etdirə bilmərik. Verilən başlanğıc yerləşdirmədən başlayaraq, tapmacanın məqsədi kral parçasını çərçivənin yuxarı-sol küncünə hərəkət etdirməkdir.
Aşağıdakı şəkil nümunə girişin dördüncü məlumat dəstinin başlanğıc yerləşdirilməsini göstərir.
Şəkil 1: Nümunə girişin dördüncü məlumat dəsti.
Sizin vəzifəniz, parçaların verilmiş yerləşdirilməsindən tapmacanı həll etmək üçün minimum hərəkət sayını hesablayan bir proqram yazmaqdır. Burada bir hərəkət, ya kral, ya da piyada parçasını bitişik mövqeyə sürüşdürmək deməkdir.
Giriş verilənləri
Giriş məlumat dəstlərinin ardıcıllığıdır. Məlumat dəstinin ilk sətri boşluqla ayrılmış iki tam ədəd H və W-dən ibarətdir, burada H və W çərçivənin hündürlüyü və enidir. Növbəti H sətir, hər biri W simvoldan ibarət olmaqla, parçaların başlanğıc yerləşdirilməsini göstərir. Bu H sətirlərdə 'X', 'o', '*', və '.' müvafiq olaraq kral parçasının bir hissəsini, piyada parçasını, maneəni və boş kvadratı göstərir. Bu H sətirlərdə başqa simvollar yoxdur. Siz 3 ≤ H ≤ 50 və 3 ≤ W ≤ 50 olduğunu qəbul edə bilərsiniz.
Boşluqla ayrılmış iki sıfırdan ibarət bir sətir girişin sonunu göstərir.
Çıxış verilənləri
Hər məlumat dəsti üçün, kral parçasını yuxarı-sol küncə hərəkət etdirmək üçün tələb olunan minimum hərəkət sayını ehtiva edən bir sətir çıxarın. Əgər bunu etmək mümkün deyilsə, -1 çıxarın.