题目链接：The 2016 ACM-ICPC Asia Beijing Regional Contest - E.What a Ridiculous Election - HihoCoder 1426
题意：有1e5组样例，每组样例给出一个长度为5由'0'~'9'组成的字符串S，并且对于字符串有以下3种操作：
- 操作1：交换字符串中相邻的两个字符，此操作可以进行任意次。
- 操作2：将某个字符+1，如果大于9则%10，此操作可以进行最多3次。
- 操作3：将某个字符*2，如果大于9则%10，此操作可以进行最多2次。
问将‘12345’字符串最少需要多少次操作可以转化为S。
解析：题解思路来自：https://blog.csdn.net/sizaif/article/details/78160989
只需用bfs预处理，用ans[s][i][j]表示将"12345"用i次操作2，j次操作3，加上最少次的操作1，变为的字符s的最少操作次数。
代码（29ms）：
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const int INF=0x3f3f3f3f;char str[10];
int ans[MAXN][4][3];
struct Node
{int num[6];int op2,op3,step;
}init;inline int get_sum(Node x)
{int res=0;for(int i=1;i<=5;i++){res=res*10+x.num[i];}return res;
}void bfs(Node t)
{memset(ans,0x3f,sizeof(ans));Node u,tu;t.op2=3;t.op3=2;t.step=0;int sum_t=get_sum(t);ans[sum_t][t.op2][t.op3]=0;queue<Node>Q;Q.push(t);while(!Q.empty()){u=Q.front();Q.pop();for(int i=2;i<=5;i++)//操作1{tu=u;swap(tu.num[i],tu.num[i-1]);sum_t=get_sum(tu);tu.step++;if(tu.step>=ans[sum_t][tu.op2][tu.op3]) continue;Q.push(tu);ans[sum_t][tu.op2][tu.op3]=tu.step;}if(u.op2>0)//操作2{for(int i=1;i<=5;i++){tu=u;tu.op2--;tu.num[i]=(tu.num[i]+1)%10;sum_t=get_sum(tu);tu.step++;if(tu.step>=ans[sum_t][tu.op2][tu.op3]) continue;Q.push(tu);ans[sum_t][tu.op2][tu.op3]=tu.step;}}if(u.op3>0)//操作3{for(int i=1;i<=5;i++){tu=u;tu.op3--;tu.num[i]=(tu.num[i]*2)%10;sum_t=get_sum(tu);tu.step++;if(tu.step>=ans[sum_t][tu.op2][tu.op3]) continue;Q.push(tu);ans[sum_t][tu.op2][tu.op3]=tu.step;}}}return;
}
int main()
{for(int i=1;i<=5;i++)init.num[i]=i;bfs(init);while(scanf("%s",str+1)!=EOF){Node a;for(int i=1;i<=5;i++)a.num[i]=str[i]-'0';int sum_a=get_sum(a);int res=INF;for(int i=0;i<=3;i++){for(int j=0;j<=2;j++){if(res>ans[sum_a][i][j]) res=ans[sum_a][i][j];}}if(res!=INF)printf("%d\n",res);elseprintf("-1\n");}return 0;
}
