[UVALive 7263]Today Is a Rainy Day

一个赛场上不小心Hack了队友正确思路的题。。。(补题谢罪!!!

题目链接及题目大意:给你两个长度不超过110的字符串,同时你有两种操作:第一种操作为将一个数字转换为另一个数字;第二种操作为将一种数字转换成另一种数字,问最少能够经过几次操作将第二个字符串变为第一个字符串。

恰巧今天也是一个Rainy Day。

点击查看原英文题面

​ Today is rainy day. The tempetature is apparently lower than yesterday. Winter is comming. It always leaves people feeling fatigued ans 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 heave 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 gose 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 dicides to skip class and dose 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 aoolies 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 nest 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 avery 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

所有在网上找到的题解说的做法均为:先进行第二种操作,然后进行第一种操作。虽然我不会证明,但直观感觉上确实是这样。

因此首先我们需要使用BFS的方法找出每一种映射所需要的步数。映射即为将$1$~$6$的每一个数字只用第二种操作将其重新变成另一种数字所需要的步数,例如$123456$->$123455$->$126455$->$326455$->$326411$->…

BFS过后我们就枚举所有的映射,将所有的数字对应于映射后的数字,然后计算第一种操作的操作次数,两种操作的次数总和即为总的操作数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+10;
const int limit=216*216;
int dp[maxn];
char s[maxn],t[maxn],q[maxn];
int len;
struct node{
int x[10];
};
int cal(node a){//计算当前状态的哈希值
int sum=0;
for(int i=1;i<=6;i++) sum=sum*6+a.x[i]-1;
return sum;
}
void bfs(){//bfs枚举所有的映射
memset(dp,-1,sizeof(dp));
queue<node>que;
node a;
for(int i=1;i<=6;i++) a.x[i]=i;
dp[cal(a)]=0;
que.push(a);
while(!que.empty()){
a=que.front();
que.pop();
node b;
//枚举所有的情况
for(int i=1;i<=6;i++){
for(int j=1;j<=6;j++){
b=a;
for(int k=1;k<=6;k++){//将所有的数字i变为数字j
if(b.x[k]==i) b.x[k]=j;
}
if(dp[cal(b)]==-1){
dp[cal(b)]=dp[cal(a)]+1;
que.push(b);
}
}
}
}
}
int solve(int x){
node q;
int sum=dp[x];
//将哈希值变回原来所对应的值
for(int i=6;i>=1;i--){
q.x[i]=x%6+1;
x/=6;
}

for(int i=0;i<len;i++){
if(q.x[t[i]-'0']!=s[i]-'0') sum++;
}
return sum;
}
int main()
{
bfs();
while(~scanf("%s",s)){
scanf("%s",t);
len=strlen(s);
int ans=1000000;
for(int i=0;i<=limit;i++){
if(dp[i]!=-1){
ans=min(ans,solve(i));
}
}
printf("%d\n",ans);
}
return 0;
}
/*
22345611
12345611
2234562221
1234561221
2234562211
1234561111
22345622112
12345611111
654321654321654321654321
123456123456123456123456

*/
感谢您的支持
-------------本文结束感谢您的阅读-------------