經(jīng)典的狀態(tài)壓縮DP，狀態(tài)是f[i][j]，表示第i行，以3進(jìn)制j為狀態(tài)。j的位代表一個(gè)格子，只能是：0表示第i行和第i - 1行都沒有炮兵，1表示第i行沒有炮兵而第i-1行有炮兵，2表示第i行有炮兵。然后用DFS進(jìn)行狀態(tài)轉(zhuǎn)移。一開始我做了超時(shí)，后來預(yù)處理了一下合法狀態(tài)，快了不少，才AC。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-29 20:53:51
File Name: pku1185.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
typedef long long int64;
const int maxint = 0x7FFFFFFF;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{ for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) { for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 110;
const int maxm = 11;
const int mask[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323};
int n, m;
int g[maxn][maxm];
int f[maxn][59049];
int ok_state[10000];
int len;
int bits[14];
inline int get_bit(int x, int k)
{
return x % mask[k + 1] / mask[k];
}
void dfs(int origin_state, int origin_line, int now_col, int delta)
{
if (now_col >= m)
{
int new_state = 0;
for (int i = 0; i < m; i++)
if (bits[i] > 0)
new_state += bits[i] * mask[i];
f[origin_line + 1][new_state] >?= f[origin_line][origin_state] + delta;
return;
}
if (bits[now_col] == -1 && g[origin_line + 1][now_col] == 0)
{
bits[now_col] = 2;
dfs(origin_state, origin_line, now_col + 3, delta + 1);
bits[now_col] = -1;
}
dfs(origin_state, origin_line, now_col + 1, delta);
}
void dfs1(int now_col, int new_state, int last1, int last2)
{
if (now_col >= m)
{
ok_state[len++] = new_state;
return;
}
if (last1 != 2 && last2 != 2)
dfs1(now_col + 1, new_state + 2 * mask[now_col], 2, last1);
if (last1 != 1 && last2 != 1)
dfs1(now_col + 1, new_state + mask[now_col], 1, last1);
dfs1(now_col + 1, new_state, 0, last1);
}
void pre_process()
{
len = 0;
dfs1(0, 0, -1, -1);
}
int dp()
{
memset(f, -1, sizeof(f));
f[0][0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < len; j++)
if (f[i][ok_state[j]] != -1)
{
for (int k = 0; k < m; k++)
bits[k] = get_bit(ok_state[j], k) - 1;
dfs(ok_state[j], i, 0, 0);
}
}
int ret = 0;
for (int i = 0; i < mask[m]; i++)
ret >?= f[n][i];
return ret;
}
int main()
{
char s[22];
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%s", s);
for (int j = 0; j < m; j++)
if (s[j] == 'P')
g[i][j] = 0;
else
g[i][j] = 1;
}
pre_process();
printf("%d\n", dp());
return 0;
}