题解 | #牛牛嚯可乐#

题目大意

给你一个字符串，问你最少交换次字符可以构成“cocacola”（每次交换两个字符）

解题思路

因为数据较小，所以如果一个位置不合法，直接枚举和后面的哪个字符交换（前面的已经构造好了）

code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int ans;
char s[100];
string str;
void dfs(int x,int now)
{
    if(now>=ans)return;
    if(x>8){
        ans=min(ans,now);
        return;
    }
    if(s[x]==str[x])dfs(x+1,now);//符合了，直接跳过
    for(int i=x+1;i<=8;++i)
        if(s[i]==str[x]){
            swap(s[x],s[i]);
            dfs(x+1,now+1);
            swap(s[x],s[i]);
        }
    return;
}
int main()
{
    scanf("%s",s+1);
    str=" cocacola";
    ans=100;
    dfs(1,0);
    printf("%d",ans);
    return 0;
}