uva 704

  1 // Colour Hash （色彩缤纷游戏）
  2 // PC/UVa IDs: 110807/704, Popularity: B, Success rate: average Level: 3
  3 // Verdict: Accepted
  4 // Submission Date: 2011-08-28
  5 // UVa Run Time: 0.048s
  6 //
  7 // 版权所有（C）2011，邱秋。metaphysis # yeah dot net
  8 //
  9 // 若从给定状态进行单向搜索，由于状态较多，容易 TLE，故采用双向搜索的办法，逆向搜索：从目标状态
 10 // 搜索 8 步，把所有得到的结果记录在集合 A 中；正向搜索：从给定状态搜索 9 步，若在搜索过程中生成
 11 // 的某个状态在集合 A 中，则表明在 16 步内能找到解，否则无法找到解。
 12 //
 13 // 这里较为关键的是如何表示游戏的当前状态，以避免在集合 A 中添加重复的状态，可以使用字符串来表示
 14 // 当前的滑块状态。集合 A 可以使用 map 来判断是否已经有重复的状态产生。
 15 
 16 #include <iostream>
 17 #include <queue>
 18 #include <map>
 19 
 20 using namespace std;
 21 
 22 #define LEFT_CLOCKWISE 1        // 左侧顺时针。
 23 #define RIGHT_CLOCKWISE 2        // 右侧顺时针。
 24 #define LEFT_COUNTERCLOCKWISE 3        // 左侧逆时针。
 25 #define RIGHT_COUNTERCLOCKWISE 4    // 右侧逆时针。
 26 
 27 #define NWHEEL 24        // 滑块总数目。
 28 #define HALF_WHEEL 9        // 左侧滑块的数目。
 29 #define MIDDLE_WHEEL 3        // 中间滑块的数目。
 30 #define BACKWARD_DEPTH 8    // 逆向搜索深度。
 31 
 32 // 目标状态。存储方式为左侧滑块-右侧滑块-中间滑块，因为编号为 10 的滑块占两个字符，故用 10 的英
 33 // 文（ten）首字母 T 来表示。
 34 string target = "034305650078709T90121";
 35 
 36 // 逆向搜索的缓存，使用字符串来表示状态和旋转序列。
 37 map < string, string > cache;
 38 
 39 // 旋转操作的逆。1 的逆为 3，2 的逆为 4，依此类推。
 40 int reverse[4] = { 3, 4, 1, 2 };
 41 
 42 // 表示滑块当前状态的结构。
 43 struct node
 44 {
 45     string config;        // 滑块状态。
 46     string sequences;    // 到达此位置的旋转序列。
 47 };
 48 
 49 // 按指定的方向旋转滑块。
 50 void rotate(string &config, int direction)
 51 {
 52     // 获取中间滑块部分。
 53     string middle = config.substr(HALF_WHEEL * 2);
 54 
 55     switch (direction)
 56     {
 57             // 左侧滑块顺时针旋转。
 58         case LEFT_CLOCKWISE:
 59 
 60             config[HALF_WHEEL * 2] = config[HALF_WHEEL - 2];
 61             config[HALF_WHEEL * 2 + 1] = config[HALF_WHEEL - 1];
 62             config[HALF_WHEEL * 2 + 2] = middle[0];
 63 
 64             for (int i = HALF_WHEEL - 1; i >= 2; i--)
 65                 config[i] = config[i - 2];
 66             config[1] = middle[2];
 67             config[0] = middle[1];
 68 
 69             break;
 70 
 71             // 右侧滑块顺时针旋转。
 72         case RIGHT_CLOCKWISE:
 73 
 74             config[HALF_WHEEL * 2] = middle[2];
 75             config[HALF_WHEEL * 2 + 1] = config[HALF_WHEEL];
 76             config[HALF_WHEEL * 2 + 2] = config[HALF_WHEEL + 1];
 77 
 78             for (int i = HALF_WHEEL; i <= (HALF_WHEEL * 2 - 3); i++)
 79                 config[i] = config[i + 2];
 80             config[HALF_WHEEL * 2 - 2] = middle[0];
 81             config[HALF_WHEEL * 2 - 1] = middle[1];
 82 
 83             break;
 84 
 85             // 左侧滑块逆时针旋转。
 86         case LEFT_COUNTERCLOCKWISE:
 87 
 88             config[HALF_WHEEL * 2] = middle[2];
 89             config[HALF_WHEEL * 2 + 1] = config[0];
 90             config[HALF_WHEEL * 2 + 2] = config[1];
 91 
 92             for (int i = 0; i <= HALF_WHEEL - 3; i++)
 93                 config[i] = config[i + 2];
 94             config[HALF_WHEEL - 2] = middle[0];
 95             config[HALF_WHEEL - 1] = middle[1];
 96 
 97             break;
 98 
 99             // 右侧滑块逆时针旋转。
100         case RIGHT_COUNTERCLOCKWISE:
101 
102             config[HALF_WHEEL * 2] = config[HALF_WHEEL * 2 - 2];
103             config[HALF_WHEEL * 2 + 1] = config[HALF_WHEEL * 2 - 1];
104             config[HALF_WHEEL * 2 + 2] = middle[0];
105 
106             for (int i = 2 * HALF_WHEEL - 1; i >= HALF_WHEEL + 2; i--)
107                 config[i] = config[i - 2];
108             config[HALF_WHEEL + 1] = middle[2];
109             config[HALF_WHEEL] = middle[1];
110 
111             break;
112     }
113 }
114 
115 // 从目标状态生成 8 步内所有可能产生的状态，使用宽度优先搜索的方法，用 map 存储生成的状态和相应
116 // 的旋转序列。
117 void backward_search(string config)
118 {
119     queue <node> open;
120 
121     node tmp;
122     tmp.config = config;
123     tmp.sequences = "";
124 
125     open.push(tmp);
126 
127     while (!open.empty())
128     {
129         node copy = open.front();
130         open.pop();
131 
132         // 当扩展的深度达到 8 层后停止在此状态上继续扩展。
133         if (copy.sequences.length() >= BACKWARD_DEPTH)
134             continue;
135 
136         for (int i = LEFT_CLOCKWISE; i <= RIGHT_COUNTERCLOCKWISE; i++)
137         {
138             // 跳过无效的移动，例如前一步采用了左侧顺时针旋转，则当前若使用
139             // 左侧逆时针旋转会回到上一步的状态。
140             if (copy.sequences.length() > 0)
141             {
142                 // 注意使用的是旋转操作的逆，故需还原后判断。
143                 int last_rotate = reverse[copy.sequences[0] - ‘0‘ - 1];
144                 if (last_rotate != i && ((last_rotate + i) == 4 ||
145                                                                 (last_rotate + i) == 6))
146                     continue;
147             }
148 
149             string t = copy.config;
150             rotate(t, i);
151 
152             if (cache.find(t) == cache.end())
153             {
154                 node successor;
155                 successor.config = t;
156                 // 记录逆向搜索的旋转序列时，使用当前旋转的逆。
157                 successor.sequences = (char)(‘0‘ + reverse[i - 1]) + copy.sequences;
158                 open.push(successor);
159 
160                 cache.insert(make_pair<string, string>(t, successor.sequences));
161             }
162         }
163     }
164 }
165 
166 // 进行正向搜索，采用宽度优先搜索模式。
167 bool forward_search(string config)
168 {
169     queue <node> open;
170 
171     node tmp;
172     tmp.config = config;
173     tmp.sequences = "";
174 
175     open.push(tmp);
176 
177     while (!open.empty())
178     {
179         node copy = open.front();
180         open.pop();
181 
182         // 已经找到在缓存中的状态，输出旋转序列。
183         if (cache.find(copy.config) != cache.end())
184         {
185             cout << copy.sequences;
186             map <string, string>::iterator it = cache.find(copy.config);
187             cout << (*it).second << endl;
188 
189             return true;
190         }
191 
192         // 搜索深度为 9。
193         if (copy.sequences.length() >= (BACKWARD_DEPTH + 1))
194             continue;
195             
196         for (int i = LEFT_CLOCKWISE; i <= RIGHT_COUNTERCLOCKWISE; i++)
197         {
198             // 若前后两步构成互补状态则跳过。
199             if (copy.sequences.length() > 0)
200             {
201                 int size = copy.sequences.length();
202                 int last_rotate = copy.sequences[size - 1] - ‘0‘;
203                 if (last_rotate != i && ((last_rotate + i) == 4 ||
204                                                                 (last_rotate + i) == 6))
205                     continue;
206             }
207 
208             string t = copy.config;
209             rotate(t, i);
210 
211             node successor;
212             successor.config = t;
213             successor.sequences = copy.sequences + (char)(‘0‘ + i);
214 
215             open.push(successor);
216         }
217     }
218 
219     return false;
220 }
221 
222 // 和目标状态比较，确定是否为已解决状态。
223 bool solved(string config)
224 {
225     for (int i = 0; i < target.length(); i++)
226         if (config[i] != target[i])
227             return false;
228 
229     return true;
230 }
231 
232 int main(int ac, char *av[])
233 {
234     string config;
235     int c;
236     int cases;
237     
238     // 先生成逆向搜索的结果以备查。
239     backward_search(target);
240     
241     cin >> cases;
242     while (cases--)
243     {
244         // 读入初始状态。
245         config.clear();
246         for (int i = 0; i < NWHEEL; i++)
247         {
248             cin >> c;
249             if (c == 10)
250                 config.append(1, ‘T‘);
251             else
252                 config.append(1, c + ‘0‘);
253         }
254 
255         // 调整表示形式。
256         config = config.substr(0, HALF_WHEEL) +
257             config.substr(HALF_WHEEL + MIDDLE_WHEEL, HALF_WHEEL) +
258             config.substr(2 * HALF_WHEEL + MIDDLE_WHEEL);
259         
260         // 先判断是否已经为解决状态。
261         if (solved(config))
262         {
263             cout << "PUZZLE ALREADY SOLVED" << endl;
264             continue;
265         }
266 
267         // 进行正向搜索查找。
268         if (!forward_search(config))
269             cout << "NO SOLUTION WAS FOUND IN 16 STEPS" << endl;
270     }
271 
272     return 0;
273 }