题解 | #牛牛吃米粒#

b题
非常经典的回溯算法，可以算作板子题练手

举个例子将 $a=coca$ 变为 $b=caoc$

从第一个字符比较。容易发现 $dfs$ 里有两个变量，一个是当前位置 $pos$ ，另一个是在当前位置时已经交换了的次数。

$pos=0$ ， $a[0]=b[0]$ ，直接 $dfs$ 下一位置

$pos=1$ ， $a[1] \neq b[1]$ ，我们要找到使得 $a[i]=b[1]$ 的 $i$ ，然后交换二者。尤其注意要恢复你刚才修改的状态。

注意：边界是 $pos=8$

按照上述思想，很容易写出此题的代码。

#include <bitsdc++.h>
using namespace std;
int ans = 10;
char a[10];
char b[] = "cocacola";
inline void dfs(int pos, int move)
{
    if(pos == 8)
        return (void)(ans = min(ans, move));
    if(a[pos] == b[pos])
        dfs(pos + 1, move);
    else
    {
        for (int i = pos + 1; i <= 7; i++)
            if(a[i] == b[pos])
            { 
                swap(a[i], a[pos]);
                dfs(pos + 1, move + 1);
                swap(a[i], a[pos]);
            }
    }
}
int main()
{
    scanf("%s", a);
    dfs(0, 0);
    cout << ans << endl;
    return 0;
}