workspace/cpp/algo/hdu3095-doublemap.cpp

/*
        #
       ###
      #####
       ###
        #
*/
#include <iostream>
#include <vector>
#include <deque>
#include <map>
#include <algorithm>

using namespace std;

// 邻居表：定义每个索引位可以和哪些位交换
vector<int> adj[13] = {
    {2},                // 0 -> 2
    {2, 5},             // 1 -> 2, 5
    {0, 1, 3, 6},       // 2 -> 0, 1, 3, 6
    {2, 7},             // 3 -> 2, 7
    {5},                // 4 -> 5
    {1, 4, 6, 9},       // 5 -> 1, 4, 6, 9
    {2, 5, 7, 10},      // 6 -> 2, 5, 7, 10
    {3, 6, 8, 11},      // 7 -> 3, 6, 8, 11
    {7},                // 8 -> 7
    {5, 10},            // 9 -> 5, 10
    {6, 9, 11, 12},     // 10 -> 6, 9, 11, 12
    {7, 10},            // 11 -> 7, 10
    {10}                // 12 -> 10
};
/*
int bfs(vector<int> from, vector<int> to) {
    if (from == to) return 0;
    
    map<vector<int>, int> mp;
    deque<vector<int>> dqf, dqb;

    dqf.push_back(from);
    dqb.push_back(to);
    mp[from] = 1;  // 正向从 1 开始
    mp[to] = -1;   // 反向从 -1 开始

    while (!dqf.empty() && !dqb.empty()) {
        // 扩展较小的一端
        bool forward = dqf.size() <= dqb.size();
        deque<vector<int>>& dq = forward ? dqf : dqb;
        
        vector<int> top = dq.front();
        dq.pop_front();
        int step = mp[top];

        // 超过步数限制剪枝 (双向BFS每边超过10步总计就可能超20)
        if (abs(step) > 10) continue; 

        // 找到两个空格（0）的位置
        for (int i = 0; i < 13; ++i) {
            if (top[i] == 0) {
                // 尝试将邻居移动到空格
                for (int neighbor : adj[i]) {
                    vector<int> next_v = top;
                    swap(next_v[i], next_v[neighbor]);

                    if (mp.count(next_v)) {
                        if (forward && mp[next_v] < 0) {
                            int total = (step - 1) + abs(mp[next_v]);
                            if (total <= 20) return total;
                        }
                        if (!forward && mp[next_v] > 0) {
                            int total = (abs(step) - 1) + mp[next_v];
                            if (total <= 20) return total;
                        }
                        continue;
                    }
                    
                    if (abs(step) < 11) { // 限制单向搜索深度
                        mp[next_v] = forward ? step + 1 : step - 1;
                        dq.push_back(next_v);
                    }
                }
            }
        }
    }
    return -1;
    }*/

int bfs(vector<int> from, vector<int> to) {
    if (from == to) return 0;

    map<vector<int>, int> mpf, mpb;
    deque<vector<int>> dqf, dqb;

    dqf.push_back(from);
    dqb.push_back(to);
    mpf[from] = 0;
    mpb[to] = 0;

    while (!dqf.empty() && !dqb.empty()) {
        // 扩展较小的一端
        bool forward = dqf.size() <= dqb.size();

        if (forward) {
            vector<int> top = dqf.front();
            dqf.pop_front();
            int step = mpf[top];
            if (step >= 10) continue;

            for (int i = 0; i < 13; ++i) {
                if (top[i] == 0) {
                    for (int neighbor : adj[i]) {
                        vector<int> next_v = top;
                        swap(next_v[i], next_v[neighbor]);

                        if (mpf.count(next_v)) continue;

                        mpf[next_v] = step + 1;

                        if (mpb.count(next_v)) {
                            int total = mpf[next_v] + mpb[next_v];
                            if (total <= 20) return total;
                        }

                        dqf.push_back(next_v);
                    }
                }
            }
        } else {
            vector<int> top = dqb.front();
            dqb.pop_front();
            int step = mpb[top];
            if (step >= 10) continue;

            for (int i = 0; i < 13; ++i) {
                if (top[i] == 0) {
                    for (int neighbor : adj[i]) {
                        vector<int> next_v = top;
                        swap(next_v[i], next_v[neighbor]);

                        if (mpb.count(next_v)) continue;

                        mpb[next_v] = step + 1;

                        if (mpf.count(next_v)) {
                            int total = mpf[next_v] + mpb[next_v];
                            if (total <= 20) return total;
                        }

                        dqb.push_back(next_v);
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    const vector<int> end({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0});
    int n;
    cin >> n;
    vector<vector<int>> pz(n, vector<int>(13));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 13; ++j){
            cin >> pz[i][j];
        }
    }
    for(int i = 0; i < n; ++i){
        int x = bfs(pz[i], end);
        if(x == -1) cout << "No solution!" << endl;
        else cout << x << endl;
    }
    return 0;
}