简答题 偏难
#7092

数字变换 给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换 1. 交换相邻的两个数字 2.…

数字变换

给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换 

1. 交换相邻的两个数字 

2. 将一个数字加1。如果加1后大于9,则变为0 

3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。 

最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。

时间限制:1000

内存限制:65536

输入

有最多 100,000 组数据 每组数据就是包含5个数字的字符串

输出

对每组数据,输出将12345变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1

样例输入

12435
99999
12374

样例输出

1
-1
3

提示

由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。 建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; using namespace std; #define _init(x, v) memset(x, v, sizeof(x)) int rcd[100000]; bool vis[100000][5][5]; struct node {   int a[5], d, o2, o3; }; queue&lt;node&gt; q; void in() {   _init(rcd, -1);   node s = {1, 2, 3, 4, 5, 0, 3, 2};   q.push(s);   vis[12345][3][2] = 1;   rcd[12345] = 0; } int toNum(node &amp;n) {   int t = 0;   for (int i = 0; i &lt; 5; ++i) {     t *= 10;     t += n.a[i];   }   return t; } void bfs() {   while (!q.empty()) {     node s = q.front();     int t = toNum(s);     if (rcd[t] == -1 || rcd[t] &gt; s.d)       rcd[t] = s.d;     // printf("n = %d, d = %d, o2 = %d, o3 = %d\n", toNum(s), s.d, s.o2, s.o3);     ++s.d;     q.pop();     for (int i = 0; i &lt; 5; ++i) {       // o1       if (i &lt; 4 &amp;&amp; s.a[i] != s.a[i + 1]) {         swap(s.a[i], s.a[i + 1]);         if (!vis[toNum(s)][s.o2][s.o3]) {           vis[toNum(s)][s.o2][s.o3] = 1;           q.push(s);         }         swap(s.a[i], s.a[i + 1]);       }       // o2       if (s.o2 &gt; 0) {         --s.o2;         s.a[i] = (s.a[i] + 1) % 10;         if (!vis[toNum(s)][s.o2][s.o3]) {           vis[toNum(s)][s.o2][s.o3] = 1;           q.push(s);         }         s.a[i] = (s.a[i] + 10 - 1) % 10;         ++s.o2;       }       // o3       if (s.o3 &gt; 0) {         --s.o3;         int bak = s.a[i];         s.a[i] = (2 * s.a[i]) % 10;         if (!vis[toNum(s)][s.o2][s.o3]) {           vis[toNum(s)][s.o2][s.o3] = 1;           q.push(s);         }         s.a[i] = bak;         ++s.o3;       }     }   } } int main() {   in();   bfs();   int n;   while (cin &gt;&gt; n) {     cout &lt;&lt; rcd[n] &lt;&lt; endl;   }   system("pause");   return 0; }</pre>
这道题暂未补解析。