题目描述
blablabla
样例
//算法思想:用二进制的方式枚举出第一列的所有情况,如果对应位是1就turn
//根据前一行如果是关闭状态,那么它对应的下一列必须turn,来定义1-3行的操作(共0-4行,从0开始)
//对于最后一行,如果有dark就证明是无解的,返回-1,step>6也返回-1;
//注意,要用memcpy进行备份,因为对于第一行的每种操作方案,都要从初始棋盘开始,所以每次在修改原棋盘之前,都要先备份一遍。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=6;
char g[N][N],backup[N][N];
int dx[5]={-1,0,0,1,0};
int dy[5]={0,-1,1,0,0};
void turn(int x,int y){
for(int i=0;i<5;i++){
int a=x+dx[i];
int b=y+dy[i];
if(x>=5||x<0||y>=5||y<0) continue;
g[a][b]^=1;
}
}
int main(){
int n;
cin>>n;
while(n--){
for(int i=0;i<5;i++) cin>>g[i];
int res=10;
for(int i=0;i<=31;i++){//枚举第一行所有情况
memcpy(backup,g,sizeof g);
int step=0;
for(int j=0;j<5;j++){
if(i>>j&1){
step++;
turn(0,j);
}
}
for (int l = 0;l < 4;l ++ )//第1-3行,根据前一行和后一行的关系。
for (int j = 0; j < 5; j ++ )
if (g[l][j] == '0')
{
step ++ ;
turn(l + 1, j);
}
bool dark=false; //最后一行
for(int c=0;c<5;c++){
if(g[4][c]=='0') {
dark=true;
break;
}
}
if(!dark) {
res=min(res,step);
//if(res>6) res=-1;
}
memcpy(g,backup,sizeof g);
}
if(res>6) res=-1;
cout<<res<<endl;
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla