现在一个紧急的任务是打开一个密码锁。密码由四位数字组成，每个数字从 1 到 9 进行编号。每次可以对任何一位数字加 1 或减 1。当将9加 1 时，数字将变为1，当1减 1 的时，数字将变为9。你也可以交换相邻数字，每一个行动记做一步。现在你的任务是使用最小的步骤来打开锁。注意：最左边的数字不与最右边的数字相邻。
输入格式
第一行输入四位数字，表示密码锁的初始状态。
第二行输入四位数字，表示开锁的密码。
输出格式
输出一个整数，表示最小步骤。
样例输入
1234 2144
样例输出:
2
#include <iostream> #include <stdio.h> #include <queue> using namespace std; char chushi[10],mima[10]; struct node{ int num[4]; //记录四个锁的数字 int d; //步数 }; bool c[10][10][10][10]; queue<node> a; //建立队列 node first,last,next; void bfs(){ first.d=0; a.push(first); //把初始状态压入队列中 c[first.num[0]][first.num[1]][first.num[2]][first.num[3]]=1; //标记已经搜索过 while(!a.empty()){ node now=a.front(); //获得队列首 a.pop(); //弹出队列首 if(now.num[0]==last.num[0] && now.num[1]==last.num[1] && now.num[3]== last.num[3] && now.num[2]==last.num[2]){ printf("%d",now.d); //判断锁是否打开 return; } for(int i=0;i<4;i++){ next=now; if(next.num[i]+1==10){ //把四个小锁，每个加一状态分别便利 next.num[i]=1; }else{ next.num[i]+=1; } if(!c[next.num[0]][next.num[1]][next.num[2]][next.num[3]]){ c[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1; next.d++; a.push(next); } } for(int i=0;i<4;i++){ //把四个小锁，减一 next=now; if(next.num[i]-1==0){ next.num[i]=9; }else{ next.num[i]-=1; } if(!c[next.num[0]][next.num[1]][next.num[2]][next.num[3]]){ c[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1; next.d++; a.push(next); } } for(int i=0;i<3;i++){ //相邻交换 next=now; next.num[i]=now.num[i+1]; next.num[i+1]=now.num[i]; if(!c[next.num[0]][next.num[1]][next.num[2]][next.num[3]]){ next.d++; a.push(next); } } } } int main(){ scanf("%s",chushi); //输入字符 scanf("%s",mima); for(int i=0;i<4;i++){ first.num[i]=chushi[i]-'0'; //把每个字符转为int存储在结构体中 last.num[i]=mima[i]-'0'; } bfs(); return 0; }
