Posted on 2009-05-18 00:16
superman 阅读(240)
评论(0) 编辑 收藏 引用 所属分类:
USACO
1 #include <map>
2 #include <queue>
3 #include <iostream>
4
5 using namespace std;
6
7 int init_state, target_state;
8
9 void get_init_and_target_state()
10 {
11 init_state = 12345678;
12 for (int i = 0, x, t = 10000000; i < 8; i++, t /= 10)
13 {
14 cin >> x;
15 target_state += x * t;
16 }
17 }
18
19 map<int, string> stateMap;
20
21 int main()
22 {
23 freopen("msquare.in", "r", stdin);
24 freopen("msquare.out", "w", stdout);
25
26 get_init_and_target_state();
27
28 queue<int> q;
29 q.push(init_state);
30 stateMap.insert(make_pair(init_state, ""));
31
32 while (q.empty() == false)
33 {
34 int cur = q.front(); q.pop();
35
36 if (cur == target_state)
37 {
38 cout << stateMap.find(cur)->second.size() << endl;
39 cout << stateMap.find(cur)->second << endl;
40 return 0;
41 }
42
43 int x[10] = { 0 };
44 for (int i = 8, t = cur; t; i--, t /= 10)
45 x[i] = t % 10;
46
47 int na = x[8] * 10000000 + x[7] * 1000000 + x[6] * 100000 +
48 x[5] * 10000 + x[4] * 1000 + x[3] * 100 + x[2] * 10 + x[1];
49
50 int nb = x[4] * 10000000 + x[1] * 1000000 + x[2] * 100000 +
51 x[3] * 10000 + x[6] * 1000 + x[7] * 100 + x[8] * 10 + x[5];
52
53 int nc = x[1] * 10000000 + x[7] * 1000000 + x[2] * 100000 +
54 x[4] * 10000 + x[5] * 1000 + x[3] * 100 + x[6] * 10 + x[8];
55
56 map<int, string>::iterator it;
57 if ((it = stateMap.find(na)) == stateMap.end())
58 {
59 it = stateMap.find(cur);
60 stateMap.insert(make_pair(na, it->second + 'A'));
61 q.push(na);
62 }
63 if ((it = stateMap.find(nb)) == stateMap.end())
64 {
65 it = stateMap.find(cur);
66 stateMap.insert(make_pair(nb, it->second + 'B'));
67 q.push(nb);
68 }
69 if ((it = stateMap.find(nc)) == stateMap.end())
70 {
71 it = stateMap.find(cur);
72 stateMap.insert(make_pair(nc, it->second + 'C'));
73 q.push(nc);
74 }
75 }
76
77 return 0;
78 }
79