首页 > 代码库 > hdu 1195 Open the Lock
hdu 1195 Open the Lock
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1195
题目大意:密码解锁,有两种方式:第一,拨动密码;第一,调换相邻密码的位置。以这两种方式找到最少次数的解锁次数!
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 using namespace std; 6 char ch[10],str[10]; 7 int dir[2]= {1,-1},flag,vis[15][15][15][15]; 8 9 struct node10 {11 int x[5];12 int time;13 } ;14 15 void bfs()16 {17 queue<node>q;18 node s;19 for (int i=0; i<4; i++)20 s.x[i]=ch[i]-‘0‘;21 s.time=0;22 q.push(s);23 vis[s.x[0]][s.x[1]][s.x[2]][s.x[3]]=1;24 while (!q.empty())25 {26 //cout<<s.x[0]<<s.x[1]<<s.x[2]<<s.x[3]<<" ";27 //cout<<s.time<<" ";28 s=q.front();29 q.pop();30 int temp=0;31 for (int i=0; i<4; i++)32 if (s.x[i]==str[i]-‘0‘)33 temp+=1;34 if (temp==4)35 {36 flag=s.time;37 return ;38 }39 else40 {41 42 for(int i=0; i<4; i++)43 {44 for(int j=0; j<2; j++)45 {46 node ss=s;47 ss.x[i]+=dir[j];48 if (ss.x[i]==10)49 ss.x[i]=1;50 else if (ss.x[i]==0)51 ss.x[i]=9;52 if(!vis[ss.x[0]][ss.x[1]][ss.x[2]][ss.x[3]])53 {54 ss.time++;55 vis[ss.x[0]][ss.x[1]][ss.x[2]][ss.x[3]]=1;56 q.push(ss);//cout<<s.time<<endl;57 }58 }59 }60 for(int i=0; i<3; i++)61 {62 node ss=s;63 int ans=ss.x[i];64 ss.x[i]=ss.x[i+1];65 ss.x[i+1]=ans;66 if(!vis[ss.x[0]][ss.x[1]][ss.x[2]][ss.x[3]])67 {68 ss.time++;69 vis[ss.x[0]][ss.x[1]][ss.x[2]][ss.x[3]]=1;70 q.push(ss);71 }72 }73 74 }75 76 }77 }78 int main ()79 {80 int t;81 while (cin>>t)82 {83 while (t--)84 {85 flag=-1;86 memset(vis,0,sizeof(vis));87 getchar();88 for (int i=0; i<4; i++)89 scanf("%c",&ch[i]);90 getchar();91 for (int j=0; j<4; j++)92 scanf ("%c",&str[j]);93 bfs();94 if (flag>-1)95 printf ("%d\n",flag);96 getchar();97 }98 }99 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。