首页 > 代码库 > JSK424:置换的玩笑(搜索)
JSK424:置换的玩笑(搜索)
小蒜头又调皮了。这一次，姐姐的实验报告惨遭毒手。
姐姐的实验报告上原本记录着从 1 到 n 的序列，任意两个数字间用空格间隔。但是“坑姐”的蒜头居然把数字间的空格都给删掉了，整个数字序列变成一个长度为 1 到 100 的且首部没有空格的数字串。
现在姐姐已经怒了，蒜头找你写个程序快点把试验数据复原。
输入
输入文件有一行，为一个字符串——被蒜头搞乱的实验数据。
字符串的长度在 1 到 100 之间。
输出
输出共一行，为姐姐的原始测试数据—— 1 到 n 的输出。
任意两个数据之间有一个空格。
如果有多组符合要求的正确解，输出其中任意一组即可。
样例输入
4111109876532
样例输出
4 1 11 10 9 8 7 6 5 3 2
Solve:
蜜汁DFS,考虑的东西有点多,但是反正就是个生成全排列啦,就是1~n内的每个数都出现且只出现一次,当然这个n也是在搜完之后才找出来了
Code:
1 #include <bits/stdc++.h> 2 using namespace std; 3 char data[666] = {‘\0‘}; 4 bool vis[666] = {0}; 5 int ans[666] = {0}; 6 int len = 0; 7 bool flag = 0; 8 int ml; 9 void Dfs(int pos , int num)10 {11 if(flag)12 return ;13 if(pos >= len)14 {15 int chu[110] = {0};16 int mx = -1;17 for(int i = 0 ; i < num ; ++i)18 {19 mx = max(mx , ans[i]);20 chu[ans[i]] = 1;21 }22 bool gao = 1;23 for(int i = 1 ; i <= mx ; ++i)24 {25 if(!chu[i])26 {27 gao = 0;28 break;29 }30 }31 if(gao)32 {33 for(int i = 0 ; i < num ; ++i)34 printf("%d " , ans[i]);35 printf("\n");36 flag = 1;37 }38 return ;39 }40 int next = data[pos] - 48;41 if(!vis[next])42 {43 vis[next] = 1;44 ans[num] = next;45 Dfs(pos + 1 , num + 1);46 vis[next] = 0;47 }48 if(pos + 1 < len)49 {50 next = (data[pos] - 48) * 10 + (data[pos + 1] - 48);51 if(!vis[next])52 {53 vis[next] = 1;54 ans[num] = next;55 Dfs(pos + 2 , num + 1);56 vis[next] = 0;57 }58 }59 return;60 }61 int main()62 {63 scanf(" %s" , data);64 len = strlen(data);65 Dfs(0 , 0);66 }
JSK424:置换的玩笑(搜索)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。