题目大意：有一个紧急开启密码锁的任务。密码由四位数字组成；每个数字从1到9；每次，可以对每一个数字进行加1或者减1；当从1加到9时，由9再加1会变为1；当从9减到1时，由1再减1会变为9；也可以交换两个相邻的数字，每次操作作为一个step。你的任务就是用最少的步骤解锁！
先来分析一下这道题目： （别人分析的，我觉得分析的好，摘抄一下） 首先考虑1234的下一step有可能是什么样的数字 针对每一位数字有四种操作，+1，-1，左交换，右交换（最左边的数字只有右交换，最右边只有左交换） 那么下一step的数字 第一数字位：2234,9234,2134 第二数字位：1334,1134,2134,1324 第三数字位：1244,1224,1324,1243 第四数字位：1235,1233,1243
到这里我发现，其实这种搜索的方法就像一般显示图里的方向一样，只不过这里把方向改为方式（搞ACM还得脑子反映灵敏点）！真他妈巧妙。那分析到这里，这题就一清二楚了！
PS：搜索是一个博大精深的算法，尤其是其思想。熟练的掌握ACM搜索的三种方法对处理大多数问题都会得心应手！
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; #define init(a,what) memset(a,what,sizeof(a)) #define read freopen("zx.in","r",stdin) #define write freopen("zx.out","w",stdout) typedef struct { char buf[5]; int step; }ARR; ARR cur,xx; queue<ARR>q; char buf1[5],buf2[5]; bool vis[10][10][10][10]; void bfs() { init(vis,false); while(!q.empty()) q.pop(); strcpy(cur.buf,buf1); cur.step=0; vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']=true; q.push(cur); while(!q.empty()) { xx=q.front(); q.pop(); for(int i=0;i<4;i++) { strcpy(cur.buf,xx.buf); cur.step=0; if(cur.buf[i]=='9') cur.buf[i]='1'; else cur.buf[i]=xx.buf[i]+1; cur.step=xx.step+1; if(!vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']) { if(strcmp(cur.buf,buf2)==0) { printf("%d/n",cur.step); return ; } else { vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']=true; q.push(cur); } } strcpy(cur.buf,xx.buf); cur.step=0; if(cur.buf[i]=='1') cur.buf[i]='9'; else cur.buf[i]=xx.buf[i]-1; cur.step=xx.step+1; if(!vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']) { if(strcmp(cur.buf,buf2)==0) { printf("%d/n",cur.step); return ; } else { vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']=true; q.push(cur); } } if(i<3) { strcpy(cur.buf,xx.buf); cur.step=0; cur.buf[i]=xx.buf[i+1]; cur.buf[i+1]=xx.buf[i]; cur.step=xx.step+1; if(!vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']) { if(strcmp(cur.buf,buf2)==0) { printf("%d/n",cur.step); return ; } else { vis[cur.buf[0]-'0'][cur.buf[1]-'0'][cur.buf[2]-'0'][cur.buf[3]-'0']=true; q.push(cur); } } } } } } int main() { //read, write; int ncase; scanf("%d",&ncase); while(ncase--) { scanf("%s",buf1); scanf("%s",buf2); //printf("%s/n",buf1); printf("%s/n",buf2); if(strcmp(buf1,buf2)==0) printf("0/n"); else bfs(); } return 0; }
