B. Бяцхан гахайнууд ба чононууд

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Эрт дээр үед хэсэг бяцхан гахайнууд, чононууд $n × m$ хэмжээтэй хоёр хэмжээст сараалжин хашаанд амьдардаг байв. Сараалжин хашааны нүд тус бүр нь хоосон эсвэл нэг гахай, нэг чононы аль нэгийг агуулна. Хэрэв сараалжны нэг гахай, нэг чоно байх нүднүүд нэг талаараа нийлсэн бол үүнийг зэргэлдээ нүд гэнэ. Бяцхан гахайнууд чононоос айх учир нэг бяцхан гахай агуулсан нүдтэй зэрэгцээ хамгийн ихдээ нэг чоно байна. Гэвч чоно тус бүрийн ойролцоо хэдэн ч гахай байж болно.

Тэд ийм байдлаар нилээд хэдэн жил эв найртай амьдарч байгаа билээ. Гэвч өнөөдөр чононууд их өлсчээ. Чононууд нэг нэгээрээ өөрийн зэрэгцээ гахайнуудаас нэгийг сонгоод хөөрхий гахайнуудыг иднэ. Энэ үйл явц дахин давтагдахгүй ба нэг чоно хамгийн ихдээ нэг л гахай иднэ гэсэн үг. Хэрэв бяцхан гахайг нэг чоно идсэн бол гахай алга болж өөр чоно түүнийг идэх боломжгүй юм.

Чононууд хамгийн ихдээ хэдэн гахай идэх магадлалтай вэ?

Оролт

Эхний мөрөнд $n$ болон $m$ ($1 ≤ n, m ≤ 10$) гэсэн хоёр бүхэл тоо агуулах ба эдгээр нь хоёр хэмжээст сараалжин хашааны эгнээний болон баганы тоог тус тус харуулна. Дараагийн $n$ мөрүүд нь тус бүрдээ $m$ тэмдэгтүүд агуулах бөгөөд энэ нь сараалжны тодорхойлолтыг агуулна. "." нь тухайн нүд хоосон гэдгийг илтгэнэ. "P" нь тухайн нүдэнд бяцхан гахай буйг, "W" нь чоно байгааг тус тус илэрхийлнэ. Хэдэн ч бяцхан гахайтай хамгийн ихдээ нэг л чоно зэрэгцээ байна.

Гаралт

Чононууд хамгийн ихдээ хэдэн гахай идэх магадлалтайг харуулсан ганц тоо хэвлэнэ үү.

Орчуулсан: Энхгэрэл

Жишээ тэстүүд

Оролт
2 3
PPW
W.P
Гаралт
2
Оролт
3 3
P.W
.P.
W.P
Гаралт
0

Тэмдэглэл

Эхний жишээнд хоёр бяцхан гахай идүүлсэн байх нэг боломжит хувилбар байж болохыг доор харуулъя.

Сэтгэгдлүүдийг ачааллаж байна...