【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs（3）

写在前面：

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

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

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

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

题目：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 <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

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;
}