-

算法

双向bfs，最后还是加了y总的ida*的剪枝优化，不加会卡tle，也许是我的思路还是有问题,不过这样感觉就不是双向bfs了，而是暴搜得到的。

C++ 代码

#include<iostream>
#include<unordered_map>b
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

string st, ed;
string source = "ABCDEFGHIJKLMNOPQRST";
int n;
int f(string s){
    int tot = 0;
    for(int i = 0; i + 1 < n; i ++){
        if(s[i + 1] != s[i] + 1 )tot ++;
    }
    return (tot + 2) / 3;
}
string bfs(){
    unordered_map<string, int> d[2];
    queue<string> qu[2];
    d[0][st] = 0;
    d[1][ed] = 0;
    qu[0].push(st);
    qu[1].push(ed);

    while(qu[0].size() && qu[1].size()){
        int p = qu[0].size() > qu[1].size();
        if(d[p][qu[p].front()] >= 4) break; //这个是因为两边都是一层一层的推进的，如果这边是4， 另一边至少是1了，不过我试了>= 3也可以过
        int size = qu[p].size();

        int dis = d[p][qu[p].front()];
        for(int i = 0; i < size;  i ++){
            string  s =  qu[p].front();
            string backup = s;
            qu[p].pop();
            if(dis + f(s) >= 5) continue;
            for(int len = n - 1;  len >= 1   ; len --)
                for(int l = 0; l + len - 1 < n; l ++){
                    int r = l + len - 1;
                    for(int k = r + 1; k < n; k ++){
                        int y = l;
                        for(int x = r + 1; x <= k; x ++, y ++)s[y] = backup[x]; 
                        for(int x = l;  x <= r; x ++, y ++)s[y] = backup[x];
                        if(d[p].count(s)) continue;
                        d[p][s] =  dis + 1;
                        if(d[1 ^ p].count(s)) { 
                            int cnt =  d[1 ^ p][s] + d[p][s];
                            // cout << d[1 ^ p][s] << " " << d[p][s] << endl;
                            return cnt >= 5 ? "5 or more" : to_string(cnt);
                        }
                        qu[p].push(s);
                        s = backup;
                    }
                }
        }
        //break;

    }



    return "5 or more";
}

int main(){
    int T;
    cin >> T;
    while(T --){

        cin >> n;
        st = "";
        for(int i = 0; i < n; i ++){
            int t;
            cin >> t;
            st += t - 1 + 'A';
        }

        ed = source.substr(0, n);
        if(st == ed) {
            cout << 0 << endl;
            continue;
        }
        cout << bfs() << endl;
    }
    return 0;

}