Problem Description

Commanding officers need to deploy artillery units on an N×M grid map. The map consists of N rows and M columns, with each cell being either mountainous terrain (denoted by 'H') or plain terrain (denoted by 'P'). Artillery units can only be placed on plain terrain, with a maximum of one unit per plain cell.

The attack range of an artillery unit extends two cells horizontally (left and right) and two cells vertically (up and down) from its position. Importantly, the attack range is not affected by terrain type. The challenge is to deploy the maximum number of artillery units such that no unit is within the attack range of another unit.

Input

The first line contains two positive integers N and M, separated by a space. The following N lines each contain M consecutive characters representing the map data, where each character is either 'P' (plain) or 'H' (mountain).

Constraints: N ≤ 100, M ≤ 10

Output

A single integer representing the maximum number of artillery units that can be deployed without violating the non-attack constraint.

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

Solution Approach

This problem can be solved using dynamic programming with bitmasking. The key insight is that since M is small (≤ 10), we can represent each row's artillery configuration as a bitmask where each bit indicates whether an artillery unit is placed in that column.

First, we preprocess all possible valid configurations for a single row (configurations where no two artillery units attack each other). Then, we use dynamic programming to consider valid configurations across three consecutive rows to ensure no attacks between them.

Implementation

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_ROWS = 110;
const int MAX_CONFIGS = 1000;

bool hasConflict(int config) {
    // Check if any artillery units in this configuration would attack each other
    if ((config & (config << 1)) || (config & (config << 2))) {
        return true;
    }
    return false;
}

int countUnits(int config) {
    // Count the number of artillery units in the configuration
    int count = 0;
    while (config) {
        count++;
        config = config & (config - 1);
    }
    return count;
}

int n, m;
vector<int> validConfigs;
int unitCounts[MAX_CONFIGS];
int terrain[MAX_ROWS];
int dp[MAX_ROWS][MAX_CONFIGS][MAX_CONFIGS];

bool isOnMountain(int row, int config) {
    // Check if any artillery unit is placed on a mountain
    return (terrain[row] & config) != 0;
}

bool areCompatible(int config1, int config2, int config3) {
    // Check if three configurations can coexist without attacks
    if ((config1 & config2) || (config1 & config3) || (config2 & config3)) {
        return false;
    }
    return true;
}

void initializeValidConfigs() {
    // Generate all valid configurations for a single row
    for (int i = 0; i < (1 << m); i++) {
        if (!hasConflict(i)) {
            validConfigs.push_back(i);
            unitCounts[validConfigs.size() - 1] = countUnits(i);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    
    // Read terrain data
    for (int i = 0; i < n; i++) {
        string row;
        cin >> row;
        for (int j = 0; j < m; j++) {
            if (row[j] == 'H') {
                terrain[i] |= (1 << (m - 1 - j));
            }
        }
    }
    
    initializeValidConfigs();
    int numConfigs = validConfigs.size();
    
    // Initialize DP table for the first row
    for (int i = 0; i < numConfigs; i++) {
        int currentConfig = validConfigs[i];
        if (!isOnMountain(0, currentConfig)) {
            dp[0][i][0] = unitCounts[i];
        }
    }
    
    // Fill DP table for subsequent rows
    for (int row = 1; row < n; row++) {
        for (int i = 0; i < numConfigs; i++) { // Previous row config
            int prevConfig1 = validConfigs[i];
            if (isOnMountain(row - 1, prevConfig1)) continue;
            
            for (int j = 0; j < numConfigs; j++) { // Current row config
                int currentConfig = validConfigs[j];
                if (isOnMountain(row, currentConfig)) continue;
                
                // Check compatibility with two rows above
                if (row >= 2) {
                    for (int k = 0; k < numConfigs; k++) {
                        int prevConfig2 = validConfigs[k];
                        if (isOnMountain(row - 2, prevConfig2)) continue;
                        
                        if (areCompatible(prevConfig2, prevConfig1, currentConfig)) {
                            dp[row][j][i] = max(dp[row][j][i], dp[row-1][i][k] + unitCounts[j]);
                        }
                    }
                } else {
                    // For the second row, only check compatibility with the row above
                    if ((prevConfig1 & currentConfig) == 0) {
                        dp[row][j][i] = max(dp[row][j][i], unitCounts[j]);
                    }
                }
            }
        }
    }
    
    // Find the maximum number of artillery units
    int maxUnits = 0;
    for (int i = 0; i < numConfigs; i++) {
        for (int j = 0; j < numConfigs; j++) {
            maxUnits = max(maxUnits, dp[n-1][i][j]);
        }
    }
    
    printf("%d\n", maxUnits);
    return 0;
}