TYVJ1266 费解的开关

恩，这题......

看看题面想到了啥？炮兵阵地！

再仔细一思考：炮兵阵地是求放置最多，而这个显然可以递推得出。

由于每个格子至多点一次，那么我们发现：

在第一行点击状态确定的情况下，后面每个格子的点击与否都是确定的。那么我们点完之后判断一下最后一行合不合法即可。

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #define say printf("*")

 using namespace std;

 const int N = ,INF = 0x3f3f3f3f;

 int a[N][N],f[N][N];

 void out()

 {

     printf("\n");

     for(int i=; i<=; i++)

     {

         for(int j=; j<=; j++) printf("%d ",a[i][j]);

         printf("\n");

     }

     return;

 }

 bool check(int x,int y)

 {

     return x<=&&x>=&&y<=&&y>=;

 }

 void click(int x,int y)

 {

     //printf("click:%d %d\n",x,y);

     a[x][y]^=;

     if(check(x,y+)) a[x][y+]^=;

     if(check(x,y-)) a[x][y-]^=;

     if(check(x+,y)) a[x+][y]^=;

     if(check(x-,y)) a[x-][y]^=;

     //out();

     return;

 }

 int cal(int x)

 {

     int a[],ans=;

     for(int i=;i<;i++) a[i]=bool(x&(<<i));

     for(int i=;i>=;i--) ans=ans*+a[i];

     return ans;

 }

 int main()

 {

     int T,s,ans;char ch;

     scanf("%d",&T);

     while(T--)

     {

         ans=INF;

         for(int i=; i<=; i++) ///读入

         {

             for(int j=;j<=;j++)

             {

                 ch=getchar();

                 while(ch!=''&&ch!='') ch=getchar();

                 f[i][j]=ch-'';

             }

         }

         for(int i=; i<(<<); i++) ///第一行

         {

             s=;

             for(int j=; j<=; j++)///复制

             {

                 for(int k=; k<=; k++) a[j][k]=f[j][k];

             }

             for(int j=; j>=; j--)///处理第一行

                 if((<<j)&i) {click(,-j);s++;}

             for(int j=;j<=;j++) ///处理后四行

             {

                 for(int k=;k<=;k++)

                     if(!a[j][k]) {click(j+,k);s++;}

             }

             bool bo=;

             for(int j=;j<=;j++)

                 if(!a[][j]) bo=;

             if(bo) continue;

             //printf("%d %d %d\n",cal(i),ans,s);

             ans=min(ans,s);

         }

         printf("%d\n",(ans<=?ans:-));

     }

     return ;

 }

AC代码