洛谷P2730 [USACO3.2]魔板 Magic Squares

题目链接：点这里

一般这种从某种状态转移到目标状态的最短距离，都可以使用BFS来做。

从题目给定的初始状态，依次执行题目给定的三种操作，分别是交换上下两行（操作A)、将最后一列插入到第一列的前面（操作B)、将中间的矩形按照顺时针旋转90度（操作C)，将这些操作存到哈希表里，由BFS的特点可知，我们如果到达了目标状态，那么操作次数一定是最小的；在这道题目里，又由于我们是按照字典序来依次执行三个操作的，所以得到的第一个可行解一定是字典序最小的。

题目还要求输出操作的顺序，我们再用一个哈希表存储当前状态是哪个状态经历了一系列操作之后得到的，比如当前状态是12345678，它的上一个状态是56784321，那么当前状态就是由初始状态经过操作A后得到的，如果上一个状态是由初始状态经过*****操作得到的，那么当前状态的操作就是上一个状态加上A，就是*****A。

注意如果初始状态就是基本状态的话，有可能会多输出一个空行，因此特判一下即可。

#include <iostream>
#include <unordered_map>
#include <queue>
#include <algorithm>
using namespace std;

const int N = 100010;

string res;

int bfs(string ed) {
    string st = "12345678";
    queue<string> q;
    unordered_map<string, int> h;
    unordered_map<string, string> kept;
    q.push(st);
    h[st] = 0;
    kept[st] = "";
    while(q.size()) {
        auto t = q.front();
        q.pop();
        
        int last = h[t];
        string ls = t;
        if(t == ed) {
            res = kept[t];
            return last;
        }
        
        //操作A
        reverse(t.begin(), t.end());
        if(!h.count(t)) {
            q.push(t), h[t] = last + 1;
            kept[t] = kept[ls] + 'A';
        }
        //变回t，就像‘作案之后还原现场’
        reverse(t.begin(), t.end());
        
        //操作B
        for(int i = 3; i > 0; i--) swap(t[i], t[i - 1]);
        for(int i = 4; i < 7; i++) swap(t[i], t[i + 1]);
        if(!h.count(t)) {
             q.push(t), h[t] = last + 1;
             kept[t] = kept[ls] + 'B';
        }
        //变回t
        for(int i = 0; i < 3; i++) swap(t[i], t[i + 1]);
        for(int i = 7; i > 4; i--) swap(t[i], t[i - 1]);
        
        //操作C
        swap(t[1], t[6]), swap(t[6], t[2]), swap(t[6], t[5]);
        if(!h.count(t)) {
            q.push(t), h[t] = last + 1, res += 'C';
            kept[t] = kept[ls] + 'C';
        }
        //变回t
        swap(t[6], t[5]), swap(t[6], t[2]), swap(t[6], t[1]);
    }
    return -1;
}

int main() {
    string ed = "";
    for(int i = 0; i < 8; i++) {
        int x;
        cin >> x;
        ed += x + '0';
    }    
    int t = bfs(ed);
    cout << t << endl;
    if(t)
        cout << res << endl;
    return 0;
}