首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#7324

数字变换 给定一个包含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;cstdlib&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;string&gt; using namespace std; char a[6] = "12345"; bool vis[100000][4][3]; int ans[100000]; struct node {   string a;   int op2, op3, step;   node(string aa, int o2, int o3, int ss = 0)       : a(aa), op2(o2), op3(o3), step(ss){}; }; queue&lt;node&gt; q; int main() {   memset(vis, false, sizeof(vis));   memset(ans, -1, sizeof(ans));   q.push(node("12345", 0, 0));   vis[12345][0][0] = true;   ans[12345] = 0;   while (!q.empty()) {     node no = q.front();     q.pop();     string temp = no.a;     if (ans[int(atof(temp.c_str()))] == -1)       ans[int(atof(temp.c_str()))] = no.step;     //    cout&lt;&lt;no.a&lt;&lt;endl;     // 第一种操作     for (int i = 0; i &lt; 4; i++) {       swap(temp[i], temp[i + 1]);       if (!vis[int(atof(temp.c_str()))][no.op2][no.op3]) {         vis[int(atof(temp.c_str()))][no.op2][no.op3] = true;         q.push(node(temp, no.op2, no.op3, no.step + 1));       }       swap(temp[i], temp[i + 1]);     }     // 第二种操作     if (no.op2 &lt; 3) {       for (int i = 0; i &lt; 5; i++) {         temp = no.a;         int num = temp[i] - '0';         num++;         if (num == 10)           num = 0;         temp[i] = '0' + num;         if (!vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3]) {           vis[int(atof(temp.c_str()))][no.op2 + 1][no.op3] = true;           q.push(node(temp, no.op2 + 1, no.op3, no.step + 1));         }       }     }     // 第三种操作     if (no.op3 &lt; 2) {       for (int i = 0; i &lt; 5; i++) {         temp = no.a;         int num = temp[i] - '0';         num *= 2;         if (num &gt; 9)           num %= 10;         temp[i] = '0' + num;         if (!vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1]) {           vis[int(atof(temp.c_str()))][no.op2][no.op3 + 1] = true;           q.push(node(temp, no.op2, no.op3 + 1, no.step + 1));         }       }     }   }   while (cin &gt;&gt; a) {     cout &lt;&lt; ans[int(atof(a))] &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。