算法:递推
全局变量记录最优解
(1)先对第一行的操作进行所有情况的枚举
(2)从第一行开始对接下来的行进行递推(若g[i][j]=0,则必须要按g[i+1][j])
(3)由最后一行的状态进行判断,是否成功,成功则更新全局变量最优解
时间复杂度:$2^N·N^2·5·T$
在本题中N=5,T为多组测试数据,5为”十”字形的五个方向
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=6;
char g[N][N],backup[N][N];
int dx[5]={-1,0,1,0,0};
int 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; // ASCII 特性决定
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
for(int i=0;i<5;i++)scanf("%s",backup[i]);
int res=10;
for(int op=0;op<32;op++){
int cnt=0;
memcpy(g,backup,sizeof g);
for(int i=0;i<5;i++){
if(op>>i&1){
turn(0,i);
cnt++;
}
}
for(int i=0;i<4;i++){
for(int j=0;j<5;j++){
if(g[i][j]=='0'){
turn(i+1,j);
cnt++;
}
}
}
bool success=true;
for(int i=0;i<5;i++){
if(g[4][i]=='0'){
success=false;
break;
}
}
if(success)res=min(res,cnt);
}
if(res>6)res=-1;
printf("%d\n",res);
}
return 0;
}