1361：产生数(Produce)

【题目描述】
给出一个整数n（n≤2000）和k个变换规则（k≤15）。规则：

① 1个数字可以变换成另1个数字；

② 规则中，右边的数字不能为零。

例如：n=234，k=2规则为

2 → 5

3 → 6

上面的整数234经过变换后可能产生出的整数为（包括原数）234，534，264，564共4种不同的产生数。

求经过任意次的变换（0次或多次），能产生出多少个不同的整数。仅要求输出不同整数个数。

【输入】
nkx1x2…xny1y2…yn
【输出】
格式为一个整数（满足条件的整数个数）。

【输入样例】
234
2
2 5
3 6
【输出样例】
4

分析

1. 一个pair数组去存k个变换规则； 一个init函数把输入的n的每一位数转为数组里，由于vector有reverse函数，我就先存在vector，然后逆序一下就是原数；一个generate函数，把当前的存在vector的数进行构造成一个整数；一个vis数组去标记某个数是否已经构造过；
2. 在dfs时候，我们遍历n每一位，在某位然后在进行遍历pair数组，看看有没有可以转化的数字，可以的话，就修改v[i]，然后构造修改过的数，如果没出现过，就标记一下，dfs再往下找；然后在找完了每一位，也就是退出了if条件里产生的一系列递归搜索，然后就把v[i]恢复一下，v[i] = p[j].first;；
3. 需要注意把n这个数本身就标记出来，不然有的变换规则把这个数变为它本身，你没标记过，然后你本身ans初始也为1，就会造成多记一次，所以，在dfs之前就标记下：vis[n] = 1;；（比如输入：234 1 2 2，但是如果不提前标记下，结果就会输出2）

dfs

#include 

using namespace std;

int n, k, ans = 1;
pair<int, int> p[20]; //存储变换规则
vector<int> v;  //存储n这个数的每一位
int vis[10010]; //标记某个数是否出现过

//把n的每一位数字存储在v中
void init(int n) {
    while (n != 0) {
        v.push_back(n % 10);
        n /= 10;
    }
    std::reverse(v.begin(), v.end());
}

//把vis数组转化为数字
int generate() {
    int res = 0;
    for (int i = 0; i < v.size(); ++i) {
        res = res * 10 + v[i];
    }
    return res;
}

void dfs() {
    for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < k; ++j) {
            if (v[i] == p[j].first) {
                //当前位满足替换
                v[i] = p[j].second;
                int newNum = generate();
                if (!vis[newNum]) {
                    //新数字
                    vis[newNum] = 1;
                    ans++;
                    dfs();
                }
                //还原回来
                v[i] = p[j].first;
            }
        }
    }
}

int main() {
    cin.tie(0);
    cin >> n >> k;
    init(n);
    for (int i = 0; i < k; ++i) {
        cin >> p[i].first;
        cin >> p[i].second;
    }
    //不能忘把本身标记一下
    vis[n] = 1;
    dfs();
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

bfs

1. 和dfs差不多的思路，不过init函数需要v.clear();，不然上一个数字还在里面存，当前数字又存里面（越续越长，而且影响bfs的遍历）；
2. 先把n放进队列，然后在while循环中（也就是bfs中），出队一个元素（为一个整数类型，转化为数组），然后调用init函数，存在一个新的动态数组（v.clear()），然后两层for，把每个满足条件的新构造的数字（在当前队头的元素进行改造的数）放进队列，然后把所有可以构造的数字放进队列，在下一次while中，让在他们的基础上再次构造；
3. bfs在这题应用的思想就是，把当前数字所能构造出来的所有数放队列，然后将队列的数，再次以他们的基础上处理新构造的数，一直把队列搞空（就是每个数都在它的基础上构造过）；

#include 

using namespace std;

int n, k, ans = 1;
pair<int, int> p[20]; //存储变换规则
vector<int> v;  //存储n这个数的每一位
int vis[10010]; //标记某个数是否出现过
queue<int> q;

//把n的每一位数字存储在v中
void init(int n) {
    //记得清一下，不然上次的数字也在
    v.clear();
    while (n != 0) {
        v.push_back(n % 10);
        n /= 10;
    }
    std::reverse(v.begin(), v.end());
}

//把vis数组转化为数字
int generate() {
    int res = 0;
    for (int i = 0; i < v.size(); ++i) {
        res = res * 10 + v[i];
    }
    return res;
}

void bfs() {
    q.push(n);
    while (!q.empty()) {
        int num = q.front();
        init(num);
        q.pop();
        for (int i = 0; i < v.size(); ++i) {
            for (int j = 0; j < k; ++j) {
                if (v[i] == p[j].first) {
                    //当前位满足替换
                    v[i] = p[j].second;
                    int newNum = generate();
                    if (!vis[newNum]) {
                        //新数字
                        vis[newNum] = 1;
                        q.push(newNum);
                        ans++;
                    }
                    //还原回来
                    v[i] = p[j].first;
                }
            }
        }
    }
}

int main() {
    cin.tie(0);
    cin >> n >> k;
    init(n);
    for (int i = 0; i < k; ++i) {
        cin >> p[i].first;
        cin >> p[i].second;
    }
    //不能忘把本身标记一下
    vis[n] = 1;
    bfs();
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71