What a Ridiculous Election ( 带约束条件的BFS )
题意： 操作1：交换相邻的两个数字，操作2：任意数字加1再模10， 操作3：任意数字*2再mod10。 给一个5位数n，问12345最少经过几次变化能成为n。注意操作1只能用3次，操作2只能用2次。
思路：开始直接想得是用一个via[]数组，bfs来遍历所有情况，结果一直wa。直到看到了大佬的博客
简述为：变成一个数的操作是有很多种的，有些用的步骤少，有些用的步骤多，在当前情况一定是取步骤少的，但如果继续往后面考虑，操作少的可能因为某一个操作用完了，无法到达后续的某种情况， 而操作步骤多的依旧可以到达。这样我们就理所应当的对每一个情况都记录下来，并往后更新。
举一个例子，比如变成 01034
依次是，12345，12354，12534，12034，21034，31034，41034，51034，01034
可以见到这里的51034用了7步，而实际上51034最优策略是6步，这里为什么用7步的51034,而不用6步的51034呢？
是因为变成7步的51034，用了一次乘法，三次加法，变成6布的51034，用了两次乘法，三次加法，而变成01034，
需要一步乘法，可是6步的51034不能再使用乘法了
所以这个约束条件就导致了不能用最优的低步数答案去推到最优的高步数答案
这里的解决方法应该是把用了三次加法，一次乘法的51034和用了三次加法，两次乘法的51034分别记录下来
这里开一个数组via[num][ins][dou],分别代表这个数，加法次数，乘法（乘二）次数
代码：
#include <bits/stdc++.h> using namespace std; typedef struct node { int date,cnt; int tot1, tot2; }ty; int via[100002][10][10]; ty t,d; void bfs( int x ) { memset(via,0x3f3f3f3f,sizeof(via)); queue <ty> Q; t.date = x; t.cnt = 0; Q.push(t); while ( !Q.empty() ) { t = Q.front(); Q.pop(); if ( via[t.date][t.tot1][t.tot2]==0x3f3f3f3f ) { via[t.date][t.tot1][t.tot2] = t.cnt; } else continue ; int i5 = t.date%10; int i4 = t.date/10%10; int i3 = t.date/100%10; int i2 = t.date/1000%10; int i1 = t.date/10000%10; if ( t.tot1<3 ) { d.tot1 = t.tot1 + 1; d.tot2 = t.tot2 ; d.cnt = t.cnt + 1; // 1 d.date = i1*10000 + i2*1000 + i3*100 + i4*10 + (i5+1)%10; Q.push(d); d.date = i1*10000 + i2*1000 + i3*100 + (i4+1)%10*10 + i5; Q.push(d); d.date = i1*10000 + i2*1000 + (i3+1)%10*100 + i4*10 + i5; Q.push(d); d.date = i1*10000 + (i2+1)%10*1000 + i3*100 + i4*10 + i5; Q.push(d); d.date = (i1+1)%10*10000 + i2*1000 + i3*100 + i4*10 + i5; Q.push(d); } if ( t.tot2<2 ) { d.tot1 = t.tot1; d.tot2 = t.tot2 + 1; d.cnt = t.cnt + 1; d.date = i1*10000 + i2*1000 + i3*100 + i4*10 + (i5*2)%10; Q.push(d); d.date = i1*10000 + i2*1000 + i3*100 + (i4*2)%10*10 + i5; Q.push(d); d.date = i1*10000 + i2*1000 + (i3*2)%10*100 + i4*10 + i5; Q.push(d); d.date = i1*10000 + (i2*2)%10*1000 + i3*100 + i4*10 + i5; Q.push(d); d.date = (i1*2)%10*10000 + i2*1000 + i3*100 + i4*10 + i5; Q.push(d); } d.tot1 = t.tot1; d.tot2 = t.tot2; d.cnt = t.cnt + 1; d.date = i2*10000 + i1*1000 + i3*100 + i4*10 + i5%10; Q.push(d); d.date = i1*10000 + i3*1000 + i2*100 + i4*10 + i5%10; Q.push(d); d.date = i1*10000 + i2*1000 + i4*100 + i3*10 + i5%10; Q.push(d); d.date = i1*10000 + i2*1000 + i3*100 + i5*10 + i4%10; Q.push(d); } } int main() { bfs(12345); int n; while ( cin>>n ) { int ans = 0x3f3f3f3f; for ( int i=0; i<=3; i++ ) { for ( int j=0; j<=2; j++ ) { ans = min(ans,via[n][i][j]); } } if ( ans == 0x3f3f3f3f ) cout << "-1" << endl; else cout << ans << endl; } return 0; }
