Qitələrin Birləşməsi
Kontinental sürüş nəzəriyyəsi, bir zamanlar yerin qitələrinin bir bütöv olduğunu və zamanla bir-birindən ayrılaraq indiki mövqelərinə gəldiklərini izah edir.
Bu məsələdə isə biz əks proseslə - Kontinental Birləşmə ilə maraqlanırıq.
Qısaca desək, qitələrin əvvəlcə bir kvadrat şəklində birləşdiyini fərz edək. Zamanla bu kvadrat parçalanaraq mənbədən uzaqlaşan düzbucaqlı formalı K fərqli qitəyə çevrilib.
Sizə qitələrin (yəni düzbucaqlıların) cari yerləri verilir. Bu yerlər peyklərin köməyi ilə müəyyən edilmişdir. İlk işiniz verilən məlumatın etibarlı olub-olmadığını müəyyən etməkdir. Məlumat etibarlıdırsa, düzbucaqları hərəkət etdirərək bir kvadrat formalaşdıra bilərsiniz. Bir hərəkətdə, istənilən düzbucağı götürüb onu dörd istiqamətdən birinə (şimal, cənub, şərq və ya qərb) bir vahid itələyə bilərsiniz. Qitələr hərəkət zamanı bir-birinin altından sürüşə bilər - yəni, bir neçə qitə eyni mövqeyi eyni anda tuta bilər. Əgər kvadrat formalaşdırmaq mümkündürsə, bunu etmək üçün lazım olan minimum hərəkət sayını da tapmalısınız. Burada kvadratın son mövqeyi əsas məsələ deyil. Qeyd edək ki, son mövqedə iki qitə üst-üstə düşə bilməz və istənilən kvadratda heç bir boşluq olmamalıdır.
Giriş verilənləri
Girişin ilk sətri test hallarının sayını göstərən bir tam ədəd T (T ≤ 200) olacaq. Hər bir hal 20 sətrdən ibarət olacaq və hər bir sətirdə 20 simvol olacaq. Hər bir simvol ya boş yeri təmsil edən nöqtə (.) ya da bir qitənin bir hissəsi olan x (ASCII dəyəri 120) ola bilər.
Qeydlər:
Giriş şəbəkəsində, fərqli qitələrdən olan x simvolları bir-birinə bitişik olmayacaq. Hər bir x simvolu bir düzbucağın bir hissəsi olacaq.
İki hüceyrə bir ortaq kənar paylaşırsa bitişikdir.
Şəbəkədə dəqiq 25 x simvolu olacaq.
Qitələrin sayı, K, ən çox 5 olacaq.
Hər bir halın başlanğıcında boş bir sətir olacaq.
Düzbucaqlar və istənilən kvadrat ox paraleldir.
Burada yer düzdür. Yəni, birinci və sonuncu sətir bir-birinə bitişik DEYİL. Eyni şey birinci və sonuncu sütun üçün də keçərlidir.
Çıxış verilənləri
Hər bir hal üçün əvvəlcə hal nömrəsini çıxarın. Əgər düzbucaqları ətrafında hərəkət etdirərək kvadrat formalaşdırmaq mümkün deyilsə, "etibarsız məlumat" çıxarın, aydınlıq üçün dırnaq işarələri ilə. Əgər mümkündürsə, tapşırığı yerinə yetirmək üçün lazım olan minimum hərəkət sayını çıxarın.