首页 > 代码库 > 搜索(剪枝优化):HDU 5113 Black And White
搜索(剪枝优化):HDU 5113 Black And White
Description
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.
― Wikipedia, the free encyclopedia
In this problem, you have to solve the 4-color problem. Hey, I’m just joking.
You are asked to solve a similar problem:
Color an N × M chessboard with K colors numbered from 1 to K such that no two adjacent cells have the same color (two cells are adjacent if they share an edge). The i-th color should be used in exactly c i cells.
Matt hopes you can tell him a possible coloring.
― Wikipedia, the free encyclopedia
In this problem, you have to solve the 4-color problem. Hey, I’m just joking.
You are asked to solve a similar problem:
Color an N × M chessboard with K colors numbered from 1 to K such that no two adjacent cells have the same color (two cells are adjacent if they share an edge). The i-th color should be used in exactly c i cells.
Matt hopes you can tell him a possible coloring.
Input
The first line contains only one integer T (1 ≤ T ≤ 5000), which indicates the number of test cases.
For each test case, the first line contains three integers: N, M, K (0 < N, M ≤ 5, 0 < K ≤ N × M ).
The second line contains K integers c i (c i > 0), denoting the number of cells where the i-th color should be used.
It’s guaranteed that c 1 + c 2 + ? ? ? + c K = N × M .
For each test case, the first line contains three integers: N, M, K (0 < N, M ≤ 5, 0 < K ≤ N × M ).
The second line contains K integers c i (c i > 0), denoting the number of cells where the i-th color should be used.
It’s guaranteed that c 1 + c 2 + ? ? ? + c K = N × M .
Output
For each test case, the first line contains “Case #x:”, where x is the case number (starting from 1).
In the second line, output “NO” if there is no coloring satisfying the requirements. Otherwise, output “YES” in one line. Each of the following N lines contains M numbers seperated by single whitespace, denoting the color of the cells.
If there are multiple solutions, output any of them.
In the second line, output “NO” if there is no coloring satisfying the requirements. Otherwise, output “YES” in one line. Each of the following N lines contains M numbers seperated by single whitespace, denoting the color of the cells.
If there are multiple solutions, output any of them.
Sample Input
41 5 24 13 3 41 2 2 42 3 32 2 23 2 32 2 2
Sample Output
Case #1:NOCase #2:YES4 3 42 1 24 3 4Case #3:YES1 2 32 3 1Case #4:YES1 22 33 1
这道题就是搜索,剪枝优化是如果当前未染色的点为x,(x+1)/2<max(col[i]),就可以return了。
1 #include <algorithm> 2 #include <iostream> 3 #include <cstring> 4 #include <cstdio> 5 using namespace std; 6 const int N=6; 7 int id[N][N],L[N*N],U[N*N],c[N*N]; 8 int T,cas,n,m,k,map[N*N],p[N*N]; 9 bool DFS(int x){10 if(x==n*m+1)return true;11 for(int i=1;i<=k;i++)12 if((n*m+2-x)/2<c[i])return false;13 for(int i=1;i<=k;i++){14 if(c[i]==0)continue;15 if(map[L[x]]!=i&&map[U[x]]!=i){16 c[i]-=1;map[x]=i;17 if(DFS(x+1))return true;18 c[i]+=1;map[x]=0;19 }20 }21 return false;22 }23 int main(){24 scanf("%d",&T);25 while(T--){int idx=0;26 scanf("%d%d%d",&n,&m,&k);27 for(int i=1;i<=k;i++)28 scanf("%d",&c[i]); 29 for(int i=1;i<=n;i++)30 for(int j=1;j<=m;j++)31 id[i][j]=++idx;32 for(int i=1;i<=n;i++)33 for(int j=1;j<=m;j++){34 L[id[i][j]]=id[i][j-1];35 U[id[i][j]]=id[i-1][j];36 }37 printf("Case #%d:\n",++cas);38 if(DFS(1)){39 puts("YES");40 for(int i=1;i<=n;i++){41 for(int j=1;j<m;j++)42 printf("%d ",map[(i-1)*m+j]);43 printf("%d\n",map[i*m]); 44 } 45 } 46 else puts("NO"); 47 }48 return 0;49 }
搜索(剪枝优化):HDU 5113 Black And White
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。