神奇密码锁 BFS (枚举) 进位转换 memcmp

题目描述

 小明忘记了旅行箱上的密码，现在他想自己暴力弄出密码来，但他又想知道最从一个数字到另一个数字最少需要多少步，现在请你帮忙。

另外，小明的密码箱很奇怪，只有四位数，上面的数字只有1到9，每次只能让每位数加1或者减1。按常识我们可以知道从1到9只需要减1，从9到1只需要加1。此外，你还能交换相邻的两个数字。如1234可以在一步后变成2134，但不能变成4231。

输入

第一行有一个整数：T，代表有多少组测试数据。

接下来T行，每行有两个整数（都是四位数），第一个是初状态，第二个是目标状态。

输出

每组数据输出一个整数，占一行。

样例输入

2

1234 2144

1111 9999

样例输出

#include 
#include 
#include 
#include 
using namespace std;
struct node
{char s[10];int sum;
};
int ans=0;
char st[10],goal[10];
int vis[10005];
bool in(char s[])
{int re=(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+s[3]-'0';if(!vis[re]){vis[re]=true;return true;}return false;
}
void BFS()
{queueque;node s;strcpy(s.s,st);s.sum=0;if(in(s.s))que.push(s);while(!que.empty()){s=que.front(); que.pop();if(strcmp(s.s,goal)==0)//memcmp(s.s,goal,sizeof(char)*4)==0{ans=s.sum ;return ;}for(int i=0;i<4;i++){ //密码设置 3种情况 上滑 下滑 移位//密码上滑char m=s.s[i];s.sum++;  //步数增加if(s.s[i]=='9') s.s[i]='1';else s.s[i]++;if(in(s.s)) //避免重复压入que.push(s);//压入队列进行判断//密码下滑s.s[i]=m;//还原该位数字if(s.s[i]=='1') s.s[i]='9';else s.s[i]--;if(in(s.s)) //避免重复压入que.push(s);//压入队列进行判断//密码位移s.s[i]=m;if(i<3){char mid=s.s[i+1];//发生密码位移s.s[i+1]=s.s[i];s.s[i]=mid;if(in(s.s))que.push(s);s.s[i]=m;s.s[i+1]=mid;//还原密码}s.sum--; //还原}}
}
int main()
{int icase;scanf("%d",&icase);while(icase--){scanf("%s%s",st,goal);memset(vis,0,sizeof(vis));BFS();printf("%d\n",ans);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！