City Oyunu#3348
Bob strategiya oyunları proqramlaşdırma mütəxəssisidir. Onun yeni şəhər qurma oyununda oyun mühiti belədir: şəhər sahələrdən ibarətdir və bu sahələrdə küçələr, ağaclar, fabriklər və binalar yerləşir. Sahədə hələ də boş olan bəzi yerlər var. Oyunun strateji məqsədi bu boş yerlərdən mümkün qədər çox kirayə pulu qazanmaqdır. Kirayə pulu qazanmaq üçün mümkün qədər uzun və geniş düzbucaqlı binalar tikmək lazımdır. Bob hər sahədə mümkün olan ən böyük binanı tikmək üçün bir yol tapmağa çalışır. Lakin o, tikdiyi sahədə artıq mövcud olan binaları, ağacları, fabrikləri və küçələri dağıtmağa icazə verilmir.
Hər sahənin eni və uzunluğu var. Sahə bərabər kvadrat vahidlərdən ibarət bir şəbəkəyə bölünür. Tikdiyiniz hər vahid üçün ödənilən kirayə 3$-dir.
Sizin vəzifəniz Bob-a bu problemi həll etməyə kömək etməkdir. Bütün şəhər K sahəyə bölünür. Hər bir sahə düzbucaqlıdır və öz uzunluğu M və eni N ilə fərqli bir şəbəkə ölçüsünə malikdir. Mövcud dolu vahidlər R simvolu ilə işarələnir. Boş vahidlər F simvolu ilə işarələnir.
Girişin ilk sətrində K tam ədədi var - məlumat dəstlərinin sayını müəyyən edir. Növbəti sətirlərdə sahə təsvirləri var. Bir təsvir aşağıdakı şəkildə müəyyən edilir: İlk sətir iki tam ədəd - sahənin uzunluğu M ≤ 1000 və eni N ≤ 1000, boşluqla ayrılmışdır. Növbəti M sətirdə boşluqla ayrılmış dolu və ya boş şəbəkə vahidlərini işarələyən N simvol var. İstifadə olunan simvollar:
R - dolu vahid
F - boş vahid
Hər bir sahə təsvirinin sonunda bir ayırıcı sətir var.
Girişdəki hər bir məlumat dəsti üçün standart çıxışda sahə tərəfindən kodlaşdırılmış ən böyük binanı tikməklə əldə olunan mənfəəti təmsil edən tam ədədi ayrıca sətirdə çap edin.
Nümunə 1