hdu 1882 Strange Billboard

题目意思：给你一个局面的strange billboard，通过最少次的反转，问能否把它全部变成白色

其实这个题目和反转拼图一样，不过yzfy上数据更强，我还没能过。

解题思路：通过对第一行的状态进行枚举，枚举我用的是recur()递归做的，一旦第一行的状态确定了，下面各行的状态也就确定了。在这个过程中有几个优化地方，开始没优化在hdu上超时了。

第一个优化：如果你要反转的次数已经超过了an记录的结果，就可以不用继续下去if(t>=an) return;
第二个优化：我是枚举第一行，如果列比行大号多，就可以把矩阵转一下，这样可以减少好多时间

比如4*16这样枚举要2^16 如果变成16*4这样枚举就只要2^4

缺点：这个程序耗时也还是比较多，500多ms 可以通过转化为位运算进一步优化，暂时还没想出来！

#include
int m,n,D[20][20],tt[20][20];
int an;
inline void copy(int a[][20],int b[][20])
{
  int i,j;
    for(i=1;i<=m;i++)
    {
      for(j=1;j<=n;j++)
        a[i][j]=b[i][j];
    }
}
inline void flip(int D[][20],int x,int y)
{
  D[x][y]^=1;
  if(x>1) D[x-1][y]^=1;
  if(x  if(y>1) D[x][y-1]^=1;
  if(y}
void display()
{
  int i,j;
    for(i=1;i<=m;i++)
    {
      for(j=1;j<=n;j++)
        printf("%d ",D[i][j]);
      printf("\n");
    }
printf("\n");
}
void recur(int p,int t)
{
  int i,j,k,totel,f;
  if(t>=an) return;
  if(p>n)
  {
 //printf("t=%d\n",t);
    //display();
    copy(tt,D);
    totel=t;
    for(k=2;k<=m;k++)
    {
      for(j=1;j<=n;j++)
        if(tt[k-1][j]==1)
        {
        flip(tt,k,j);totel++;
        if(totel>=an) goto loop;
        }
    }
    f=1;
    //display();
    //printf("over\n\n");
    for(j=1;j<=n;j++)
      if(tt[m][j]==1){f=0;break;}
    if(f&&totel      an=totel;
      //printf("over\n\n");
loop:    return;
  }
  for(i=0;i<=1;i++)
  {
    if(i==1)
    {
    flip(D,1,p);
    recur(p+1,t+1);
    flip(D,1,p);
    }
    else
    {
    recur(p+1,t);
    }
    //if(i==1)flip(D,1,p);
  }
}
int main()
{
  int i,j,flag,temp;
  char ch[20];
  while(scanf("%d%d",&m,&n)&&m+n)
  {
    flag=0;
    for(i=1;i<=m;i++)
    {
    scanf("%s",ch);
    for(j=1;j<=n;j++)
      if(ch[j-1]=='X'){D[i][j]=1;flag=1;}
      else D[i][j]=0;
    }/*
    for(i=1;i<=m;i++)
    {
      for(j=1;j<=n;j++)
        printf("%d ",D[i][j]);
      printf("\n");
    }*/
    //display();
    ///原来就是这里没有换过来 导致超时
    if(n>m)
    {
      for(i=1;i<=m;i++)
      for(j=i+1;j<=n;j++)
      {
        temp=D[i][j];D[i][j]=D[j][i];D[j][i]=temp;                
      }
      temp=m;m=n;n=temp;     
    }
    if(flag==0)
    {printf("You have to tap 0 tiles.\n");continue;}
    an=1005;
    recur(1,0);
    if(an==1005)
      printf("Damaged billboard.\n");
    else
    printf("You have to tap %d tiles.\n",an);
  }
}