Titanların döyüşü
Sasha kompüter oyunlarının proqramlaşdırılması ilə maraqlanır. Artıq üç gündür ki, o, "Titanların Döyüşü" adlı yeni bir mobil telefon oyunu yazır. Oyunun qəhrəmanları qalay əsgərlərdir. Qalay əsgərin hərəkətlərini təsvir etmək üçün Sasha şahmat qalasını prototip kimi götürdü.
Şahmat qalası - şaquli və ya üfüqi olaraq istənilən sayda hüceyrə hərəkət edə bilən bir fiqurdur. Qalalar maneələri keçə bilməz. Tapşırıq - lövhədə elə maksimum sayda qala yerləşdirməkdir ki, heç bir ikisi bir-birini vurmur. Bu o deməkdir ki, konfiqurasiya düzgün sayılır, əgər heç bir iki qala bir-birinin görünüş sahəsində eyni üfüqi və ya şaquli xəttdə yerləşmirsə.
Növbəti nümunə beş şəkil göstərir. Birinci şəkil boşdur, ikinci və üçüncü şəkillər düzgün konfiqurasiyaları göstərir, dördüncü və beşinci şəkillər isə düzgün olmayan konfiqurasiyaların nümunələridir.
Sashaya proqramı mümkün qədər tez bitirməkdə kömək edin və lövhənin verilmiş konfiqurasiyası üçün maksimum qala sayını hesablayın.
Giriş verilənləri
Giriş faylında birinci sətirdə lövhənin ölçüsünü göstərən tam ədəd var, bu ədəd 4-dən çox deyil. Növbəti sətirlər şahmat lövhəsinin təsvirini ehtiva edir, burada '.' simvolu boş hüceyrəni, böyük hərflə 'X' simvolu isə maneəni göstərir. Giriş faylında boşluqlar yoxdur.
Çıxış verilənləri
Düzgün konfiqurasiya üçün maksimum qala sayını çıxarın.