poj 1185

import java.io.*;

public class POJ_1185 {

	static int n, m;
	static int a[];
	static int sta[];
	static int cot[];
	static int num;
	static int sum;
	static int ans = 0;
	static int dp[][][];

	public static void main(String[] args) throws Exception {

		BufferedReader buf = new BufferedReader(
				new InputStreamReader(System.in));

		String[] data = buf.readLine().split(" ");
		n = Integer.parseInt(data[0]);
		m = Integer.parseInt(data[1]);

		init();
		dp = new int[105][105][105];   //dp[i][j][k]   i表示正在安排的当前行,  j表示i的前一行的状态, k表示当前行的状态 
		a = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			String str = buf.readLine();
			for (int j = 0; j < m; j++) {
				if (str.charAt(j) == 'H') {
					int temp = 1 << j;
					a[i] += temp;
				}
			}
		}

		DP();

	}

	public static void DP() {

		for (int i = 0; i < num; i++) {
			if (fit(sta[i], a[1]))
				continue;
			dp[1][0][i] = cot[i];
			ans = Math.max(dp[1][0][i], ans);
		}

		for (int i = 2; i <= n; i++) {
			for (int j = 0; j < num; j++) {
				for (int k = 0; k < num; k++) {
					if (fit(sta[k], a[i]) || fit(sta[j], a[i - 1])
							|| fit(sta[k], sta[j]))
						continue;
					for (int l = 0; l < num; l++) {         //l表示 第i-2行的状态    由前两行的状态 决定当前行i的状态
						if (fit(a[i - 2], sta[l]) || fit(sta[l], sta[j])
								|| fit(sta[l], sta[k]) || dp[i - 1][l][j] == 0)
							continue;
						dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][l][j]
								+ cot[k]);
					}
					ans = Math.max(ans, dp[i][j][k]);
				}
			}
		}

		System.out.println(ans);

	}

	public static void init() {
		sum = 1 << m;
		sta = new int[1 << 11];
		cot = new int[1 << 11];
		num = 0;

		for (int i = 0; i < sum; i++) {

			if (fit(i, i << 1) || fit(i, i << 2))
				continue;
			sta[num] = i;
			int temp = i;
			int count = 0;
			while (temp != 0) {
				count++;
				temp &= (temp - 1);
			}
			cot[num++] = count;
		}

	}

	public static boolean fit(int i, int j) {
		if ((i & j) != 0)
			return true;
		return false;
	}

}