午夜的留言附属站

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
using namespace std;

map<pair<string,string>,int> h;
int calc(const pair<string,string> &input){
    if (input.first.compare(input.second)==0) return 0;
    if (h.count(input)) return h[input];

    int &res=h[input];
    res=-1;

    for (int i=0;i<input.first.size();i++){
        if (i&&input.first[i-1]!=input.second[i-1]) break;
        for (int j=input.first.size();j>i;j--){
            if (j<input.first.size()&&input.second[j]!=input.first[j]) break;
            pair<string,string> next(
                string(input.first.begin()+i,input.first.begin()+j),
                string(input.second.begin()+i,input.second.begin()+j));
            reverse(next.first.begin(),next.first.end());
            int tmp=calc(next);
            if (tmp==-1) continue;
            tmp++;
            if (res==-1||tmp<res) res=tmp;
        }
    }
    return res;
}

struct ReversalChain{
    int minReversal(string x,string y){
        h.clear();
        return calc(make_pair(x,y));
    }
};