## DP Finite Automata with Compression: Artillery Position

The generals plan to deploy their artillery troops on a grid map of N × M.

Each cell may be a map of the mountain (with H representation), it may be plain (with P representation), as shown below.

At most one artillery unit can be deployed on each grid of plain terrain (P) and artillery units cannot be deployed on mountainous terrain (H); the attack range of an artillery unit on the map is shown in the black area in the figure:

If an artillery unit is deployed on the plain marked by gray in the map, the black grid in the figure indicates the area it can attack: two squares in the horizontal direction and two squares in the vertical direction.

None of the other white grids on the map can be attacked.

It can be seen from the picture that the attack range of the artillery is not affected by the terrain.

Now, the generals plan how to deploy artillery units, under the premise of preventing accidental injury (ensure that no two artillery units can attack each other, that is, any artillery unit is not within the attack range of other artillery units) in the entire map. Find the maximum number of artillery units that can be placed in the area.

Input format
The first line contains two positive integers separated by spaces, which represent N with M；

Next N Rows, each row contains consecutive M characters ( P or H) without spaces. Represents the data of each row in the map in order.

Output format
Only one line, contains an integer K, Which indicates the maximum number of artillery units that can be placed.

data range N≤ 100 , M≤ 10

Input sample:

Sample Input:

5 4
PHPP
PPHH
PPPP
PHPP
PHHP


Sample Output:

6


### Solution

dp[i][j][k]: the maximum number of artilleries placed

• i: current row,
• j: the placement of artilleries in row i
• k: the placement of artilleries in row i - 1

dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][u] + cnt[j])

Optimization:

• We use a rolling array to compress the first dimension to 2 since only i-1 values are needed.
• We add valid j to a list state[] and enumerate that list for all possible i, i-1, i-2 rows

dp[i%2][state[j]][state[k]] = max(dp[i%2][state[j]][state[k]], dp[(i-1)%2][state[k]][state[u]] + cnt[state[j]])