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:

'通过使用一个六位的字符串来标示出来这将近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;
}
}