恩，这题......
看看题面想到了啥？炮兵阵地！
再仔细一思考：炮兵阵地是求放置最多，而这个显然可以递推得出。
由于每个格子至多点一次，那么我们发现：
在第一行点击状态确定的情况下，后面每个格子的点击与否都是确定的。那么我们点完之后判断一下最后一行合不合法即可。
#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代码