3133状态压缩插头dp.cpp

pku 3133 Manhattan Wiring 连通性状态压缩DP

#include <iostream>
#define MAX 59100
#define INF 0x3ffffff
#define mmin(x, y) ((x) < (y) ? (x): (y))
using namespace std;

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


int solve()
{
	int i, j, k;
	for(i = 0; i <= n; i++)		//注意初始化
		for(j = 0; j <= m; j++)
			for(k = 0; k <= t[m+1]; k++)
				dp[i][j][k] = INF;
	
	dp[0][0][0] = 0;
	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] != INF){
			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] == 1){
				if(j1 == 0 && j2 == 0)
					dp[i][j+1][k] = mmin(dp[i][j+1][k], dp[i][j][k]);
			}
			else if(g[i][j] == 2){
				if(j1 == 0 && j2 == 1 || j1 == 1 && j2 == 0)
					dp[i][j+1][pre_s] = mmin(dp[i][j+1][pre_s], dp[i][j][k]+1);
				if(j1 == 0 && j2 == 0){
					dp[i][j+1][pre_s+t[j]] = mmin(dp[i][j+1][pre_s+t[j]], dp[i][j][k]+1);
					dp[i][j+1][pre_s+t[j+1]] = mmin(dp[i][j+1][pre_s+t[j+1]], dp[i][j][k]+1);
				}
			}
			else if(g[i][j] == 3){
				if(j1 == 0 && j2 == 2 || j1 == 2 && j2 == 0)
					dp[i][j+1][pre_s] = mmin(dp[i][j+1][pre_s], dp[i][j][k]+1);
				if(j1 == 0 && j2 == 0){
					dp[i][j+1][pre_s+2*t[j]] = mmin(dp[i][j+1][pre_s+2*t[j]], dp[i][j][k]+1);
					dp[i][j+1][pre_s+2*t[j+1]] = mmin(dp[i][j+1][pre_s+2*t[j+1]], dp[i][j][k]+1);
				}
			}
			else {
				if(j1 == 0 && j2 == 1 || j1 == 1 && j2 == 0){
					dp[i][j+1][pre_s+t[j]] = mmin(dp[i][j+1][pre_s+t[j]], dp[i][j][k]+1);
					dp[i][j+1][pre_s+t[j+1]] = mmin(dp[i][j+1][pre_s+t[j+1]], dp[i][j][k]+1);
				}
				if(j1 == 0 && j2 == 2 || j1 == 2 && j2 == 0){
					dp[i][j+1][pre_s+2*t[j]] = mmin(dp[i][j+1][pre_s+2*t[j]], dp[i][j][k]+1);
					dp[i][j+1][pre_s+2*t[j+1]] = mmin(dp[i][j+1][pre_s+2*t[j+1]], dp[i][j][k]+1);
				}
				if(j1 == 1 && j2 == 1 || j1 == 2 && j2 == 2)
					dp[i][j+1][pre_s] = mmin(dp[i][j+1][pre_s], dp[i][j][k]+1);
				if(j1 == 0 && j2 == 0){
					dp[i][j+1][pre_s] = mmin(dp[i][j+1][pre_s], dp[i][j][k]);
					dp[i][j+1][pre_s+t[j]+t[j+1]] = mmin(dp[i][j+1][pre_s+t[j]+t[j+1]], dp[i][j][k]+1);
					dp[i][j+1][pre_s+2*t[j]+2*t[j+1]] = mmin(dp[i][j+1][pre_s+2*t[j]+2*t[j+1]], dp[i][j][k]+1);
				}
			}
		}
		for(k = 0; k < t[m]; k++)
			dp[i+1][0][k*3] = dp[i][m][k];
	}
	if(dp[n-1][m][0] == INF)
		return 0;
	else 
		return dp[n-1][m][0] - 2;
}


int main()
{
	//freopen("data.txt", "r", stdin);
	int i, j, k;
	for(i = 0; i < 59100; i++){
		j = 0;
		k = i;
		while(k > 0){
			ibit[i][j] = k%3;
			k = k/3;
			j++;
		}
	}
	t[0] = 1;
	for(i = 1; i < 11; i++)
		t[i] = 3*t[i-1];
	while(scanf("%d%d", &n, &m) != EOF){
		if(n == 0 || m == 0)
			break;
		for(i = 0; i < n; i++)
			for(j = 0; j < m; j++)
				scanf("%d", &g[i][j]);
		printf("%d\n", solve());
	}
return 0;
}