題目 2498:
信息學(xué)奧賽一本通T1595-炮兵陣地
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 18 解決: 11
題目描述
原題來(lái)自：NOI 2001
司令部的將軍們打算在 N×M 的網(wǎng)格地圖上部署他們的炮兵部隊(duì)。一個(gè) N×M 的地圖由 N 行 M 列組成，地圖的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊(duì)（山地上不能夠部署炮兵部隊(duì)）；一支炮兵部隊(duì)在地圖上的攻擊范圍如圖中黑色區(qū)域所示：
司令部的將軍們打算在 N×M 的網(wǎng)格地圖上部署他們的炮兵部隊(duì)。一個(gè) N×M 的地圖由 N 行 M 列組成，地圖的每一格可能是山地（用 H 表示），也可能是平原（用 P 表示），如下圖。在每一格平原地形上最多可以布置一支炮兵部隊(duì)（山地上不能夠部署炮兵部隊(duì)）；一支炮兵部隊(duì)在地圖上的攻擊范圍如圖中黑色區(qū)域所示：
如果在地圖中的灰色所標(biāo)識(shí)的平原上部署一支炮兵部隊(duì)，則圖中的黑色的網(wǎng)格表示它能夠攻擊到的區(qū)域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網(wǎng)格均攻擊不到。從圖上可見(jiàn)炮兵的攻擊范圍不受地形的影響。
現(xiàn)在，將軍們規(guī)劃如何部署炮兵部隊(duì)，在防止誤傷的前提下（保證任何兩支炮兵部隊(duì)之間不能互相攻擊，即任何一支炮兵部隊(duì)都不在其他支炮兵部隊(duì)的攻擊范圍內(nèi)），在整個(gè)地圖區(qū)域內(nèi)最多能夠擺放多少我軍的炮兵部隊(duì)。
輸入格式
第一行包含兩個(gè)由空格分割開的正整數(shù)，分別表示 N 和 M；
接下來(lái)的 N行，每一行含有連續(xù)的 M 個(gè)字符(P 或者 H)，中間沒(méi)有空格。按順序表示地圖中每一行的數(shù)據(jù)。
接下來(lái)的 N行，每一行含有連續(xù)的 M 個(gè)字符(P 或者 H)，中間沒(méi)有空格。按順序表示地圖中每一行的數(shù)據(jù)。
輸出格式
僅一行，包含一個(gè)整數(shù) K，表示最多能擺放的炮兵部隊(duì)的數(shù)量。
樣例輸入
5 4 PHPP PPHH PPPP PHPP PHHP
樣例輸出
6
提示
數(shù)據(jù)范圍與提示：
N≤100,M≤10。
N≤100,M≤10。