hihoCoder 1426 : What a Ridiculous Election（总统夶选）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

hihoCoder #1426 : What a Ridiculous Election（总统夶选）

Description - 题目描述

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 - 样例输入

Sample Output - 样例输出

题解

花式枚举，次序全排列 + 数值枚举 + 位置枚举。
因为操作有顺序问题，把最多5次操作压入数组，用全排列枚举次序。
根据上面枚举出来的全排列，DFS搜索各个位置上可能出现的数值情况，压入队列。
（友情提示某人一开始想写5层循环，然后写到第二层就弃坑了……）
这个时候队列中已经有不少初始元素了，相邻位置两两交换，BFS搜索可能的情况，并更新。
（队列 == BFS ？ 雾 : 雾）

代码 C++