问题描述
何老板的密码锁由四位数字组成,每个数字的范围在1到9之间。
现在何老板告诉你开锁的密码,问,你最少需要多少步才能打开锁。
每一步,你可以进行下列三种操作:
1.向上转动密码盘,使一个数字加1(数字9再加1会变为1);
2.向下转动密码盘,使一个数字减1(数字1再减1会变为9);
3.交换两个相邻的数字(交换相邻两个密码盘,比如数字1357,交换左起第一和第二个密码盘后,得到3157)
输入格式
第一行,4个数字,表示锁当前的状态
第二行,4个数字,表示开锁的密码
输出格式
一个整数,表示打开锁需要的最少步数
思路+分析
考虑尝试BFS。
分类讨论加一、减一和交换数字的情况,简单模拟即可。
#include <cstdio>
#include <queue>
using namespace std;
int n,m,ans,a[10][10][10][10],b[5];
struct Node
{
int c[5];
int step;
};
queue<Node>q;
int main()
{
for(int i=1;i<=4;i++)
{
scanf("%d",&b[i]);
}
Node node;
for(int i=1;i<=4;i++)
{
scanf("%d",&node.c[i]);
}
//BFS
node.step=0;
q.push(node);
while(!q.empty())
{
Node nodee=q.front();
q.pop();
for(register int i=1;i<=4;i++)
{
//加一
node=nodee;
if(nodee.c[i]<9)
{
node.c[i]=nodee.c[i]+1;
}
else
{
node.c[i]=1;
}
node.step=nodee.step+1;
if(node.c[1]==b[1] && node.c[2]==b[2] && node.c[3]==b[3] && node.c[4]==b[4])
{
printf("%d",node.step);
return 0;
}
if(a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]==0)
{
q.push(node);
a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]=1;
}
//减一
if(nodee.c[i]>1)
{
node.c[i]=nodee.c[i]-1;
}
else
{
node.c[i]=9;
}
node.step=nodee.step+1;
if(node.c[1]==b[1] && node.c[2]==b[2] && node.c[3]==b[3] && node.c[4]==b[4])
{
printf("%d",node.step);
return 0;
}
if(a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]==0)
{
q.push(node);
a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]=1;
}
}
//交换两个数
for(register int j=1;j<=3;j++)//可能是1与2 2与3 3与4,共三种情况
{
node=nodee;
node.c[j]^=node.c[j+1];
node.c[j+1]^=node.c[j];
node.c[j]^=node.c[j+1];
//等价于swap(node.c[j],node.c[j+1];
node.step++;
if(node.c[1]==b[1] && node.c[2]==b[2] && node.c[3]==b[3] && node.c[4]==b[4])
{
printf("%d",node.step);
return 0;
}
if(a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]==0)
{
q.push(node);
a[node.c[1]][node.c[2]][node.c[3]][node.c[4]]=1;
}
}
}
}