Kəsik
Frodo, Sam, Merry və Pippin Yaşıl Əjdahada oturub pivə içərkən, növbəti raundda pivəni kimin alacağını müəyyən etmək üçün kağız və qələm ilə kiçik bir oyun oynamağa qərar verdilər. Oyun aşağıdakı kimidir:
m × n ölçülü düzbucaqlı lövhə var, hər hüceyrəsi W, I və ya N hərflərindən biri ilə işarələnmişdir. Lövhədən elə bir maksimum sayda triomino tapın ki, W və N hüceyrələri triominonun uclarında, I isə ortasında olsun (yəni hər hansı bir sırada WIN oxuna bilsin). Qəbul edilən triominolar ardıcıl üç hüceyrədən ibarət olub, düz xətt və ya künc şəklində yerləşə bilər. Ən çox triomino tapan şəxs qalib gəlir və pivə almağa gedəcək şəxsi göstərir. Siz bu cür sözlərin maksimum sayını tapmalısınız.
Giriş məlumatları
Bir neçə testdən ibarətdir. Hər test m × n ölçülü düzbucaqlı şəbəkə (1 ≤ m, n ≤ 30) ehtiva edir, burada W, I və N hərfləri var. Testlər bir-birindən boş sətirlə ayrılır.
Çıxış məlumatları
Hər test üçün lövhədən kəsilə bilən triominoların maksimum sayını ayrı bir sətirdə çıxarın.