poj 1691 Painting A Board 拓扑序+dfs

题意：

一个木板上被分成了很多区域，每个区域要涂上一种特定的颜色，当涂一个区域的时候，它上方与它有重合部分的区域必须之前要涂好。求最少需要拿几次画笔（拿一次画笔可以涂颜色相同的多个区域）。

分析：

上方与它有重合部分的区域必须之前要涂好这个限制可以用拓扑序来描述，每次涂有很多种可以涂的颜色，dfs就可以了。dfs的状态空间维数定为拿笔的次数，每次枚举可以涂的颜色。要注意的是dfs过程中要慎用全局变量。。否则每个维度需枚举的东西被下一维改了就跪了。。。

代码：

//poj 1691
//sep9
#include <iostream>
using namespace std;
int n,col_max,ans;
int g[32][32];
int d[32];
int colored[32];

struct P
{
	int x1,y1,x2,y2,col;
}p[32];

void dfs(int color_used,int times)
{
	if(color_used>=n){
		ans=times;
		return ;
	}
	if(times>=ans)
		return ;
	int i,j,k,col,col_num,t=0;
	int tmp1[32];
	int tmp2[32];
	int try_col[32];
	int in_set[32];
	memset(try_col,0,sizeof(try_col));
	memset(in_set,0,sizeof(in_set));
	for(i=1;i<=n;++i)
		if(!d[i]&&!colored[i]&&!in_set[p[i].col]){
			try_col[++t]=p[i].col;
			in_set[p[i].col]=1;
		}
	for(i=1;i<=t;++i){
		col=try_col[i];
		col_num=0;
		memcpy(tmp1,colored,sizeof(colored));
		memcpy(tmp2,d,sizeof(d));
		while(1){
			int find;
			for(find=0,j=1;j<=n;++j)
				if(!d[j]&&!colored[j]&&p[j].col==col){
					colored[j]=1;
					find=1;
					++col_num;
					for(k=1;k<=n;++k)
						if(g[j][k]==1&&d[k])
							--d[k];
				}
			if(!find)
				break;						
		}
		dfs(color_used+col_num,times+1);
		memcpy(colored,tmp1,sizeof(tmp1));
		memcpy(d,tmp2,sizeof(tmp2));		
	}
	return ;	
}

int main()
{
	int cases,i,j;
	scanf("%d",&cases);
	while(cases--){
		scanf("%d",&n);
		memset(g,0,sizeof(g));
		memset(d,0,sizeof(d));
		memset(colored,0,sizeof(colored));
		col_max=0;
		for(i=1;i<=n;++i){
			scanf("%d%d%d%d%d",&p[i].x1,&p[i].y1,&p[i].x2,&p[i].y2,&p[i].col);
			col_max=max(col_max,p[i].col);
		}
		for(i=1;i<=n;++i)
			for(j=1;j<=n;++j)
				if(i!=j)
					if(p[i].x2==p[j].x1)
						if(!(p[i].y2<=p[j].y1||p[i].y1>=p[j].y2)){
							g[i][j]=1;
							++d[j];
						}
		ans=INT_MAX;
		dfs(0,0);
		printf("%d\n",ans);
	}
	return 0;	
} 

poj 1691 Painting A Board 拓扑序+dfs

原文：http://blog.csdn.net/sepnine/article/details/42607689