题解 | #牛牛嚯可乐#

牛牛嚯可乐

https://ac.nowcoder.com/acm/contest/11179/B

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



#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;
}
全部评论

相关推荐

后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
06-30 18:19
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务