Problem : 77 - 砲兵陣地

Problem Statistics

Solved Member: 8　　Submission: 44　　User Tried: 11

Statement:

司令部的將軍們打算在N*M的網格地圖上部署他們的砲兵部隊。一個N*M的地圖由N行M列組成，地圖的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下圖。在每一格平原地形上最多可以佈置一支砲兵部隊（山地上不能夠部署砲兵部隊）；一支砲兵部隊在地圖上的攻擊範圍如圖中黑色區域所示：

如果在地圖中的灰色所標識的平原上部署一支砲兵部隊，則圖中的黑色的網格表示它能夠攻擊到的區域：沿橫向左右各兩格，沿縱向上下各兩格。圖上其它白色網格均攻擊不到。從圖上可見砲兵的攻擊範圍不受地形的影響。

現在，將軍們規劃如何部署砲兵部隊，在防止誤傷的前提下（保證任何兩支砲兵部隊之間不能互相攻擊，即任何一支砲兵部隊都不在其他支砲兵部隊的攻擊範圍內），在整個地圖區域內最多能夠擺放多少我軍的砲兵部隊。

Input:Output:

第一行包含兩個由空格分割開的正整數，分別表示N和M；
接下來的N行，每一行含有連續的M個字符('P'或者'H')，中間沒有空格。按順序表示地圖中每一行的數據。N <= 100；M <= 10。

僅一行，包含一個整數K，表示最多能擺放的砲兵部隊的數量。

Sample Input:Sample Output:

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Source:

NOI 2001

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	500ms	5000kb
1	500ms	5000kb	10
2	500ms	5000kb	10
3	500ms	5000kb	10
4	500ms	5000kb	10
5	500ms	5000kb	10
6	500ms	5000kb	10
7	500ms	5000kb	10
8	500ms	5000kb	10
9	500ms	5000kb	10
10	500ms	5000kb	10