双向广搜-> hdu1195

问题描述：密码锁有起始和目标两个状态，状态有4个连续数字，数字范围是1~9。其中特殊情况9 + 1 = 0, 1 - 1 = 9。 每次操作可以交换相邻的两个锁上的数字，或者将该位上数字±1。求最小操作次数

分析：是一道双向广搜的题，但是这个题目的第一个思路就是枚举所有的排列组合状态，然后对每个状态求出变成目标状态的最少加减次数以及初始态到该状态的交换次数，直接dfs枚举状态 + 判定即可。

因为没有hdu账号，所以testcase通过了就先默认正确了。

这里初始序列到目标序列交换次数用的是暴力从后往前交换，类似冒泡，好像只有这么一种方法。

void solve(){
    string s, t;
    cin >> s >> t;

    auto getcost = [&](int i, int j)->int{
        int rst = 0;
        if (s[i] <= t[j]){
            rst = min(t[j] - s[i], s[i] + 9 - t[j]);
        }
        else{
            rst = min(s[i] - t[j], t[j] + 9 - s[i]);
        }
        return rst;
    };

    string bg = "0123";
    auto getSwap = [&bg](vector<int>& chosen)->int{
        int rst = 0;
        string now;
        for (auto& x : chosen){
            now += ('0' + x);
        }
        for (int i = 3; i >= 0; --i){
            if (now[i] != bg[i]){
                for (int j = i - 1; j >= 0; --j){
                    if (now[j] == bg[i]){
                        swap(now[i], now[j]);
                        rst ++;
                        break;
                    }
                }
            }
        }
        return rst;
    };
    
    int ans = int(1e9);
    function<void(int, vector<int>&, int)> dfs = [&](int idx, vector<int>& chosen, int cost){
        if (idx == 4 || cost >= ans){
            if (changeMin(ans, cost + getSwap(chosen))){
                //
            }
            return;
        }
        for (int i = 0; i <= 3; ++i){
            bool haschosen = false;
            for (int j = 0; j < idx; ++j){
                if (chosen[j] == i){
                    haschosen = true;
                }
            }
            if (haschosen){
                continue;
            }
            else{
                chosen[idx] = i;
                dfs(idx + 1, chosen, cost + getcost(idx, i));
            }
        }
    };
    
    vector<int> chosen(4, -1);
    dfs(0, chosen, 0);

    cout << ans << '\n';
}