深度优先搜索应用.docx
版权申诉
184 浏览量
2021-11-23
12:41:39
上传
评论
收藏 336KB DOCX 举报
深度优先搜索应用
例题 1：字母排列(主题库 2698)
给定一个由不同的小写字母组成的字符串，输出这个字符串的所有全排列。
我们假设对于小写字母有 'a' < 'b' < ... < 'y' < 'z'，而且给定的字符串中的字母已经按照从小到大的顺序排列。
输入格式
输入有多组数据，每行一组，每组数据是一个由小写字母组成的字符串，已知字符串的长度在 1 到 6 之间。
输出格式
输出这个字符串的所有排列方式，每行一个排列。要求字母序比较小的排列在前面。字典序如下定义：
已知 S = s_1s_2...s_k , T = t_1t_2...t_kS=s1s2...sk,T=t1t2...tk，则 S < TS<T 等价于，存在 p (1 <= p <= k)p(1<=p<=k)，使得 s_1 =
t_1, s_2 = t_2, ..., s_{p - 1} = t_{p - 1}, s_p < t_ps1=t1,s2=t2,...,sp−1=tp−1,sp<tp 成立。
注意每组样例输出结束后接一个空行。
样例输入
xyz
Copy
样例输出
xyz
xzy
yxz
yzx
zxy
zyx
Copy
解题思路：详细解题思路见代码解析。
#include<bits/stdc++.h>
using namespace std;
char a[10];
int n,use[10];
string s;
void print()
{
for(int i=1;i<=n;i++)
{
cout<<a[i];
}
cout<<endl;
}
void dfs(int cur)
//当前位置
{
if(cur>n)
//当前位置大于 n,结束
剩余27页未读，继续阅读
资源评论
