另外，小明的密码箱很奇怪，只有四位数，上面的数字只有1到9，每次只能让每位数加1或者减1。按常识我们可以知道从1到9只需要减1，从9到1只需要加1。此外，你还能交换相邻的两个数字。如1234可以在一步后变成2134，但不能变成4231。
接下来T行，每行有两个整数（都是四位数），第一个是初状态，第二个是目标状态。
样例输入
2
1234 2144
1111 9999
样例输出
2
4
另外，这个题用DFS也是可以写出来的（而且用时很少），渣了，还不理解。。。
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; const int N=10; int vis[N][N][N][N],ans; struct Node { int num[4]; int cnt; } a,b,que[20005]; Node gb(Node p,int x) { p.cnt++; if(x<4)///+1 { if(p.num[x]==9) p.num[x]=1; else p.num[x]++; } else if(x<8)///-1 { x=x%4;///注意取模，因为结构体中的数组num大小为4 if(p.num[x]==1) p.num[x]=9; else p.num[x]--; } else if(x<11)///交换 { x=x%4;///同上 int t=p.num[x]; p.num[x]=p.num[x+1]; p.num[x+1]=t; } return p; } void bfs() { Node now,next; int front=1,rear=1; que[front]=a; vis[a.num[0]][a.num[1]][a.num[2]][a.num[3]]=1; while(front<=rear)///队列非空 { now=que[front];///取队头元素 if(now.num[0]==b.num[0]&&now.num[1]==b.num[1]&&now.num[2]==b.num[2]&&now.num[3]==b.num[3])///找到目标状态 { ans=now.cnt; return ; } for(int i=0; i<11; i++) { next=gb(now,i); if(vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]==0)///没有访问过 { vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1; rear++; que[rear]=next; } } front++;///删除队头元素 } } int main() { int t; char str1[10],str2[10]; //freopen("E:/in.txt","r",stdin); scanf("%d",&t); while(t--) { memset(vis,0,sizeof(vis)); scanf("%s%s",str1,str2); for(int i=0; i<4; i++) { a.num[i]=str1[i]-'0'; b.num[i]=str2[i]-'0'; } bfs(); printf("%d\n",ans); } return 0; }讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/27105.html