HDU 5113

HDU 5113
类似四色定理的什么东西，大体就是dfs了，不过有两个坑点，这个题的逼格瞬间就上去了
1.剪枝很神奇，任何一种颜色都不能超过剩下总格子数的一半，想想确实显然但是比赛的时候没有想到：
2.测评时是所有字符，不忽略空格，导致我wa了很多遍。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<queue>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<ctime>
  7 #include<set>
  8 #include<map>
  9 #include<stack>
 10 #include<cstring>
 11 #define inf 2147483647
 12 #define For(i,a,b) for(register int i=a;i<=b;i++)
 13 #define p(a) putchar(a)
 14 #define g() getchar()
 15 
 16 using namespace std;
 17 int t,n,m,k,T;
 18 int a[10][10];
 19 int c[30];
 20 bool flag;
 21 
 22 void in(int &x)
 23 {
 24     int y=1;
 25     char c=g();x=0;
 26     while(c<'0'||c>'9')
 27     {
 28         if(c=='-')
 29             y=-1;
 30         c=g();
 31     }
 32     while(c<='9'&&c>='0')
 33     {
 34         x=(x<<1)+(x<<3)+c-'0';c=g();
 35     }
 36     x*=y;
 37 }
 38 void o(int x)
 39 {
 40     if(x<0)
 41     {
 42         p('-');
 43         x=-x;
 44     }
 45     if(x>9)o(x/10);
 46     p(x%10+'0');
 47 }
 48 
 49 bool ju(int x,int y){
 50     int num=n*m-((x-1)*m+y)+1;
 51     For(i,1,k)
 52     if(c[i]>(num+1)/2)
 53     return true;
 54     return false;
 55 }
 56 
 57 inline void dfs(register int x,register int y){
 58     
 59     if(ju(x,y))return;
 60     
 61     if(!flag)
 62     For(i,1,k)
 63       if(c[i]&&a[x-1][y]!=i&&a[x][y-1]!=i){
 64           a[x][y]=i;
 65           c[i]--;
 66           if(y<m){
 67               dfs(x,y+1);
 68               c[i]++;
 69           }
 70           
 71           else if(x<n&&y==m){
 72               dfs(x+1,1);
 73               c[i]++;
 74           }
 75           else if(x==n&&y==m){
 76               cout<<"YES"<<endl;
 77               For(i,1,n){
 78                   For(j,1,m)
 79                   if(j!=m)
 80                   o(a[i][j]),p(' ');
 81                   else
 82                   o(a[i][j]);
 83                   p('
');
 84               }
 85               flag=true;
 86               return;
 87           }
 88       }
 89 }
 90 
 91 int main()
 92 {
 93     in(T);
 94     while(++t<=T){
 95         cout<<"Case #"<<t<<":"<<endl;
 96         in(n);in(m);in(k);
 97         For(i,1,k)
 98           in(c[i]);
 99         dfs(1,1);
100         if(!flag)cout<<"NO"<<endl;
101         flag=false;
102     }
103     
104     return 0;
105 }

View Code