Flood-It
Flood-It, bir çox ağıllı telefonlarda məşhur olan tək oyunçulu bir oyundur. Oyunçuya n×n ölçüsündə bir taxta verilir və hər bir plitə 6 rəngdən (nömrələnmiş 1–6) biri ilə rənglənir. Hər bir plitə Şimal, Cənub, Şərq və Qərb istiqamətlərində ən çox 4 qonşu plitə ilə əlaqəlidir. Bir plitə başlanğıca (yuxarı sol küncdəki plitə) bağlıdırsa, bu plitə başlanğıcla eyni rəngdədir və yalnız bu rəngdəki plitələrdən ibarət bir yol vasitəsilə başlanğıca çatmaq mümkündür.
Oyunçu 6 rəngdən birini seçərək hərəkət edir. Seçim edildikdən sonra, başlanğıca bağlı olan bütün plitələr seçilən rəngə dəyişdirilir. Oyun bütün plitələr eyni rəngə sahib olana qədər davam edir. Oyunun məqsədi bütün plitələri mümkün qədər az hərəkətlə eyni rəngə çevirməkdir.
Optimal hərəkətləri tapmağın çox çətin bir problem olduğu sübut edilmişdir. Bu problem üçün çox sadə bir açgözlü strategiyanı simulyasiya edəcəksiniz:
hər hərəkət üçün, başlanğıca bağlı olan plitələrin sayını ən çox artıracaq rəngi seçin;
əgər bərabərlik varsa, ən aşağı nömrəli rəngi seçərək bərabərliyi pozun.
Bunu göstərmək üçün, nümunə girişindəki ilk test halına baxırıq, orijinal taxta belədir:
Əgər ilk hərəkət üçün rəng 3 seçsək, nəticə belə olacaq:
burada başlanğıca bağlı olan plitələr kölgələnmişdir. Növbəti hərəkətdə, başlanğıca bağlı olan plitələrin sayını 5 plitə artırmaq üçün rəng 4 seçirik:
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Girişin ilk sətri, ardınca gələcək test hallarının sayını göstərən, 20-dən çox olmayan tək bir tam ədəddir. Hər bir hal, n (1 ≤ n ≤ 20) tam ədədini ehtiva edən bir sətrlə başlayır. Növbəti n sətr, n×n ölçüsündəki plitələrin ilkin rənglərini verən n simvol ehtiva edir. Hər bir rəng 1 ilə 6 arasında bir rəqəmlə göstərilir.
Çıxış verilənləri
Hər bir hal üçün iki sətr çıxış göstərin. Birinci sətr, bütün plitələri eyni rəngə çevirmək üçün lazım olan hərəkətlərin sayını göstərir. İkinci sətr, bir boşluq ilə ayrılmış 6 tam ədəd ehtiva edir. i-ci tam ədəd, oyunda hərəkət olaraq rəng i-nin seçildiyi dəfə sayını göstərir.