Qitələrin Birləşməsi#3101
Kontinental sürüşmə Yer səthindəki qitələrin vaxtilə bir arada olması və zamanla bir-birindən ayrılıb indiki mövqelərinə keçməsi ideyasını ifadə edir.
Bu məsələdə isə biz əks prosesi — Kontinental Birləşmə ilə maraqlanırıq.
Sadəlik naminə, fərz edək ki, qitələr bir vaxtlar birləşmiş vəziyyətdə olub və kvadrat təşkil edirdi. Zaman keçdikcə, bu kvadrat parçalanaraq biri-birindən ayrılmış, düzbucaqlı formalı müxtəlif qitəyə çevrilib və öz mövqeyindən uzaqlaşıb.
Sizə qitələrin (yəni, düzbucaqlıların) hazırki yerləri verilib. Bu yerlər peyklər vasitəsilə müəyyən olunub. Sizin ilk vəzifəniz verilmiş məlumatın düzgünlüyünü yoxlamaqdır. Məlumat aşağıdakı şərtlər ödənilirsə, düzgün hesab olunur: düzbucaqlıların hamısını elə bir yerə sürüşdürmək olar ki, onlar bir kvadrat əmələ gətirsin. Bir gedişdə istənilən düzbucaqlını seçib onu bir vahid şimala, cənuba, şərqə və ya qərbə itələyə bilərsiniz. Qitələr hərəkət zamanı bir-birinin altından keçə bilər — yəni, bir mövqe eyni anda bir neçə qitəyə aid ola bilər. Əgər kvadrat əmələ gətirmək mümkündürsə, sizdən həm də bunu etmək üçün lazım olan minimal gediş sayını tapmaq tələb olunur. Kvadratın son mövqeyi əhəmiyyətli deyil. Qeyd edək ki, yekun vəziyyətdə iki qitə üst-üstə düşməməli və bütöv kvadratda boş hüceyrə qalmamalıdır.
Girişin ilk sətrində testlərin sayı olan (T \leq 200) tam ədədi verilir. Hər test üçün ardıcıl sətirdən ibarət 20 \times 20 ölçülü xəritə verilir. Hər sətirdə simvol var: nöqtə (.) boş yeri, (ASCII ) isə torpağı göstərir. Hər simvolu hansısa qitənin tərkib hissəsidir.
Qeydlər:
Giriş xəritəsində müxtəlif qitələrə aid simvolları qonşu olmur. Hər bir düzbucaqlının içindədir.
İki hüceyrə əgər ümumi kənar paylaşırsa, qonşudur.
Xəritədə dəqiq olaraq simvolu (torpaq) var.
Qitələrin sayı, , ən çox -dir.
Hər testdən əvvəl bir boş sətir yerləşdirilib.
Düzbucaqlıların və məqsəd kvadratının kənarları oxlara paraleldir.
Burada dünya düzdür. Yəni, ilk və sonuncu sətir qonşu deyil. Eyni prinsip ilk və sonuncu sütuna da aiddir.
Hər test üçün, test nömrəsini çap edin. Əgər düzbucaqlıların hərəkəti ilə kvadrat əmələ gətirmək mümkün deyilsə, "invalid data" (tırnaq içində) çap edin. Əks halda, tələb olunan minimal gediş sayını çap edin.
Nümunə 1