[水题]ZOJ3038 Triangle War II

题意：

给了这样一张图有两种状态：pushed(*)和unpushed(.) 为方便起见分别成为开和关

改变一个点的开关状态会同时改变与它相邻的点的开关状态比如改变5，则2、3、4、6、8、9都会改变

N（行数）最多为6 即最多21个点

求：任意改变开关状态后最多能有几个关着。

为什么这么像高斯消元！！！

每个点的状态只有开和关总共就只有2^21个状态

dfs会爆栈！

所以bfs就行了！把这些点的开关状态看成二进制用0到$2^{21}$的数组来标记当前状态有没有出现过

  1 struct node
  2 {
  3     bool a[25];
  4 }front, rear;
  5 queue<node> q;
  6 int ans;
  7 bool vis[2100000];
  8 int biao[]={0, 1, 3, 6, 10, 15, 21};
  9 int b[][2]={
 10             {0,0},
 11             {-1,0},
 12             {-1,-1},
 13             {1,0},
 14             {1,1},
 15             {0,1},
 16             {0,-1}
 17            };
 18 int l[25], c[25][10];
 19 void pre()
 20 {
 21     memset(l, 0, sizeof(l));
 22     for(int i=1;i<=21;i++)
 23     {
 24         int x=0;
 25         while(biao[x]<i)
 26             x++;
 27         int y=i-x*(x-1)/2;
 28         for(int k=0;k<7;k++)
 29         {
 30             int dx=x+b[k][0];
 31             int dy=y+b[k][1];
 32             if(dx>=1 && dx<=6 && dy>=1 && dy<=dx)
 33                 c[i][l[i]++]=dx*(dx-1)/2+dy;
 34         }
 35     }
 36 }
 37 void bfs(int n)
 38 {
 39     int d=0;
 40     for(int i=1;i<=n;i++)
 41         d=(d<<1)+front.a[i];
 42     vis[d]=1;
 43     q.push(front);
 44     while(!q.empty())
 45     {
 46         front=q.front();
 47         q.pop();
 48         for(int i=1;i<=n;i++)
 49             if(!front.a[i])
 50             {
 51                 rear=front;
 52                 for(int j=0;j<l[i];j++)
 53                     rear.a[c[i][j]]=1^front.a[c[i][j]];
 54                 d=0;
 55                 int cnt=0;
 56                 for(int j=1;j<=n;j++)
 57                 {
 58                     d=(d<<1)+rear.a[j];
 59                     if(!rear.a[j])
 60                         cnt++;
 61                 }
 62                 if(!vis[d])
 63                 {
 64                     vis[d]=1;
 65                     ans=max(ans, cnt);
 66                     if(ans==n)
 67                         return ;
 68                     q.push(rear);
 69                 }
 70             }
 71     }
 72 }
 73 int main()
 74 {
 75     pre();
 76     int n;
 77     while(~scanf("%d", &n))
 78     {
 79         ans=0;
 80         for(int i=1;i<=n;i++)
 81             for(int j=1;j<=i;j++)
 82             {
 83                 char ch;
 84                 cin>>ch;
 85                 if(ch=='.')
 86                     ans++;
 87                 front.a[i*(i-1)/2+j]=(ch=='*');
 88             }
 89         n=(n+1)*n/2;
 90         if(ans==n)
 91         {
 92             printf("%d
", ans);
 93             continue;
 94         }
 95         while(!q.empty())
 96             q.pop();
 97         memset(vis, 0, sizeof(vis));
 98         bfs(n);
 99         printf("%d
", ans);
100     }
101     return 0;
102 }

ZOJ 3038