【非图BFS+STL】电脑修好了—Open the Lock_HDU 1195
电脑折腾了三天总算修好了…C盘出现了一片bad sector…虽然以前写的ACM都没了，启动的也特别慢，但毕竟是修好了，于是又开始了。
涉足了一下自己最害怕的BFS（虽然这个对别人来说是弱智级别的），非图的+STL。
大意是一个四位密码锁，有两种方式，都算一步：
1、前后的+1和-1.
2、相邻两个调换顺序.
从一个密码到目标密码需要几步。
加上个STACK，跌跌撞撞的卡TIME AC了。。。据说网上说二分BFS更好，但是不会……ORZ
#include <iostream>#include <stdlib.h>#include <queue>#include <string>using namespace std;class passwd{public:int num[4];int step;};bool visited[10][10][10][10];int flag;void BFS(passwd initer,passwd traget){memset(visited,0,sizeof(visited));queue<passwd> q;passwd start=initer;passwd end;start.step=0;q.push(start);visited[start.num[0]][start.num[1]][start.num[2]][start.num[3]]=true;while(!q.empty()){start=q.front();q.pop();int tg=0;for(int a=0;a<4;a++){if(start.num[a]==traget.num[a]){tg++;}}if(tg==4){cout<<start.step<<endl;return;}//+1开搜for(int i=0;i<4;i++){end=start;if(start.num[i]==9){end.num[i]=1;}else{end.num[i]=start.num[i]+1;}if(visited[end.num[0]][end.num[1]][end.num[2]][end.num[3]]==0){visited[end.num[0]][end.num[1]][end.num[2]][end.num[3]]=1;end.step=start.step+1;q.push(end);}} //-1开搜for(int i=0;i<4;i++){end=start;if(start.num[i]==1){end.num[i]=9;}else{end.num[i]=start.num[i]-1;}if(visited[end.num[0]][end.num[1]][end.num[2]][end.num[3]]==0){visited[end.num[0]][end.num[1]][end.num[2]][end.num[3]]=1;end.step=start.step+1;q.push(end);}} //交换开搜for(int i=0;i<3;i++){end=start;end.num[i]=start.num[i+1];end.num[i+1]=start.num[i];if(visited[end.num[0]][end.num[1]][end.num[2]][end.num[3]]==0){visited[end.num[0]][end.num[1]][end.num[2]][end.num[3]]=1;end.step=start.step+1;q.push(end);}} //搜完了偶也~ }}int main(){string startstr,endstr;passwd c1,c2;int testcase;cin>>testcase;for(int j=0;j<testcase;j++){cin>>startstr>>endstr;for(int i=0;i<4;i++){c1.num[i]=startstr[i]-'0';c2.num[i]=endstr[i]-'0';c1.step=0;c2.step=0;}BFS(c1,c2);}return 0;}