题解 | #牛牛嚯可乐#

因为题目保证一定有解，而且以及没有啥可以用的性质， 所以就直接暴力搜索所有方案。记得剪枝防止一个状态多次搜索，具体看代码

#include<bits/stdc++.h>
using namespace std;
struct ty{
    string y;//当前的字符串
    int ct;//交换了几次
};
queue<ty> q;

string x = "cocacola";
unordered_map<string,int> mp;

int main(){
    ty s;    s.ct = 0;
    cin >> s.y;

    ++mp[s.y];
    q.push(s);
    while(1){

        s = q.front();q.pop();

        if(s.y == x){// 判断是否是 “cocacola”
            cout << s.ct << '\n';
            return 0;
        }
        for(int i = 0; i < 8; ++i){
            for(int j = i + 1; j < 8; ++j ){
                ty ss = s;
                swap(ss.y[i],ss.y[j]);//交换这两个字符
                    ss.ct++;
                if(mp.find(ss.y) == mp.end())//如果这个方案没有记录过才入队
                    q.push(ss), ++ mp[ss.y];//表示这个方案已经记录了
         }

        }
    }
    return 0;
}