1 条题解
-
1
#include<queue> #include<cstdio> #include<cstring> using namespace std; short vis[1000000][7][2]; struct node{ int now; int stp,pos; //pos: 当前光标位置 bool flag; }S,B,f,tmp; queue<node>q; const int ws[]={1000000,100000,10000,1000,100,10,1}; inline int UpOrDown(int num,int pos,int chg){ int t=num/ws[pos]%10+chg; if(t>=0&&t<=9) return num/ws[pos-1]*ws[pos-1]+t*ws[pos]+num%ws[pos]; return num; } inline int Swap(int num,int pos,int chg){ int bg=num/ws[pos]%10; int ed=num/ws[chg]%10; if(bg==ed)return num; num=num/ws[pos-1]*ws[pos-1]+ed*ws[pos]+num%ws[pos]; num=num/ws[chg-1]*ws[chg-1]+bg*ws[chg]+num%ws[chg]; return num; } int TWBFS(void){ //TIANWEN BFS(bushi) while(!q.empty()){ tmp=f=q.front(); tmp.stp++; q.pop(); if(~vis[f.now][f.pos][!f.flag]) return f.stp+vis[f.now][f.pos][!f.flag]; //将光标左移一位 if(f.pos>1){ tmp.pos=f.pos-1; if(vis[tmp.now][tmp.pos][tmp.flag]==-1){ vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp; q.push(tmp); } } //将光标右移一位 if(f.pos<6){ tmp.pos=f.pos+1; if(vis[tmp.now][tmp.pos][tmp.flag]==-1){ vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp; q.push(tmp); } } //记得把光标移回来,不要像本蒟蒻一样傻傻踩坑 tmp.pos=f.pos; //将光标所在位置的数值增加1 tmp.now=UpOrDown(f.now,f.pos,1); if(vis[tmp.now][tmp.pos][tmp.flag]==-1){ vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp; q.push(tmp); } //将光标所在位置的数值减少1 tmp.now=UpOrDown(f.now,f.pos,-1); if(vis[tmp.now][tmp.pos][tmp.flag]==-1){ vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp; q.push(tmp); } //swap0 if(f.pos!=1){ tmp.now=Swap(f.now,f.pos,1); if(vis[tmp.now][tmp.pos][tmp.flag]==-1){ vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp; q.push(tmp); } } //swap1 if(f.now!=6){ tmp.now=Swap(f.now,f.pos,6); if(vis[tmp.now][tmp.pos][tmp.flag]==-1){ vis[tmp.now][tmp.pos][tmp.flag]=tmp.stp; q.push(tmp); } } } return 114514; } int main(){ scanf("%d%d",&S.now,&B.now); memset(vis,-1,sizeof(vis)); S.pos=1; q.push(S); B.flag=1; vis[S.now][1][0]=0; //最终密码的光标在每一位都有可能出现 for(int i=1;i<=6;++i){ B.pos=i; vis[B.now][i][1]=0; q.push(B); } printf("%d\n",TWBFS()); return 0; }
- 1
信息
- ID
- 913
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者