题目描述
blablabla
样例
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=504;
int n;
char g[N][N],backup[N][N];//用字符表示
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};//偏移量
void turn(int x, int y)
{
for(int i=0;i<5;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a<0 || a>5 || b<0 || b>5) continue;
g[a][b]^=1;//亦或操作,
}
}
int main()
{
cin>>n;
while(n--)
{
int res=10;
for(int i=0;i<5;i++) cin>>g[i];
for(int op=0;op<32;op++)
{
memcpy(backup,g,sizeof g);
int step=0;
for(int i=0;i<5;i++)//例举第一行所有的操作
if(op>>i & 1)
{
step++;
turn(0,i);
}
for(int i=0;i<4;i++)
for(int j=0;j<5;j++)
{
if(g[i][j]=='0')//如果是灭的,那么下面的一个必须按下去
{
step++;
turn(i+1,j);
}
}
bool dark=false;//判断最后一行是否有灭的灯,有的话就不更新
for(int i=0;i<5;i++)
{
if(g[4][i]=='0')
{
dark=true;
break;
}
}
if(!dark) res=min(res,step);
memcpy(g,backup,sizeof backup);
}
if(res>6) res=-1;
cout<<res<<endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
牛哇牛哇