写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好深度优先搜索，为了用好暴搜应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1088 [NOIP2004 普及组] 火星人 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

共三行。
第一行一个正整数 N，表示火星人手指的数目（1 ≤ N ≤ 10000）。
第二行是一个正整数 M，表示要加上去的小整数（1 ≤ M ≤ 100）。
下一行是 1 到 N 这 N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式：

N 个整数，表示改变后的火星人手指的排列顺序。

每两个相邻的数中间用一个空格分开，不能有多余的空格。

输入样例：

5
3
1 2 3 4 5

输出样例：

1 2 4 5 3

提示：

对于 30% 的数据，N≤15。

对于 60% 的数据，N≤50。

对于 100% 的数据，N≤10000。

解题思路：

我们使用深度优先搜索的时候，

第一个要注意的点是搜索的顺序，

因为我们要保证，

我们写出的递归结构能够遍历所有情况，

在我们初学搜索的时候，我们一定要画一个递归搜索树观察，

递归非常抽象，画图能很好的帮助我们解题。（以上递归搜索的基本思路，多熟悉总是好的）

 接下来是具体思路：

我们根据题目要求，先画一个递归搜索树：

根节点：（以外星人有5个手指为例）

我们根据每个位置能放什么数据来进行搜索：

 数太多就不一一枚举了，

我们就画出最先搜索的路径，

找出大致的思路：

继续往下搜索：

 最后我们搜索出：

 然后题目给出了计数的起始位置，

让我们往后数3个，然后输出数完后的手指排列，

总结规律后：

手指排布大致如上图，

从12345的初始排列，搜索三步，到12453，然后输出。 

下面是代码实现：

代码：

//包好头文件
#include 
#include 
#include 
#include using namespace std;//外星人有手指 < 一万
const int N = 10010;int n, m;
int cnt;
int flag;//存数据
int arr[N];//存外星人手指的初始排列
int cmp[N];//判断数字有没有使用过
bool used[N];void dfs(int u)
{//如果已经找到，直接返回（剪枝）if(flag)return;if(u > n){//证明已经搜索了一次cnt++;if(cnt == m + 1){flag++;for(int i = 1; i <= n; i++){printf("%d ", arr[i]);}}return;}for(int i = 1; i <= n; i++){//如果是第一次搜索，直接从外星人手指的初始排列开始if(!cnt){i = cmp[u];}if(!used[i]){arr[u] = i;used[i] = true;dfs(u + 1);used[i] = false;//该位置改为没用过}}
}int main()
{scanf("%d %d", &n, &m);//存手指的初始排列for(int i = 1; i <= n; i++){scanf("%d", &cmp[i]);}dfs(1);return 0;
}

AC ！！！！！！！！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。