A48211. 数字变换给定一个包含5个数字（0-9）的字符串，例如 “02943”，请将“12345”变换到它。 你可以采取3种操作进行变换 1. 交换相邻的两个数字 2. 将一个数字加1。如果加1后大于9，则变为0 3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。最多只能用第2种操作3次，第3种操作2次 求最少经过多少次操作可以完成变换。输入有最多 100,000 组数据每组数…
填空题
困难
知识点
题目描述
数字变换
给定一个包含5个数字（0-9）的字符串，例如 “02943”，请将“12345”变换到它。 你可以采取3种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加1。如果加1后大于9，则变为0
3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次，第3种操作2次 求最少经过多少次操作可以完成变换。
输入
有最多 100,000 组数据
每组数据就是包含5个数字的字符串
输出
对每组数据，输出将"12345"变换到给定字符串所需要的最少操作步数。如果无法变换成功，输出-1
样例输入
12435
99999
12374
样例输出
1
-1
3
参考答案
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
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<node> 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& n){
int t = 0;
for(int i= 0; i < 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] > 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 < 5; ++i){
// o1
if(i < 4 && 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 > 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 > 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 >> n){
cout << rcd[n] <<endl;
}
system("pause");
return 0;
}答案解析
先做预处理，即以“12345”作为初始状态做一遍彻底的广搜，找出“12345”经合法变换能够到达的所有字符串，并记录到达这些字符串各需要多少步操作。
然后对读入的每组数据，在上述预处理记录的结果中进行查询即可。
上一题
下一题