本题主要思路:
1.通过枚举第一行的所有情况枚举一遍,只要将某一行的0的下一行该位置进行turn,
——则该情况就有唯一确定的方案,只需要将最后一行判断是否全为1并判断最小步数。
过程:
1.通过2进制枚举第一行的所有情况
2.将某一行的0的下一项同一位置turn
3.判断是否满足条件并判断最小步数
细节操作:
1.二进制枚举:
——通过0-31的二进制的每一位就可以表示第一行的所有方案
for(int i=0;i<32;i++) //枚举方案数
{
for(int j=0;j<5;j++) //枚举2进制的每一位的数值
{
if(i>>j&1) //判断二进制是什么
{
turn(1,j+1); //具体操作
step++;
}
}
}
2.cope数组:
——由于使用二进制会改变map数据,因此需要cope备份一下
——使其不会影响下一次枚举
道古:我是道古呼叫清明
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int const N=10;
char map[N][N];
char cope[N][N];
int dx[]={0,0,0,1,-1};
int dy[]={1,-1,0,0,0};
//turn函数
void turn(int x,int y)
{
int tx,ty;
for(int i=0;i<5;i++)
{
tx=x+dx[i]; ty=y+dy[i]; //通过偏移量来实现转化函数
if(tx<=5 && tx>=1 && ty>=1 && ty<=5)
{
if(map[tx][ty]=='1') map[tx][ty]='0';
else map[tx][ty]='1';
}
}
}
int main()
{
int n; cin>>n; //输入n
while(n--)
{
//第零步
int ans=10; //存储该样例最小的步数方案
for(int i=1;i<=5;i++)
for(int j=1;j<=5;j++)
cin>>map[i][j];
memcpy(cope,map,sizeof map); //输入地图并初始化cope
//第一步
for(int i=0;i<32;i++)
{
int step=0; //将该样例的每一个方案的步数初始化为0
for(int j=0;j<5;j++)
{
if(i>>j&1) //判断该方案的第一行的枚举情况
{
turn(1,j+1); //转化步数++
step++;
}
}
//第二步
for(int i=1;i<=4;i++)
{
for(int j=1;j<=5;j++)
{
if(map[i][j]=='0') //将每一行位置为0的下一行相同位置turn使该行变成1
{
turn(i+1,j); //转化步数++
step++;
}
}
}
//第三步
int flag=1;
for(int j=1;j<=5;j++)
{
if(map[5][j]=='0')
{
flag=0;
break;
}
}
if(flag==1) ans=min(ans,step);//判断步数和方案是否符合
memcpy(map,cope,sizeof cope); //现场恢复
}
//第四步
if(ans>6) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
}
大佬
大佬大佬tql
大佬大佬别骂了
大佬