首页 > 代码库 > [HDU 5113] Black And White (dfs+剪枝)
[HDU 5113] Black And White (dfs+剪枝)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5113
题目大意：给你N*M的棋盘，K种颜色，每种颜色有c[i]个(sigma(c[i]) = N*M)，现在给棋盘染色，使得相邻的两个棋盘染成不同的颜色，并且把所有颜色用完。
因为棋盘最大为5*5的，因此可以考虑搜索+剪枝。
从左到右，从上到下看当前格子能够染成什么颜色。
有一个限制性条件，就是说如果当前棋盘的格子数量的一半小于一种颜色的数量时，那么就一定有两个相邻的棋盘被染成了相同的颜色。
因为假设棋盘容量为cap，那么我们间隔着放颜色，最多能够放cap/2个。
因此就可以用限制性条件来剪枝。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6 typedef long long LL; 7 typedef pair<int,int> PII; 8 typedef vector<int> vec; 9 typedef vector<vec> mat;10 #define AA first11 #define BB second12 13 int T,N,M,K;14 int m[10][10];15 int c[100];16 bool hasAns;17 18 bool C(int x,int y,int c){19 int row = true, column = true;20 if( x-1>=1&&m[x-1][y]==c ) column = false;21 if( y-1>=1 && m[x][y-1]==c ) row = false;22 return row&&column;23 }24 25 void dfs(int x,int y,int cur){26 for(int i=1;i<=K;i++){27 if( c[i]>(cur+1)/2 ) return;28 }29 if(hasAns) return;30 if( x==N+1 ){31 hasAns = true;32 puts("YES");33 for(int i=1;i<=N;i++) {34 for(int j=1;j<=M;j++ ){35 printf(j==M?"%d\n":"%d ",m[i][j]);36 }37 }38 return;39 }40 for(int i=1;i<=K;i++)if( c[i] ){41 if( C(x,y,i) ){42 c[i]--;43 m[x][y] = i;44 if( y==M ) dfs(x+1,1,cur-1);45 else dfs(x,y+1,cur-1);46 c[i]++;47 m[x][y] = 0;48 }49 }50 }51 52 int main(){53 scanf("%d",&T);54 for(int cases = 1; cases <= T; cases++){55 scanf("%d%d%d",&N,&M,&K);56 for(int i=1;i<=K;i++){57 scanf("%d",&c[i]);58 }59 hasAns = false;60 printf("Case #%d:\n",cases);61 dfs(1,1,N*M);62 if(!hasAns) puts("NO");63 }64 return 0;65 }
[HDU 5113] Black And White (dfs+剪枝)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。