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 node
10 {
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         else
40         {
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
",flag);
96             getchar();
97         }
98     }
99 }