【DFS】产生数

【AC代码】 

#include <iostream>#include <cstdio>    //cstdio内有scanf()函数#include <cstring>    //cstring内有strlen()，memset()函数using namespace std;char num[32];    //字符型num数组用于输入做变换的巨大数字，它最多长达31位数int value[32]={0,1};    //value[1]设为1，既是乘法的开始，也是k=0这种情况的特殊结果int change[10][10];    //bool型的change[i][j]储存是否存在从i向j的变换int node[10];    //bool型的node[n]记录n这种变换结果是否被记录过int factor;    //factor记录每一位上可能的变换结果的总数，所有位上的factor相乘得到的即是所求的种类总数int multilen=1;    //变化的multilen反映的是当前高精度乘法结果的位数void DFS(int n)    //深度优先搜索一个数字{    int j;    if(node[n])    //如果node[n]为1，表示n这种变换结果已被记录过        return ;    //这时再向下搜索得到的也只是与之前重复的情况，这时候就不必再DFS，只要返回上一个DFS(调用该DFS的DFS)    else    //如果node[n]为0，表示n这种结果没有被记录过    {        node[n]=1;    //下面要记录它，将node[n]设为1        factor++;    //用全局变量factor因子记录这种情况    }    for(j=0;j<=9;j++)    //对于这10个数字j        if(change[n][j])    //如果存在从n向j的变换            DFS(j);    //那么我们就变换，搜索变换后的j}void multiply()    //高精度乘法，将因子factor乘入数组value[]{    int carry=0;    //carry表示每次乘法需要进位的数字    for(int i=1;i<=multilen;i++)    //从第一位到最后一位每一位都要乘    {        value[i]=value[i]*factor+carry;    //乘上因子factor，再加上上一位留下的进位数carry        carry=value[i]/10;    //carry再变成当前这一位对下一位产生的进位数        value[i]%=10;    //进位后，本位当然要对10取余    }    if(carry>0)    //如果到最后一位也乘完，还存在向下一位的进位数carry        value[++multilen]=carry;    //那么总位数就要增加一位，并将进位数放进去}int main(){    int k,i,j,length;    //length将储存num的长度    scanf("%s%d",num,&k);    //用scanf以跳过空格    memset(change,0,sizeof(change));    //change[i][j]为0时表示不存在从i向j的变换，先清零，再在后面赋1    while(k--)    {        cin>>i>>j;        change[i][j]=1;    //change[i][j]为1时表示存在从i向j的变换    }    length=strlen(num);    //这样做仅避免反复的求长度运算    for(i=0;i<length;i++)    //遍历输入数字的每一位数    {        memset(node,0,sizeof(node));    //每次将DFS节点数组node[]清空        factor=0;    //factor临时储存每一位的因子        DFS(num[i]-'0');    //对每一位深度优先搜索能做多少次变换        multiply();    //将因子相乘(高精度)放入数组value[]    }    for(i=multilen;i>=1;i--)        cout<<value[i];    //从高位到低位输出每一位数return 0;}