网站建设 ader,网页微信手机登录,遂宁移动端网站建设,如何自己创建网站【解题思路】 1、将数字拆分保存在数组中#xff0c;而后转换每一位。 2、将数字变化规则保存在x、y两个一维数组中#xff0c;x[i]到y[i]是一种转换规则。 3、从n的初始值开始搜索#xff0c;对n做数字拆分#xff0c;将拆分后的各位数字保存在一个数组中。针对数组中的每…【解题思路】 1、将数字拆分保存在数组中而后转换每一位。 2、将数字变化规则保存在x、y两个一维数组中x[i]到y[i]是一种转换规则。 3、从n的初始值开始搜索对n做数字拆分将拆分后的各位数字保存在一个数组中。针对数组中的每位数字看能否通过转换规则将该数字转换为另一个数字。如果可以那么做一次转换将该数组通过数字组合变为一个整数通过vis数组判断该整数是否出现过。如果出现过那么略过。如果没出现过将该整数在vis数组中设为“出现过”产生的数字个数加1而后从该整数开始再次进行搜索。
输入样例分析 234 2 2 5 3 6 【参考代码】
广搜
#includebits/stdc.h
using namespace std;
#define K 20
int n, k, ct, x[K], y[K], arr[5], ai;
bool vis[10001];
void toArr(int num)//将整数num进行数字拆分结果保存在数字数组arr中。包括num为0的情况
{ai 0;int a num;do{arr[ai] a % 10;a / 10;}while(a 0);
}
int toNum()//将数字数组arr保存的数字转为整型数字
{int num 0;for(int i ai; i 1; --i)num num * 10 arr[i];return num;
}
void bfs()
{queueint que;vis[n] true;ct 1;que.push(n);while(que.empty() false){int u que.front();que.pop();toArr(u);//将u转为数字数组arr for(int i 1; i ai; i)//遍历arr中的每一位 {for(int j 1; j k; j)//遍历每条规则 {if(arr[i] x[j]){arr[i] y[j];int newNum toNum();if(vis[newNum] false){vis[newNum] true;ct;que.push(newNum);}arr[i] x[j];//还原 }}}}
}
int main()
{cin n k;for(int i 1; i k; i)cin x[i] y[i];bfs();cout ct;return 0;
}深搜
#include bits/stdc.h
using namespace std;
int n, k, x[20], y[20], arr[5], ai, ct;
bool vis[10000];
void toArr(int num)//将整数num进行数字拆分结果保存在数字数组arr中。包括num为0的情况
{ai 0;int a num;do{arr[ai] a % 10;a / 10;}while(a 0);
}
int toNum()//将数字数组arr保存的数字转为整型数字
{int num 0;for(int i ai; i 1; --i)num num * 10 arr[i];return num;
}
void dfs(int num)
{int temp, newNum;for(int i 1; i ai; i){for(int j 1; j k; j)//如果存在替换arr[i]的规则 {if(arr[i] x[j]){arr[i] y[j];newNum toNum();//合成得到新的整数 if(vis[newNum] false)//如果新的整数nweNum没出现过 {vis[newNum] true;//将newNum标记为出现过 ct;//数字出现的个数加1 dfs(newNum);}arr[i] x[j];//还原 }}}
}
int main()
{cin n k;for(int i 1; i k; i)cin x[i] y[i];toArr(n);vis[n] true;ct 1;dfs(n);cout ct;return 0;
}
