链接
背景
2006年NOIp模拟赛（一） by Matrix67 第四题 。
题意
给定 \(5*5\) 方格灯， \(0\) 表示关， \(1\) 表示开，每点击一格时上下左右四格均变为与原来相反的灯。求最少能使所有灯都开着的点击次数，若多于 \(6\) 次输出 \(-1\) 。
解法
不得不说这题解法挺妙的，通过确定第一行的点击方法递推确定后四行的点击方法。 由于第一行方法仅有 \(2^5=32\) 种，可以通过枚举一个 \(5\) 位二进制数 $n (0 \leqslant n < 2^5) $ 来解决。 当 \(n\) 的第 \(k\) 位上为 \(0\) 时，点击 \((1,k+1)\) 位置即可。 然后从第二行起， \((i-1,j)\) 位置为 \(0\) 时，点击 \((i,j)\) 位置即可。 每点击一次，记录一步，还要查 \(25\) 格是否均为 \(1\) 。
\(trick\)
\(1.\) 先把图取反，再按全部变成 \(0\) 去想要方便的多。
\(2.\) 对特定数取反直接 \(xor\) \(1\) 即可。
细节
\(1.\) 读入数据：按字符读入时一定注意所有的换行。（好傻逼的错误啊）
\(2.\) 方案变动：每个方案均要先复制一份原图再变动。（好傻逼的错误啊）
代码
$View$ $Code$
//省略头文件
using namespace std;
inline int read()
{
int ret=0,f=1;
char ch=getchar();
while(ch>'9'||ch='0'&&ch<='9')
{
ret=(ret<<1)+(ret<<3)+ch-'0';
ch=getchar();
}
return ret*f;
}
int n,tmp,ans;
char c;
bool s[6][6],ss[6][6];
inline void opr(int x,int y)
{
ss[x][y]^=1;
if(x>1)
ss[x-1][y]^=1;
if(y>1)
ss[x][y-1]^=1;
if(x<5)
ss[x+1][y]^=1;
if(y<5)
ss[x][y+1]^=1;
}
inline bool ck()
{
for(register int i=5;i>=1;i--)
for(register int j=5;j>=1;j--)
if(ss[i][j])
return 0;
return 1;
}
int main()
{
n=read();
while(n--)
{
for(register int i=1;i<=5;i++)
{
for(register int j=1;j<=5;j++)
{
scanf("%c",&c);
s[i][j]=(c-'0')^1;
}
scanf("%c",&c);
}
ans=1e8;
for(register int p=0;p<32;p++)
{
tmp=0;
for(register int i=1;i<=5;i++)
for(register int j=1;j<=5;j++)
ss[i][j]=s[i][j];
for(register int k=0;k<5;k++)
{
if(p>>k&1)
{
opr(1,k+1);
tmp++;
}
}
for(register int i=2;i<=5;i++)
{
for(register int j=1;j<=5;j++)
{
if(ss[i-1][j])
{
opr(i,j);
tmp++;
}
}
}
if(ck())
ans=min(ans,tmp);
}
if(ans<=6)
printf("%d\n",ans);
else
printf("-1\n");
if(n!=0)
scanf("%c",&c);
}
return 0;
}
转载于:https://www.cnblogs.com/Peter0701/p/11217109.html
