题目链接：https://vjudge.net/problem/UVALive-7263

或者：http://hihocoder.com/problemset/problem/1251

 

 

题目大意：给你两个字符串，问你从一个变成另一个的最少变化次数。变化规则有二，一是将某一字符变成另一个字符，二是将某一类字符变成另一类字符，都算变化一次。

 

题解：首先有一个弯要转过来，就是先进行第二种变化，再进行第一种变化。我们首先暴力出所有的变化的可能性，以及变过去需要的变化次数，然后再进行变化一，加上变化一的次数。

比如：

初始： 1 2 3 4 5 6

目标： 1 2 3 3 6 5

表示的变化是所有初始中的4最后变成3，所有初始中的5最后变成6，所有初始中的6最后变成5，通过BFS搜出最少变化次数为4，即依次为：4变3，6变4，5变6，4变5。然后再遍历字符串进行变化一。

代码：

 

#include <bits/stdc++.h>
#define N 50000
using namespace std;

void turn_to(int x,int *a)                  //10进制变6进制
{
    for (int i=5;i>=0;i--,x/=6) a[i]=x % 6;
}
int turn_back(int *a)                           //6进制变10进制
{
    int t=0;
    for (int i=0;i<6;i++)t=t*6+a[i];
    return t;
}

int f[N];
string a,b;
int G[10][10],r[10];
queue<int>q;

void presolve()                 //BFS最小变化次数
{
    while (!q.empty())q.pop();
    int a[10]={0,1,2,3,4,5},c[10];
    int t=turn_back(a);
    memset(f,0x3f,sizeof f);
    f[t]=0;
    q.push(t);
    while (!q.empty())
    {
        int x=q.front();q.pop();
        turn_to(x,a);
        for (int i=0;i<6;i++)for (int j=0;j<6;j++)    //暴力所有可能的变化
        {
            memcpy(c,a,sizeof a);
            for (int k=0;k<6;k++) if (c[k]==i) c[k]=j; //将当前状态中的所有i变为j
            t=turn_back(c);
            if (f[t]>f[x]+1)
            {
                f[t]=f[x]+1;
                q.push(t);
            }
        }
    }
}

int main()
{
    int x[10];
    presolve();
    while(cin>>b>>a)
    {
        memset(G,0,sizeof G);
        memset(r,0,sizeof r);
        for (int i=0;i<a.length();i++)
        {
            int u=a[i]-'1',v=b[i]-'1';
            r[u]++;
            G[u][v]++;
        }
        int ans=1e8;
        for (int i=0;i<N-10;i++)            //枚举所有变化
        {
            int t=f[i];
            turn_to(i,x);
            for (int j=0;j<6;j++) t+=r[j]-G[j][x[j]];   //变化一
            ans=min(ans,t);
        }
        printf("%d\n",ans);
    }
}