Link: Vjudge
　　　UVA

Description:
PDF题面:Today is a rainy day
Today is a rainy day. The temperature is apparently lower than yesterday. Winter is coming. It always
leaves people feeling fatigued and tired.
Lee hasn’t prepared for winter yet. As he wakes up this morning, he looks out of the window.
Yesterday’s shining sunlight can no longer be seen. It is dark outside. The sky looks so heavy that it
may collapse down at any moment. Lee gets out of his bed, shakes his head slightly to make himself
more awake. But it’s of no use for him. Then he goes to the restroom and washes up.
Lee has a class in fifteen minutes. If he sets out immediately, he may gets to the classroom on time.
But he is not in the mood to do so. He decides to skip class and does something more interesting to
train his mind.
He takes out a draft paper and writes a list of digits using a dice. It is obvious that the digits are
all between 1 and 6. And then he applies two kind of modifications to the digits. The first kind is
to modify one digit into another. The second kind is to modify one kind of digits into another. For
example, he can modify “12123” to “12121” using the first kind of modification, or modify “12123” to
“13133” using the second kind of modification. In the process of modification, all digits should be in
{1, 2, 3, 4, 5, 6};
After a few modifications, he feels tired but pleased. He’s got a list of digits which is very different
from the original one. Thinking of the next thing to do, Lee becomes a little excited. He is going to
figure out the least number of modifications to transform the final list back to the original one using
the same rules.
Lee made it in a very short time. Can you do this like him?
Input
There are up to 100 test cases.
For each test case, there are two lines containing two lists of digits, representing the original list
and the final list in order. The digits are all between 1 and 6. It is guaranteed that two lists are of
same length. The length will not be greater than 110.
Output
For each test case, output one integer, the answer.
Sample Input
22345611
12345611
2234562221
1234561221
2234562211
1234561111
22345622112
12345611111
654321654321654321654321
123456123456123456123456
Sample Output
1
2
3
3
11

Problem solving:
这道题的意思就是给你两个只有1~6这六个数字组成的字符串，有一种操作是把一个字符串中的一类字符串都换成另一个。比如说这个字符串里面的1全部换成2，第二种操作就是单独的换一个。都是可以任意换的，问你最少换几次，能使第二个字符串和第一个字符串相等。

一开始信誓旦旦的跟队友说这是一道dp的题，然后心安理得的训练赛的时候跳过。
后来补题的时候发现，哦，原来是BFS，啊！怎么能这么写，太妙了吧。（好了不BB了，我们开始讨论这个解题思路

首先我们要知道因为这里要求的步数是最小的，所以我们要尽可能地使用更换一类的操作，才会使总操作数最小。关于这个的证明，网上搜出来的题解大多没有具体说，因为这个确实是属于“一想就是这样的啊”的结论。但是我们想一下，如果现在有两个串分别是”123456“和”123455“，这个时候当然是一次，并且这一次无论是哪种操作，结果都是一样的。但是如果这个串是”123444“和”123333“，如果你一个一个换，需要四次，但是如果你先把'3'全部换成'4'，再对那个剩下的变成4的3的处理其实就跟上一种情况说的一样了。其实总结一句话说就是，只要换一个能解决的换一类都能解决。（仅是个人理解）

并且这个字符串中只是由1~6这六个字符串组成的，所以我们考虑每一种第二类变化的话，会有将近6^6种变化。所以我们可以通过使用一个六位的字符串来标示出来这将近6^6种变化以及变换所需要的次数计算出来并存起来，这就用到了BFS。然后枚举每一种情乱，再看剩下会有哪些不同的数再采用一个变的那种变化，取最小值即可。

网上大部分题解说到这就丢代码了。可能高智商比较好明白，但是我整整想了一天才搞明白。
'通过使用一个六位的字符串来标示出来这将近6^6种变化以及变换所需要的次数计算出来并存起来'这句话就是重点，我门这个算出来的是每一位数字变化之后的情况，所以我们初始情况下首先定义一个”123456“的字符串进行bfs。这里再说下去，会更加抽象和不好理解，我给代码加上了我认为的完全清晰的注释。可以一边看代码一边看注释理解这句话。

Code:

// 注：下面注释中无特别说明的均表示变化一类的那种变化
#include <bits/stdc++.h>
using namespace std;
const int        maxn = 1e6 + 10;
const int        INF = 0x3f3f3f3f;
string           x, y;
map<string, int> ma;   // 记录从”123456“变化到每种情况所需要的次数
queue<string>    que;  //BFS需要用到
string           pre[maxn];  //存下来每一种可以变化到的情况，方便以后遍历
int              pos = 0;
void init()  //预处理出来每一种变化情况
{
    string a, b;
    ma["123456"] = 1;   //标记123456已经出现过，避免死循环
    que.push("123456");
    pre[++pos] = "123456"; //存入string数组
    while (!que.empty())
    {
        string mid = que.front(), Mid = "000000";
        que.pop();
        for (int i = 0; i < 6; i++)  //这个双重for循环就是模拟的把所有的i+1换成j+1
        {
            for (int j = 0; j < 6; j++)
            {
                if (i == j)     //如果这两个相等，就没必要换下去了
                    continue;
                for (int k = 0; k < 6; k++)  //只有6个字符，所以这里循环6次就行
                {
                    if (mid[k] == '1' + i)    //如果当前情况下，出现了一个跟i+1的值相等的数就需要变化成j+1
                        Mid[k] = '1' + j;
                    else
                        Mid[k] = mid[k];        //如果不是i+1，不需要变化
                }
                if (!ma[Mid])   //如果ma[mid]为0，说明这种情况还没记录过
                {
                    ma[Mid] = ma[mid] + 1;  //Mid这种情况是mid变化了一次过来的，所以变化次数加一
                    que.push(Mid);
                    pre[++pos] = Mid;   //存进字符串数组
                }
            }
        }
    }
}

int solve()
{
    int ans = INF, l = x.size();   //因为答案是一个最小值，要取min，所以初始化为一个极大值
    for (int i = 1; i <= pos; i++) //遍历每一种可以变化到的情况
    {
        int cnt = ma[pre[i]] - 1;  //这种情况下的答案初始化为已经变化了的次数，因为我们计算变化次数的时候123456也算了一次，所以要减一
        for (int j = 0; j < l; j++)  //遍历需要变换的字符串的每一个字符，判断它与当前这种变换的情况下的结果需要再进行几次第一次变化才可以相等
        {
            if (pre[i][y[j] - '0' - 1] != x[j])   //这一步真的是关键，pre[i]代表的是当前遍历到的这种变化情况下123456每一个字符所对应的变化到的字符，因为我们一开始就是初始化的123456，所以pre[i][y[j] - '0' - 1]代表的就是123456这六个字符在这一次变化下的结果。这个理解了就很简单了
                cnt++;   //如果pre[i][y[j] - '0' - 1]与x[j]不等，当前情况答案加一，因为需要一次第一种变化
        }
        ans = min(ans, cnt);  //答案每次更新为最小值
    }
    return ans;
}

int main()
{
    init();  //预处理
    while (cin >> x >> y)
    {
        cout << solve() << endl;
    }
}

可能看完了你还不是很明白，其实理解的关键就在于BFS预处理得到的结果以及pre[i][y[j] - '0' - 1] != x[j])的理解。
这里我在说一遍（没用的话也没事，如果帮到了你我很荣幸）：BFS中从123456开始搜索，每次得到的情况都是其中一个数字变化成另外一个数字的情况。例如，pre字符串数组中会有223456，323456，111111等。代表的就是对应位置上的数字经过了ma[pre[i]]次变化之后变成的数字。初始状态下字符串为123456，正好跟下标是对应的，所以我们可以直接用pre[i][S[i]-'0'-1]来表示当前pre[i]的情况下变化成的数字，在跟之前的字符串的这个位置的字符进行比较，如果不等，就再来一次只变化一个的操作，答案加一。

赏