首页 > 代码库 > [HDU1195]Open the Lock
[HDU1195]Open the Lock
题目大意：给你一个4位数的初始状态（只包含1~9），要求你变化成另一个4位数。
变化规则为：每次可给任意一位加1或减1（1减1变为9,9加1变为1），或交换相邻两个数位上的数字（第一位和最后一位不相邻）。
要你求出最少的变化次数。
解题思路：这道题很明显是一道BFS的题，只不过变化的操作复杂了点。我使用了字符串进行处理。
一开始我用的是STL的string，后来我改成了C字符串，对比如下：
这充分说明了string的慢。。
操作虽然复杂，但耐心点还是能写好的。
具体见代码。
C++ Code:
#include<cstdio>#include<string.h>#include<stdlib.h>using namespace std;char n[5],m[5];struct sss{ int a; char s[5];};sss d[9002];bool b[10001];const int dd[]={1,-1};void bfs(){ int l=0,r=1; memset(b,0,sizeof(b)); d[1].a=0; strcpy(d[1].s,n); while(l!=r){ l=l%9000+1; for(int i=0;i<4;i++) for(int j=0;j<3;j++) if(j!=2){ char c[5]; strcpy(c,d[l].s); c[i]+=dd[j]; if(c[i]==‘0‘)c[i]=‘9‘; if(c[i]>‘9‘)c[i]=‘1‘; int f=atoi(c); if(!b[f]){ b[f]=1; r=r%9000+1; strcpy(d[r].s,c); d[r].a=d[l].a+1; if(strcmp(c,m)==0){ printf("%d\n",d[r].a); return; } } }else{ for(int k=0;k<=2;k++){ char c[5]; strcpy(c,d[l].s); char f=c[k]; c[k]=c[k+1]; c[k+1]=f; int ll=atoi(c); if(!b[ll]){ b[ll]=1; r=r%9000+1; strcpy(d[r].s,c); d[r].a=d[l].a+1; if(strcmp(c,m)==0){ printf("%d\n",d[r].a); return; } } } } }}int main(){ int o; scanf("%d",&o); while(o--){ scanf("%s",n); scanf("%s",m); if(strcmp(n,m)==0){ puts("0"); continue; } bfs(); }}
[HDU1195]Open the Lock
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。