bfs ZOJ 2416 Open the Lock
时间：2010-09-09 来源：sysuwhj
第一次写DFS，这题不难，基本照着今早找到那个程序的思路敲出来的，但是搞了好久才AC掉， 一开始就超时， 到后来就WA，纳闷了很久
DFS主要就是
有个flag数组，储存所有可能状态，标记是否查找过
设定好操作集，对数据进行的操作
一般思路就是
开始有一个Queue, 对现在的每一个状态的所有可能不断地push进队列， 再检查， 直到找到答案
经验：
C++里面那个string对象作为参数传入时，不是引用的，而是副本，这点和java不同，java除了基本类型外，所有对象都是引用
每次bfs前， 先清理Queue，以防上次留下的数据导致出错
Open the Lock
Open the Lock
1 #include <iostream>
2 #include <string>
3 #include <queue>
4 using namespace std;
5
6 struct node
7 {
8 string a;
9 int step;
10 };
11 //标记数组，题目中有1111~9999这么多个数，用这些数作为下标
12 int flag[10000] = {0};
13 node N,P;
14 string c, b;
15 queue<node>Q;
16 //题目中有三种操作，+，—，交换
17 string adddigit(string , int );
18 string minusdigit(string , int );
19 string changedigit(string , int );
20
21 void bfs();
22
23 int main()
24 {
25 int num;
26 cin >> num;
27 for (int i = 0; i < num; i++)
28 {
29 cin >> c >> b;
30
31 for (int i = 1111; i < 10000; i++)
32 flag[i] = 0;
33
34 bfs();
35 }
36 return 0;
37 }
38
39
40 void bfs()
41 {
42 N.a = c;N.step = 0;
43 //bfs前清空队列
44 while(!Q.empty())
45 Q.pop();
46
47 Q.push(N);
48 flag[atoi(N.a.c_str())] = 1;
49
50 while (!Q.empty())
51 {
52 N = Q.front();
53 Q.pop();
54
55 if (N.a == b)
56 break;
57
58 for (int j = 0; j < 4; j++)
59
60 for (int i = 0; i < 3; i++)
61 {
62 switch(i)
63 {
64 case 0:
65 P.a = adddigit(N.a, j);
66
67 if (!flag[atoi(P.a.c_str())])
68 {
69 P.step = N.step + 1;
70 Q.push(P);
71 flag[atoi(P.a.c_str())] = 1;
72 if (P.a == b)
73 {
74 cout << P.step << endl;;
75 return;
76 }
77 }
78 break;
79 case 1:
80
81 P.a = minusdigit(N.a, j);
82 if (!flag[atoi(P.a.c_str())])
83 {
84 P.step = N.step + 1;
85 Q.push(P);
86 flag[atoi(P.a.c_str())] = 1;
87 if (P.a == b)
88 {
89 cout << P.step << endl;;
90 return;
91 }
92 }
93
94 break;
95 case 2:
96 if (j != 3)
97 P.a = changedigit(N.a, j);
98 if (!flag[atoi(P.a.c_str())])
99 {
100 P.step = N.step + 1;
101 Q.push(P);
102 flag[atoi(P.a.c_str())] = 1;
103 if (P.a == b)
104 {
105 cout << P.step << endl;
106 return;
107 }
108 }
109
110 break;
111 }
112 }
113
114 }
115 cout << N.step << endl;
116
117 }
118 string adddigit(string a, int n)
119 {
120 if (a[n] == '9')
121 a[n] = '1';
122 else
123 a[n]++;
124 return a;
125 }
126
127 string minusdigit(string a, int n)
128 {
129 if (a[n] == '1')
130 a[n] = '9';
131 else
132 a[n]--;
133 return a;
134 }
135
136 string changepredigit(string a, int n)
137 {
138
139 string::value_type temp;
140 temp = a[n];
141 a[n] = a[n-1];
142 a[n-1] = temp;
143 return a;
144
145 }
146 string changedigit(string a, int n)
147 {
148
149
150 string::value_type temp;
151 temp = a[n];
152 a[n] = a[n+1];
153 a[n+1] = temp;
154 return a;
155
156 }
157
相关阅读 更多 +
排行榜 更多 +
