神奇密码锁 (简单bfs)

时间限制: 2 Sec  内存限制: 128 MB
提交: 244  解决: 64
[提交][状态][讨论版]

题目描述

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

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

输入

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

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

输出

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

样例输入

2
1234 2144
1111 9999

样例输出

2
4

BFS一般用于求最优化问题，最值问题，题目有三种操作：上滑，下滑，交换。将这三种操作所得的结果加入队列，直到目标解。其实跟跳马问题极其相似，但是一定要记得还原！而且不要用string，会TLE。

#include
using namespace std;
char a[6],b[6];
int vis[10000];
int ans;
int in(char s[])
{if(!vis[(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0')]){vis[(s[0]-'0')*1000+(s[1]-'0')*100+(s[2]-'0')*10+(s[3]-'0')]=1;return 1;}return 0;
}
struct node
{char s[6];int step;
};
void bfs()
{queueqq;node f;strcpy(f.s,a);f.step=0;if(in(a)) qq.push(f);while(!qq.empty()){f=qq.front();qq.pop();if(strcmp(f.s,b)==0){ans=f.step;return;}for(int i=0;i<4;i++){char t=f.s[i];f.step++;if(f.s[i]!='9') f.s[i]++;else f.s[i]='1';if(in(f.s)) qq.push(f);f.s[i]=t;if(f.s[i]!='1') f.s[i]--;else f.s[i]='9';if(in(f.s)) qq.push(f);f.s[i]=t;if(i<3){f.s[i]=f.s[i+1];f.s[i+1]=t;if(in(f.s)) qq.push(f);f.s[i+1]=f.s[i];f.s[i]=t;}f.step--;//还原操作}}
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%s%s",a,b);ans=0;memset(vis,0,sizeof(vis));bfs();printf("%d\n",ans);}
}

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