这个题是一个排列组合问题,
以这样一组数据为例:
12040 7
1 2
1 3
4 1
2 5
5 3
4 6
6 0
1可以变成2、3,2又可以变成5,共有1(不变)、2、3、5四个可能数字;
同理,2有2、5、3三个可能数字。
3不能变成其他数字,只有一个可能数字。
4可以变成4、1、2、3、5五个可能数字。
5可以变成5、3两个可能数字。
6不能变成其他数字,只有一个可能数字。
0可以变成0、6两个可能数字。
在12040这个数字中,每个数码都可能变为对应的可能数字,根据乘法原理,共有4×3×2×5×2=240种可能数字,并且不会重复。
因此我们可以递归搜索输入数字的每一位,用一个数组来存每一位可以变换的种类,然后用循环将所有种类相乘。用for循环对每一位进行dfs搜索,而在dfs搜索中,要循环1~9,看是否可以变换。注意:可以变换的种类中要加上自己本身。
以下是我的第一版代码:
但这个代码是不通过的,因为题目中的数字范围较大,必须用高精度乘法,将每一个数字的情况相乘。
高精度乘法详解。
更改后的代码
方法二:
这道题是排列组合的乘法原理,但是每一位都有多少种可能呢,其实可以把这个问题转换成当前这位数字与多少个数字联通,这里处理是否联通用的是一种方法——Floyd变形
> Floyd模板
初始化:
这里将模板变形,将联通视为1,不连通视为0。
d[i][j] 表示从点 i 到点 j 是否联通。
AC代码