3.1费解的开关
#include<iostream>
#include<cstring>
using namespace std;
const int INF=1e6+10;
char g[10][10];
void turn(int x,int y)
{
int dx[5]={0,-1,0,1,0},dy[5]={0,0,1,0,-1};
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)
g[a][b]^=1;
}
}
int work()
{
int ans=INF;
//枚举状态
for(int k=0;k<1<<5;k++)//第一行摁或者不摁,有32种可能数来求最优解,00000~11111
{
int res=0;
char backup[10][10];
memcpy(backup,g,sizeof g);
///////////////////枚举第一行的摁操作,那首先规定从前往后看第一行的第j位是否是1,如果是,就要turn一下
//////////////////例如00000,表示5展灯都不摁,11111,表示5展灯都摁,所以我们就把第一行的所有摁的状态都枚举一遍
for(int j=0;j<5;j++)
if(k>>j&1)
{
res++;
turn(0,j);
}
//////////////////枚举前四行的状态
for(int j=0;j<4;j++)
{
for(int i=0;i<5;i++)
{
if(g[j][i]=='0')
{
res++;
turn(j+1,i);
}
}
}
//////////////////判断最后一行是不是全是1即可
bool is_successful=true;
for(int j=0;j<5;j++)
{
if(g[4][j]=='0')
{
is_successful=false;
break;
}
}
if(is_successful) ans=min(ans,res);
memcpy(g,backup,sizeof g);//g数组恢复原状重新枚举下一个状态
}
if(ans>6) ans=-1;
return ans;
}
int main()
{
int n;
cin>>n;
while(n--)
{
for(int i=0;i<5;i++)
cin>>g[i];
cout<<work()<<endl;
}
return 0;
}
3.2 奇怪的汉诺塔
#include<iostream>
#include<cstring>
using namespace std;
int d[15],f[15];
int main()
{
d[1]=1;
for(int i=2;i<=12;i++)
d[i]=2*d[i-1]+1;
memset(f,0x3f,sizeof f);
f[1]=1;
for(int i=2;i<=12;i++)//i个盘子4塔问题
{
//枚举前j个盘子(j<i)先移动
for(int j=1;j<i;j++)
{
f[i]=min(f[i],f[j]*2+d[i-j]);
}
}
for(int i=1;i<=12;i++) cout<<f[i]<<endl;
return 0;
}
网友评论