样例输出 $13$

#include <bits/stdc++.h>

using namespace std;

long long n, m;
bool a[102][12];
char S[12];
long long f[102][(1 << 10) + 2][(1 << 10) + 2];

long long dkw (long long n, long long k) {
	n >>= k;
	return n & 1;
}

bool inlaw (long long s1, long long s2, long long p, long long s) {
	p = m - p;
	if (dkw(s1, p) == 1) return false;
	if (dkw(s2, p) == 1) return false;
	if (dkw(s, p + 1) == 1) return false;
	if (dkw(s, p + 2) == 1) return false;
	return true;
} // s1 p, s2 p, s p - 1, s p - 2

void dfs (long long i, long long s1, long long s2, long long p, long long s) {
	if (p > m) {
		f[i + 1][s][s1] += f[i][s1][s2];
		return;
	}
	dfs(i, s1, s2, p + 1, s);
	if (a[i][p] && inlaw(s1, s2, p, s)) 
		dfs(i, s1, s2, p + 1, s | (1 << (m - p)));
}

int main () {
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", S);
		for (long long j = 0; j < (long long)(strlen(S)); j++)
			if (S[j] == 'P') a[i][j + 1] = 1;
			else a[i][j + 1] = 0;
	}
	f[0][0][0] = 1ll;
	for (long long i = 0; i < n; i++)
		for (long long s1 = 0; s1 < (1 << m); s1++)
			for (long long s2 = 0; s2 < (1 << m); s2++)
				dfs(i, s1, s2, 1, 0);
	long long Max = 0;
	for (long long s1 = 0; s1 < (1 << m); s1++)
		for (long long s2 = 0; s2 < (1 << m); s2++)
			Max = max(Max, f[n][s1][s2]);
//	for (long long s1 = 0; s1 < (1 << m); s1++) {
//		for (long long s2 = 0; s2 < (1 << m); s2++)
//			printf("%lld ", f[n][s1][s2]);
//		puts("");
//	}
	printf("%lld", Max);
	return 0;
}