Riddik Kubu
Tarixdə ən çox satılan oyuncaq olan Rubik Kubunu bilirsiniz. Ümumilikdə 350 milyondan çox satılmışdır.
Bir qazax biznesmen bu uğuru təkrarlamaq istəyərək, bu tapmacanın sadələşdirilmiş bir versiyasını hazırlayıb. Riddik Kubu n × m ölçüsündə, hər biri 1 × 1 ölçüsündə hüceyrələrdən ibarət bir düzbucaqlıdır və hər hüceyrə müəyyən bir rəngə boyanmışdır. Bir gedişdə istənilən bir sıra və ya sütunu istənilən istiqamətdə bir hüceyrə qədər dövrü şəkildə sürüşdürmək mümkündür. Məsələn, 2-ci sıranın sağa və 3-cü sütunun yuxarıya necə sürüşdüyü belədir:
Tapmacanın həlli, hər bir sırada və ya hər bir sütunda bütün hüceyrələrin eyni rəngdə olduğu bir konfiqurasiyadır (qələbə konfiqurasiyası).
Tapmacanın satışına başlamaq üçün onun mürəkkəbliyini qiymətləndirmək lazımdır, bu da sizin həll etməli olduğunuz məsələdir. Mürəkkəbliyi hesablamaq üçün sadələşdirilmiş qaydalardan istifadə edəcəyik: əvvəlcə bəzi sütunları (bəlkə də heç birini) və sonra bəzi sətirləri (bəlkə də heç birini) sürüşdürməlisiniz.
Sizə Riddik Kubunun konfiqurasiyasının təsviri veriləcək. Əgər verilmiş konfiqurasiyadan sadələşdirilmiş qaydalarla qələbə konfiqurasiyasını əldə etmək mümkündürsə, cari konfiqurasiyanın mürəkkəbliyi qələbəyə çatmaq üçün lazım olan minimal gedişlərin sayına bərabərdir. Əgər bu qaydalarla qələbə konfiqurasiyasını əldə etmək mümkün deyilsə, mürəkkəblik 100500 olaraq qəbul edilir (tapmaca adi qaydalarla hələ də həll edilə bilər, lakin çox mürəkkəbdir).
Giriş məlumatları
Birinci sətir iki tam ədəd n və m (1 ≤ n, m ≤ 5) ehtiva edir. Növbəti n sətir hər biri m tam ədəd ehtiva edir - tapmacanın təsviri. Hər bir ədəd müvafiq hüceyrənin boyandığı rəngin nömrəsidir. Rəng nömrələri 1-dən 100-ə qədər tam ədədlərdir. Verilən təsvirin hətta adi qaydalarla həll edilə bilən bir tapmacaya uyğun gəlməsi təmin edilmir.
Çıxış məlumatları
Bir tam ədəd çıxarın - verilmiş konfiqurasiyanın mürəkkəbliyi.