1739.cpp

pku 1739 Tony s Tour 连通性状态压缩DP

#include <iostream>
#define MAX 20000
using namespace std;

const int mm = 12;

int dp[mm][mm][MAX];
int n, m, g[mm][mm];
int ibit[MAX][mm], t[mm];

int find1(int k, int j, int pre_s)
{
	int i = j+1, p = 1;
	while(i <= m && p){
		if(ibit[k][i] == 1)
			p++;
		else if(ibit[k][i] == 2)
			p--;
		i++;
	}
	return pre_s - t[i-1];
}

int find2(int k, int j, int pre_s)
{
	int i = j-1, p = 1;
	while(i >= 0 && p){
		if(ibit[k][i] == 2)
			p++;
		else if(ibit[k][i] == 1)
			p--;
		i--;
	}
	return pre_s + t[i+1];
}


int solve()
{
	int i, j, k, l;
	memset(dp, 0, sizeof(dp));
	dp[0][0][0] = 1;
	for(i = 0; i < n; i++){
		for(j = 0; j < m; j++)
		for(k = 0; k < t[m+1]; k++) if(dp[i][j][k]){
			int j1 = ibit[k][j];
			int j2 = ibit[k][j+1];
			int pre_s = k - j1*t[j] - j2*t[j+1];
			if(g[i][j]){	//状态转移
				if(j1 == 0 && j2 == 0){
					dp[i][j+1][pre_s+t[j]+2*t[j+1]] += dp[i][j][k];
				}
				else if(j1 == 0 && j2 == 1 || j1 == 1 && j2 == 0){
					dp[i][j+1][pre_s+t[j]] += dp[i][j][k];
					dp[i][j+1][pre_s+t[j+1]] += dp[i][j][k];
				}
				else if(j1 == 0 && j2 == 2 || j1 == 2 && j2 == 0){
					dp[i][j+1][pre_s+2*t[j]] += dp[i][j][k];
					dp[i][j+1][pre_s+2*t[j+1]] += dp[i][j][k];
				}
				else if(j1 == 1 && j2 == 1){//特殊情况 1插头并1插头 
					l = find1(k, j+1, pre_s);
					dp[i][j+1][l] += dp[i][j][k];
				}
				else if(j1 == 2 && j2 == 2){//特殊情况 2插头并2插头 
					l = find2(k, j, pre_s);
					dp[i][j+1][l] += dp[i][j][k];
				}
				if(j1 == 2 && j2 == 1){
					dp[i][j+1][pre_s] += dp[i][j][k];
				}
			}
			else{
				if(j1 == 0 && j2 == 0)
					dp[i][j+1][pre_s] += dp[i][j][k];
			}
		}
		for(k = 0; k < t[m]; k++){
			dp[i+1][0][k*3] = dp[i][m][k];
		}
	}

	return dp[n-1][m][1+2*t[m-1]];
}


int main()
{
	//freopen("data.txt", "r", stdin);
	int i, j, k;
	for(i = 0; i < MAX; i++){
		j = 0;
		k = i;
		while(k > 0){
			ibit[i][j] = k%3;
			k = k/3;
			j++;
		}
	}
	t[0] = 1;
	for(i = 1; i < mm; i++)
		t[i] = 3*t[i-1];

	char s[100];
	while(scanf("%d%d", &n, &m) != EOF){
		memset(g, 0, sizeof(g));
		if(n == 0 && m == 0)
			break;
		for(i = 0; i < n; i++){
			scanf("%s", s);
			for(j = 0; j < m; j++)
				if(s[j] == '.')
					g[i][j] = 1;
				else 
					g[i][j] = 0;
		}
		printf("%d\n", solve());
	}
return 0;
}