产生数

题目描述

给定一个初始整数 n（1≤n≤2000）和 k 个数字变换规则（1≤k≤15）。每条规则形如$a\to b$，表示可以将数字$a$ 替换为数字 ( b）。规则满足以下约束：

1. 变换方向：规则是单向的（即 $a\to b$ 不意味着$b\to a$）。

2. 非零约束：规则右侧的数字 $b$ 不能为 0（保证变换后的数字有效）。

通过应用这些规则任意次数（包括零次），可以将 $n$ 的某些数字替换为其他数字，从而生成一系列新的整数。求所有可能生成的不同整数的总数（包括原始数 $n$）。

问题分析：

题目要求我们计算给定初始数字n，通过一系列数字变换规则（每个规则允许将某个数字替换为另一个非零数字），经过任意次数的变换后，能够生成的不同整数的总数。关键在于如何高效地枚举所有可能的变换组合，并避免重复计数。

算法选择：

1. 广度优先搜索（BFS）：

   • 思路：从初始数字出发，逐层生成所有可能的变换数字。每次变换一位数字，将新生成的数字加入队列，直到无法生成新的数字为止。

   • 优点：直观，易于实现，可以确保所有可能的数字都被生成。

   • 缺点：对于较大的数字或较多的变换规则，可能会生成大量中间数字，占用较多内存和时间。

   • 为了进一步优化BFS的实现，可以考虑以下几点：

     • 字符串处理：将数字作为字符串处理，方便逐位修改。

     • 提前终止：如果某位数字没有变换规则，可以跳过该位的处理。

     • 规则预处理：预处理变换规则，快速查找某位数字可以变换成的所有数字。

     
     

     
     

2. 深度优先搜索（DFS）：

   • 思路：从初始数字出发，递归或迭代地尝试所有可能的变换路径，直到无法继续变换为止。

   • 优点：实现简单，内存消耗相对较小（取决于实现方式）。

   • 缺点：可能需要处理重复状态，且不如BFS直观。

输入

• 第一行：整数 $n$（初始数字）。

• 第二行：整数 $k$（规则数量）。

• 接下来$k$ 行：每行两个数字 $a$ 和$b$，表示一条规则$a\to b$。

输出

• 一行，输出所有可能生成的不同整数的总数。

样例

提示

解释：
初始数：234
可能生成的数：

• 不应用任何规则：234

• 替换第一个 2：534

• 替换 3：264

• 同时替换 2 和 3：564
  共 4 种不同的数。

来源/分类