What a Ridiculous Election（预处理bfs）

What a Ridiculous Election（预处理bfs）

In country Light Tower, a presidential election is going on. There are two candidates, Mr. X1 and Mr. X2, and both of them are not like good persons. One is called a liar and the other is called a maniac. They tear(Chinese English word, means defame) each other on TV face to face, on newspaper, on internet . . . on all kinds of media. The country is tore into two parts because the people who support X1 are almost as many as the people who support X2. After the election day, X1 and X2 get almost the same number of votes. No one gets enough votes to win. According to the law of the country, the Great Judge must decide who will be the president. But the judge doesn’t want to offend half population of the country, so he randomly chooses a 6 years old kid Tom and authorize him to pick the president. Sounds weird? But the democracy in Light Tower is just like that. The poor or lucky little kid Tom doesn’t understand what is happening to his country. But he has his way to do his job. Tom’s ao shu(Chinese English word, means some kind of weird math for kids) teacher just left him a puzzle a few days ago, Tom decide that he who solve that puzzle in a better way will be president. The ao shu teacher’s puzzle is like this: Given a string which consists of five digits(‘0’..‘9’), like “02943”, you should change “12345” into it by as few as possible operations. There are 3 kinds of operations: 1. Swap two adjacent digits. 2. Increase a digit by one. If the result exceed 9, change it to it modulo 10. 3. Double a digit. If the result exceed 9, change it to it modulo 10. You can use operation 2 at most three times, and use operation 3 at most twice. As a melon eater (Chinese English again, means bystander), which candidate do you support? Please help him solve the puzzle. Input There are no more than 100,000 test cases. Each test case is a string which consists of 5 digits. Output For each case, print the minimum number of operations must be used to change “12345” into the given string. If there is no solution, print ‘-1’. Sample Input 12435 99999 12374 Sample Output 1 -1 3

题目大概：

给出一个五位的数字，问12345经过多少操作能变成这个数。操作有一下三种。

1.交换相邻的两位，可以交换无数次。

2.任意一位的数字+1，对10取模。最多增加3次。

3.任意一位数字*2，对10取模。最多增加2次。

思路：

测试数据太多，可以先预处理，询问的时候可以查表。

直接 暴力bfs 12345 可以转化为那些数，并且需要多少步。

代码

#includeusing namespace std;#define ll long longconst int mod=10;const int INF=0x3f3f3f3f;const int maxn=1100;const int maxm=110000;const double pi=acos(-1);int dp[100001][5][5];struct node{ int sum; int ans1; int ans2; int tem;};int us[5];int b[5];void init(){ queueQ; node st; st.sum=12345; st.ans1=3; st.ans2=2; st.tem=0; Q.push(st); while(!Q.empty()) { node u=Q.front(); Q.pop(); for(int i=0; i<5; i++) { us[4-i]=u.sum%10; u.sum/=10; } node v; for(int i=0; i<4; i++) { for(int j=0; j<5; j++)b[j]=us[j]; swap(b[i],b[i+1]); int sum_1=0; for(int j=0; j<5; j++) { sum_1=sum_1*10+b[j]; } v.sum=sum_1; v.ans1=u.ans1; v.ans2=u.ans2; v.tem=u.tem+1; if(dp[v.sum][v.ans1][v.ans2]!=INF)continue; dp[v.sum][v.ans1][v.ans2]=v.tem; Q.push(v); } if(u.ans1>=0) { for(int i=0; i<5; i++) { for(int j=0; j<5; j++)b[j]=us[j]; b[i]=(b[i]+1)%mod; int sum_1=0; for(int j=0; j<5; j++) { sum_1=sum_1*10+b[j]; } v.sum=sum_1; v.ans1=u.ans1-1; v.ans2=u.ans2; v.tem=u.tem+1; if(dp[v.sum][v.ans1][v.ans2]!=INF)continue; dp[v.sum][v.ans1][v.ans2]=v.tem; Q.push(v); } } if(u.ans2>=0) { for(int i=0; i<5; i++) { for(int j=0; j<5; j++)b[j]=us[j]; b[i]=(b[i]*2)%mod; int sum_1=0; for(int j=0; j<5; j++) { sum_1=sum_1*10+b[j]; } v.sum=sum_1; v.ans1=u.ans1; v.ans2=u.ans2-1; v.tem=u.tem+1; if(dp[v.sum][v.ans1][v.ans2]!=INF)continue; dp[v.sum][v.ans1][v.ans2]=v.tem; Q.push(v); } } }}int main(){ memset(dp,INF,sizeof(dp)); dp[12345][3][2]=0; init(); int n; while(~scanf("%d",&n)) { int min_1=INF; for(int i=0; i<=3; i++) { for(int j=0; j<=2; j++) { min_1=min(min_1,dp[n][i][j]); } } if(min_1==INF) { printf("-1\n"); } else printf("%d\n",min_1); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。