Masala #0189
Plyus * Plyus
Sizga \(N \times M\) o’lchamli jadval berilgan, har bir elementi yaxshi (good - G) yoki yomon (bad - B) ni ifodalaydi.
To’g’ri Plyus deb gorizontal va vertikal uzunliklari teng, bu uzunlik toq, chiziqlar o’zaro teng markazdan kesishganiga aytiladi. Plyusning yuzasi u egallab turgan yacheykalar soniga teng. Quyidagi diagrammada yashil maydonlar Plyus hisoblanadi, sariq maydonlar esa Plyus hisoblanmaydi.
Sizga berilgan jadvaldan tomonlari faqat yaxshi elementlardan iborat bo’ladigan shunday ikkita Plyusni ajratib olingki, ajratilgan Plyuslar jadvalda umumiy nuqtaga ega bo’lmasin va ikkila Plyusning yuzalari ko’paytmasi maksimal bo’lsin.
Dastlabki satrda ikkita butun son, \(N\) va \(M(2 \le N, M \le 15)\) sonlari, jadvalning qatorlar va ustunlar soni kiritiladi. Keyingi qatordan boshlab \(N\) ta qatorning har birida \(M\) tadan belgi, jadvalning elementlari kiritiladi.
Umumiy koordinataga ega bo’lmagan holda ajratib olingan ikkita Plyusning yuzalari ko’paytmasi maksimal necha bo’lishini chop eting.
# | input.txt | output.txt |
---|---|---|
1 |
5 6 GGGGGG GBBBGB GGGGGG GGBBGB GGGGGG |
5 |
2 |
6 6 BGBBGB GGGGGG BGBBGB GGGGGG BGBBGB BGBBGB |
25 |
Quyidagi rasmning chap tomonidagi jadvalda 1-test, o’ng tomondagi jadvalda 2-test bo’yicha ikkita Plyus qanday ajratib olinganligini ko’rishingiz mumkin: