1361：产生数(Produce)

时间限制: 1000 ms         内存限制: 65536 KB

【题目描述】

【输入】

【输出】

【输入样例】

234
2
2 5
3 6

【输出样例】

4

解析：

详见代码：

#include <bits/stdc++.h>
using namespace std;
string n;
int k;
bool b[10000];//标记某个数是否出现过
int x[20],y[20];//变换规则
int ans=0;
queue<string> q;
void bfs() {
    q.push(n);//种子入队
    b[stoi(n)]=1;//标记出现过
    ans++;//答案加一
    while (q.size()) {//只要队列里有数
        string xx=q.front();//取队首
        q.pop();//弹出队首
        for (int i=0;i<xx.length();i++) {//枚举每一位
            for (int j=1;j<=k;j++) {//枚举每个变换规则
                if (xx[i]==x[j]+'0') {//符合规则
                    string yy=xx;//临时变量
                    yy[i]=char(y[j]+'0');//按规则变化
                    if (b[stoi(yy)]==0){//如果没出现过
                        ans++;//答案加一
                        q.push(yy);//入队
                        b[stoi(yy)]=1;//标记出现过
                    }
                }
            }
        }
    }
    return;//返回
}
int main() {
    cin >>n>>k;
    for (int i=1;i<=k;i++) {
        cin >>x[i]>>y[i];
    }
    bfs();
    cout <<ans<<endl;
    return 0;
}

用int的解法：

#include <bits/stdc++.h>
using namespace std;
int n,k,f[10000],a[20],b[20],ans=0,x[20],z=1;
queue<int> q;
void bfs() {
    q.push(n);
    f[n]=1;
    ans++;
    while (q.size()) {
        int xx=q.front();
        z=1;
        while (xx) {
            x[z]=xx%10;
            xx/=10;
            z++;
        }
        for (int i=1;i<z;i++) {
            for (int j=1;j<=k;j++) {
                if (x[i]==a[j]) {
                    int y=0;
                    for (int l=z-1;l>=1;l--) {
                        if (l==i) {
                            y=y*10+b[j];
                        } else {
                            y=y*10+x[l];
                        }
                    }
                    if (f[y]==0) {
                        q.push(y);
                        f[y]=1;
                        ans++;
                    }
                }
            }
        }
        q.pop();
    }
    return ;
}
int main() {
    cin >>n>>k;
    for (int i=1;i<=k;i++) {
        cin >>a[i]>>b[i];
    }
    bfs();
    cout <<ans<<endl;
    return 0;
}