问题 A: 魔法鲜花
时间限制: 1.000 Sec 内存限制: 128 MB
提交: 107 解决: 78
[命题人:][下载数据: ?]
题目描述
小李手上有一束魔法鲜花，他想将这些花送给小媛，但是小媛只想要特定数量的花。好在这些魔法鲜花可以在小李的控制下变化数量，这样小李就可以刚好变出足够数量的鲜花，来送给小媛了。但是笨手笨脚的小李想要尽快变出刚好数量的鲜花，现在小李找到了你，想要你告诉他最快的变化方法。
已知小李的魔法鲜花的手柄上，有3个按钮。可以对鲜花的数量做出如下改变：
（1）按A按钮：鲜花数量+1
（2）按B按钮：鲜花数量-10（手里鲜花数量足够的情况下）
（3）按C按钮：鲜花数量*2
小李的魔法鲜花只能变出1到100000的朵鲜花。
输入
一行两个整数a,b表示小明手中的初始鲜花数量与目标鲜花数量。（1<=a,b<=1e5）
输出
第一行：一个整数，表示小明得到目标鲜花数量所需要的步数。
第一行：一个字符串表示按钮的操作序列，若方法不止一种，则输出步数最小，且操作序列字典序最小的那个。
样例
提示
这题其实和抓住那头牛差不多，就是还要输出操作序列。
代码
#include <bits/stdc++.h>
using namespace std;
struct node {
int x,step;
string czxl;
};
queue <node> Q;
int newwz[4],newstep;
string newczxl[4];
bool vis[200001];
int s,t;
int main() {
cin>>s>>t;
if(s==t) { cout<<0<<endl; return 0;}
Q.push({s,0,""}); vis[s]=1;
while(!Q.empty()) {
int tx=Q.front().x;
int tstep=Q.front().step;
string tczxl=Q.front().czxl;
Q.pop();
newstep=tstep+1;
newwz[1]=tx+1; newczxl[1]=tczxl+"A";newwz[2]=tx-10;newczxl[2]=tczxl+"B";newwz[3]=2*tx; newczxl[3]=tczxl+"C";
for(int i=1; i<=3; i++) {
if(newwz[i]==t)
{
cout<<newstep<<endl;cout<<newczxl[i]<<endl; return 0;
}
int nxx=newwz[i];
if(vis[nxx]==0&&nxx>=0&&nxx<=100000)
{
Q.push({nxx,newstep,newczxl[i]});
vis[nxx]=1;
}
}
}
cout<<"wujie"<<endl;
return 0;
}
