题目大意
给出两个均由1..6组成的长度相等的字符串，每次你可以进行两种操作。操作1是把数字一样的数字全部改成另外一个数字( 改一种 )；操作2是把某个位置的数字改成另外一个数字( 改一个 )。两个操作的代价一样，求给出的第二个串变成第一个串需要的最少代价。
解答
这题做的时候比较智障，我错误地认为搜索剪支或记忆化可以通过这题( 剪支和记忆化不能同时使用，同时使用逻辑上就是错的 )。其实仔细想来，搜索每层分支太多一定会炸，记忆化状态太多不能承受，因此这个思路应该一开始就发现是错的。
这题要首先想到，操作1和操作2是分开进行的，必须是先做完了操作1，然后再做操作2。这个结论其实一开始我们就猜想了，但是以为不好证明，没有继续下去。后来大致证明下发现并不难。
假设第i个位置是1，先执行操作2变成2，再执行操作1，如果变回1的话显然第一步多余；如果变成3，那么等价于先执行操作1把所有2的变成3( 不包括i位置的1 )，然后再执行操作2直接把第i个位置的1变成3，代价一样。由此看来，先执行操作1，再执行操作2，是可以保证最少代价的。
因此，我们可以枚举操作1变到的所有状态，然后执行操作2。如何枚举操作1的状态并求得它的最少代价呢？我的初始想法是排列搞搞，但感觉比较复杂。后来看到网上的题解才想起用bfs。用6维数组p[a][b][c][d][e][f]可以表示1..6分别经过操作1变成对应数字需要的最少步数( 只需要看种类，不需要看个数 )，由于每步转移是1，所以我们可以用bfs来预处理。6维数组可以用六进制数表示。
比较简单的做法，十分强大。预处理的时间复杂度是O(68)，空间复杂度是O(66)。枚举状态计算的复杂度是O(6^6*len)。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)
#define Mem(a,b) memset(a,b,sizeof(a))
const int maxn=110+10;
const int maxL=6*6*6*6*6*6+100;
char s1[maxn],s2[maxn];
int N;
int o[maxL],F[maxL];
void change(int *p,int &x,int d) // 转化数组和六进制数
{
if (d)
{
x=0;
for (int i=0,ss=1; i<6; i++)
{
x+=ss*p[i];
ss*=6;
}
}
else
{
for (int i=0,ss=x; i<6; i++)
{
p[i]=ss%6;
ss/=6;
}
}
}
void extend(int x,int *p,int u,int v,int &t) // 扩展
{
static int q[8];
bool flag=0;
for (int i=0; i<6; i++)
if (p[i]==u)
{
flag=1;
q[i]=v;
}
else q[i]=p[i];
if (!flag) return ;
int y;
change(q,y,1);
if (F[y]==-1) o[++t]=y,F[y]=F[x]+1;
}
void Prepare() // bfs预处理
{
static int p[8];
Mem(F,255);
int h=0,t=0;
int s=0+6+2*6*6+3*6*6*6+4*6*6*6*6+5*6*6*6*6*6; // 初始状态
o[h]=s; F[s]=0;
for (; h<=t; h++)
{
int x=o[h];
change(p,x,0);
for (int i=0; i<6; i++)
for (int j=0; j<6; j++)
if (i!=j) extend(x,p,i,j,t); // 扩展
}
}
int Done(char *s1,char *s2,int state) // 枚举状态，计算操作二
{
static int p[8];
change(p,state,0);
int ret=F[state];
For(i,1,N)
{
int u=s2[i]-'0'-1;
int v=s1[i]-'0'-1;
ret+=(p[u]!=v);
}
return ret;
}
int main(int argc, char* argv[])
{
Prepare();
for (; scanf("%s%s",s1+1,s2+1)!=EOF; )
{
N=strlen(s1+1);
int ans=N;
For(i,0,maxL-1)
if (F[i]!=-1) ans=min(ans,Done(s1,s2,i));
printf("%d\n",ans);
}
return 0;
}
