題目：
http://acm.hdu.edu.cn/showproblem.php?pid=1195問題大意：有一個(gè)四位的數(shù)字，要用最少的變化次數(shù)將其變成目標(biāo)數(shù)字，變換方式三種，每次只能使用一種變換方式，對一位進(jìn)行操作。
算法大意：
1.和洋蔥同學(xué)討論之后， 直接把每一步的所有情況窮舉出來，因?yàn)槊恳徊綄?shí)際上只有11種方式而已，這樣之后，就有了一個(gè)新的狀態(tài)，然后在此狀態(tài)上繼續(xù)窮舉，直到達(dá)到目標(biāo)狀態(tài)。
2.利用BFS可以方便的遍歷到?jīng)]一步的所有狀態(tài)，把每一步新的狀態(tài)壓入隊(duì)列中。
3.記錄每一個(gè)新的狀態(tài)，當(dāng)下次遍歷到的時(shí)候，即可直接跳過。
源代碼：
1 /*
2 算法思想：利用BFS進(jìn)行窮舉。從一步窮舉到N步。
3 剪掉重復(fù)的很重要
4 catch 中有些設(shè)計(jì)上的失誤
5 */
6 #include<iostream>
7 #include<queue>
8 using namespace std;
9 int s[4],ds[4];
10
11
12 int BfsSearch(int vist[])
13 {
14 queue<int>q;
15 int tmp[5];
16 int step=0;
17
18 q.push(s[0]);
19 q.push(s[1]);
20 q.push(s[2]);
21 q.push(s[3]);
22 q.push(0);
23
24 while(!q.empty())
25 {
26 int a,b,c,d;
27
28 a=tmp[0]=q.front();
29 q.pop();
30 b=tmp[1]=q.front();
31 q.pop();
32 c=tmp[2]=q.front();
33 q.pop();
34 d=tmp[3]=q.front();
35 q.pop();
36 step=q.front();
37 q.pop();
38
39 for(int i=0;i<11;i++)
40 {
41 switch(i)
42 {
43 case 0:
44 {
45 if(tmp[0]>8) a=1;
46 else a++;
47 b=tmp[1];c=tmp[2];d=tmp[3];
48 }break;
49 case 1:
50 {
51 if(tmp[1]>8) b=1;
52 else b++;
53 a=tmp[0];c=tmp[2];d=tmp[3];
54 }break;
55 case 2:
56 {
57 if(tmp[2]>8) c=1;
58 else c++;
59 a=tmp[0];b=tmp[1];d=tmp[3];
60 }break;
61 case 3:
62 {
63 if(tmp[3]>8) d=1;
64 else d++;
65 a=tmp[0];b=tmp[1];c=tmp[2];
66 }break;
67 case 4:
68 {
69
70 if(tmp[0]<2) a=9;
71 else a--;
72 b=tmp[1];c=tmp[2];d=tmp[3];
73 }break;
74 case 5:
75 {
76 if(tmp[1]<2) b=9;
77 else b--;
78 a=tmp[0];c=tmp[2];d=tmp[3];
79 }break;
80 case 6:
81 {
82 if(tmp[2]<2) c=9;
83 else c--;
84 a=tmp[0];b=tmp[1];d=tmp[3];
85 }break;
86 case 7:
87 {
88 if(tmp[3]<2) d=9;
89 else d--;
90 a=tmp[0];b=tmp[1];c=tmp[2];
91 }break;
92 case 8:
93 {
94 int t;
95 a=tmp[0];
96 b=tmp[1];
97 c=tmp[2];
98 d=tmp[3];
99 if(a==b) continue;
100 t=a;
101 a=b;
102 b=t;
103 }break;
104 case 9:
105 {
106 int t;
107 a=tmp[0];
108 b=tmp[1];
109 c=tmp[2];
110 d=tmp[3];
111
112 if(b==c) continue;
113 t=b;
114 b=c;
115 c=t;
116 }break;
117 case 10:
118 {
119 int t;
120 a=tmp[0];
121 b=tmp[1];
122 c=tmp[2];
123 d=tmp[3];
124
125 if(c==d) continue;
126 t=c;
127 c=d;
128 d=t;
129 }break;
130 }//switch
131
132
133 if(a==ds[0]&&b==ds[1]&&c==ds[2]&&d==ds[3])
134 {
135 return step+1;
136 }
137
138 if(vist[d+c*10+b*100+a*1000])//如果重復(fù)則不壓入隊(duì)列 很重要
139 {
140 continue;
141 }
142 else
143 {
144
145 vist[d+c*10+b*100+a*1000]=1;
146 q.push(a);
147 q.push(b);
148 q.push(c);
149 q.push(d);
150 q.push(step+1);
151 }//else
152
153 }//for
154
155 }//while
156
157 }//bfs
158
159 int main()
160 {
161
162 int t,k;
163 int m,n;
164 cin>>t;
165 while(t--)
166 {
167 int vist[10000]={0};
168 cin>>m>>n;
169 s[0]=m/1000;
170 s[1]=m/100%10;
171 s[2]=m/10%10;
172 s[3]=m%10;
173
174 ds[0]=n/1000;
175 ds[1]=n/100%10;
176 ds[2]=n/10%10;
177 ds[3]=n%10;
178
179 k=BfsSearch(vist);
180 cout<<k<<endl;
181 }
182
183
184 return 0;
185 }
個(gè)人體會：BFS的應(yīng)用真是神奇。