首页 > 代码库 > hdu 5113 Black And White

hdu 5113 Black And White

2024-11-08 08:35:02   203人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=5113

题意：给你n*m的格子，然后在每个格子内涂色，相邻格子不能同色，然后给你每个颜色涂的格子的固定个数，然后可不可以实现，可以实现输出任意一种，否则输出NO

思路：dfs枚举，剪纸，每种颜色剩余的个数不能超过剩余格子数的一半，如果剩余格子数是奇数，不能超过一半加1，偶数是一半。

技术分享
  1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #define maxn 100  5 using namespace std;  6   7 struct node  8 {  9     int c; 10     int id; 11     bool operator<(const node &a)const 12     { 13         return c>a.c; 14     } 15 }p[10000]; 16 int t,n,m,k; 17 int c[maxn]; 18 int g[100][100]; 19 bool flag1; 20  21 void dfs(int cc) 22 { 23     if(flag1) return; 24     if(cc>=n*m) return ; 25     for(int i=1; i<=k; i++) 26     { 27         if((n*m-cc)%2==0) 28         { 29           if(p[i].c>(n*m-cc)/2) return; 30         } 31         else 32         { 33             if(p[i].c>(n*m-cc)/2+1) return; 34         } 35     } 36     int x=cc/m; 37     int y=cc%m; 38     for(int i=1; i<=k; i++) 39     { 40         if((g[x-1][y]==p[i].id&&x-1>=0)||(g[x][y-1]==p[i].id&&y-1>=0)) continue; 41         if(p[i].c==0) continue; 42         g[x][y]=p[i].id; 43         p[i].c--; 44         dfs(cc+1); 45         p[i].c++; 46         if(cc==n*m-1) 47         { 48             flag1=true; 49             printf("YES\n"); 50             for(int xx=0; xx<n; xx++) 51             { 52                 for(int yy=0; yy<m; yy++) 53                 { 54                     if(yy==0) printf("%d",g[xx][yy]); 55                     else printf(" %d",g[xx][yy]); 56                 } 57                 printf("\n"); 58             } 59         } 60     } 61 } 62  63 int main() 64 { 65     scanf("%d",&t); 66     for(int cas=1; cas<=t; cas++) 67     { 68         scanf("%d%d%d",&n,&m,&k); 69         for(int i=1; i<=k; i++) 70         { 71             scanf("%d",&c[i]); 72             p[i].c=c[i]; 73             p[i].id=i; 74         } 75         sort(p+1,p+k+1); 76         bool flag=true; 77         for(int i=0; i<k; i++) 78         { 79             if((n*m)%2==0) 80             { 81                 if(c[i]>(n*m/2)) 82                 { 83                     flag=false; 84                     break; 85                 } 86             } 87             else 88             { 89                 if(c[i]>((n*m)/2+1)) 90                 { 91                     flag=false; 92                     break; 93                 } 94             } 95         } 96         printf("Case #%d:\n",cas); 97         if(!flag) 98         { 99             printf("NO\n");100             continue;101         }102         flag1=false;103         dfs(0);104         if(!flag1) printf("NO\n");105     }106     return 0;107 }
View Code

 

hdu 5113 Black And White


联系
我们