首页 > 代码库 > poj 1691 Painting A Board 拓扑序+dfs
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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。