Sicily 1150: 简单魔板（BFS）

　　此题可以使用BFS进行解答，使用8位的十进制数来储存魔板的状态，用BFS进行搜索即可
  1 #include <bits/stdc++.h> 
  2 using namespace std;
  3 
  4 int op_a(int n) {//操作A（上下行互换）
  5     int low = n % 10000;
  6     int high = n / 10000;
  7     return low * 10000 + high;
  8 }
  9 
 10 int op_b(int n) {//操作B（每次以行循环右移一个）
 11     int low = n % 10000;
 12     int high = n / 10000;
 13     int h = high % 10;
 14     high = h * 1000 + high / 10;
 15     int l = low % 10;
 16     low = l * 1000 + low / 10;
 17     return high * 10000 + low;
 18 }
 19 
 20 int op_c(int n) {//操作C（中间四小块顺时针转一格）
 21     int a[8];
 22     for (int i = 0; i < 8; i++) {
 23         a[7-i] = n % 10;
 24         n = n / 10;
 25     }
 26     int ans =   a[0] * 10000000 +
 27                 a[5] * 1000000 +
 28                 a[1] * 100000 +
 29                 a[3] * 10000 +
 30                 a[4] * 1000 +
 31                 a[6] * 100 +
 32                 a[2] * 10 +
 33                 a[7];
 34     return ans;
 35 }
 36 struct Node {
 37     int num;//num储存状态，用8位的十进制数来储存状态 
 38     vector<char> path;//path储存操作 
 39 };
 40 Node bfs(int step, int n) {
 41     queue<Node> q;
 42     Node front;
 43     front.num = 12348765;//初始的魔板 
 44     q.push(front);
 45     while (!q.empty()) {
 46         front = q.front();
 47         q.pop();
 48         if (front.path.size() > step) {
 49             return front;//如果操作的次数大于step数，返回 
 50         }
 51         //依次进行三种操作 
 52         Node tmp1 = front;
 53         tmp1.num = op_a(front.num);
 54         tmp1.path.push_back('A');
 55         if (tmp1.num == n) {
 56             return tmp1;//如果得到目标状态则返回 
 57         }
 58         else {
 59             q.push(tmp1);
 60         }
 61 
 62         Node tmp2 = front;
 63         tmp2.num = op_b(front.num);
 64         tmp2.path.push_back('B');
 65         if (tmp2.num == n) {
 66             return tmp2;//如果得到目标状态则返回 
 67         }
 68         else {
 69             q.push(tmp2);
 70         }
 71 
 72         Node tmp3 = front;
 73         tmp3.num = op_c(front.num);
 74         tmp3.path.push_back('C');
 75         if (tmp3.num == n) {
 76             return tmp3;//如果得到目标状态则返回 
 77         }
 78         else {
 79             q.push(tmp3);
 80         }
 81 
 82     }
 83 }
 84 int main(){
 85     int step;
 86     while (cin >> step && step != -1) {
 87         int ans = 0; 
 88         int a;
 89         for (int i = 0; i < 8; i++) {//将魔板转换成数字 
 90             cin >> a;
 91             ans = 10 * ans + a;
 92         } 
 93         Node node = bfs(step, ans);
 94         if (node.path.size() > step) cout << "-1" << endl;//如失败则输出-1，否则输出path 
 95         else {
 96             cout << node.path.size() << ' ';
 97             for (int i = 0; i < node.path.size(); i++) {
 98                 cout << node.path[i];
 99             }
100             cout << endl;
101         }
102         
103     }
104     return 0;
105 }