sgu132

132. Another Chocolate Maniac

time limit per test: 0.5 sec.

memory limit per test: 4096 KB

Bob really LOVESchocolate. He thinks he never gets enough. Imagine his joy when his parentstold him that they would buy him many rectangular chocolate pieces forhis birthday. A piece of chocolate is a 2x1 or 1x2 rectangle.Bob's parents also bought him a nice birthday cake, which can be imaginedas a matrix having M rows and N columns. Some positions onthe cake are occupied by candles, the others are empty. Bob's parents askedtheir son to place as many chocolate pieces as he can on the empty squareson the cake, in such a manner that no two chocolate pieces overlap. However,he would like to keep the chocolate pieces to himself. That's why, he wantsto place only a minimal amount of them on the cake and keep the rest. Inorder not to make Mon and Dad suspicious, Bob wants to place the chocolatepieces in such a way, that no other piece may be placed on the cake (thatis, there won't exist any two adjacent empty squares). Find the minimalnumber of pieces which need to be placed on the cake, so that they do notoverlap and no extra piece may be added.

Input

The first line ofthe input contains 2 integers: M (1<=M<=70)and N (1<=N<=7). Next, M lines will follow,each of them containing N characters, describing the cake. The characteron row i and column j of the cake may be either a '*'(ASCII code 42), representing a candle, or a'.' (ASCII code 46), representing an empty square.

Output

You should outputone integer: the minimal amount of pieces of chocolate which need to beplaced on the cake.

Sample Input

5 5
.*..*
*....
..**.
**.*.
.**..
      

Sample Output

4

題目大意:在一個N*M的矩陣中,有些位置不能放入巧克力,要求你放入盡可能少的1*2的巧克力,使得該矩陣中不能再放入巧克力.

題解:

看到那麼小的N,那麼熟悉的棋盤覆寫模型,狀壓DP很司空見慣了把.

也許有人會把這道題目跟上面的SGU131聯系起來,有一點不同的地方就是,131是要把棋盤覆寫滿,而132不用覆寫滿,

131我們知道某一行的狀态就可以直接知道它的上一行應該是什麼狀态,但是這道題目就不能這樣.是以我們在要儲存2維的狀态,分别為這一行的狀态和上一行的狀态,

這樣就可以避免後效性.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int mn = 80,mm = 10,ms = 512,INF = 0x7FFFFFFF/2;
int f[2][ms][ms],n,m,i,j,k,t;
int a[mn],mi[10]={1};
char op[10];int tmpJ,tmpK;
void dfs(int p,int j,int k,int s,int cnt){
    //保證目前行的前兩行不能放入2*1的巧克力
    if (p > 0 && ((k & mi[p-1]) == 0) && ((j & mi[p-1]) == 0)) return ;
    //保證目前行上一行不能放入1*2的巧克力
    if (p > 1 && ((k & mi[p-1]) == 0) && ((k & mi[p-2]) == 0)) return;
    //轉移
    if (p == m){
	f[i & 1][k][s] = min(f[i & 1][k][s],f[1-(i&1)][tmpJ][tmpK]+cnt);
	return;
    }
    //什麼都不放的狀态
    dfs(p+1,j,k,s,cnt);
    //在目前行的上一行放入一個1*2的骨牌
    if (p < (m-1) && ((k & mi[p]) == 0) && ((k & mi[p+1]) ==0)) 
	dfs(p+1,j,k | mi[p] | mi[p+1],s,cnt+1);
    //在目前行的上一行放入一個2*1的骨牌,并影響到目前行
    if (((k & mi[p]) == 0) && ((s & mi[p])==0))
	dfs(p+1,j,k | mi[p],s | mi[p],cnt+1);
}
int main(){
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    scanf("%d %d\n",&n,&m);t = (1 << m)-1;
    for (i=1;i<=m;++i) mi[i] = mi[i-1] *2;//計算2的幂次,用來減少計算量
    for (i = 1;i<=n;++i){
	scanf("%s\n",op+1);
	for (j=1;j<=m;++j)
	    a[i] = a[i]*2+(op[j]=='*');
	/*
	 *讀入每一行的不能覆寫的方案,二進制轉十進制儲存
	 *不能放為1,能放為0
	 */
    }
    /*
     *初始化
     */
    for (j = 0;j<=t;++j)
	for (k=0;k<=t;++k) f[0][j][k] = INF;
    f[0][t][a[1]] = 0;
    /*
     *動歸過程
     */
    for (i = 1;i<=n;++i){
	//初始化
	for (j=0;j<=t;++j)
	    for (k=0;k<=t;++k)
		f[i & 1][j][k] = INF;
	//枚舉目前行前兩行的狀态
	for (j=0;j<=t;++j)
	    for (k=0;k<=t;++k)
		if (f[1 - (i & 1)][j][k] != INF) {
		    tmpJ = j,tmpK = k,dfs(0,j,k,a[i+1],0);
		}
    }int ans = INF;
    for (i = 0;i<=t;++i)
	ans = min (ans,f[n & 1][i][0]);
    printf("%d\n",ans);
    return 0;
}