题解 P1706 【全排列问题】

· · 题解

算法解析

DFS，对楼上的回溯+剪枝进行详解。

我们以N=3为例，构造一棵搜索树（或说是状态树）来进行搜索。

同时构造出三个格子，用来存放搜索树中的结果。

现在，我们从第一格开始搜索。第一格填1的搜索树如下：

所以N=3的情况下，第一格填1的排列情况共有两种123,132.

第一格填2的搜索树如下：

所以N=3的情况下，第一格填2的排列情况共有两种 213,231.

如果你看懂了，请你自己画画第一格填3的搜索树。

程序实现

我们总结一下在上一部分中的思路在程序中如何实现。

先定义两个数组，一个是用来存放解的，一个是用来标记该数是否用过。

我们可以先写一个用于打印的函数print()，每当深搜时找到一个符合条件的解时，则print()一下，输出这个解（注意题目输出要求）。

接下来就是写深搜的函数了。主要思路：先判断格子是否填满了，如果填满，则print()一下。

如果没有填满，则开始循环，在循环中先判断当前填的数是否用过，如果没有，则填入，搜索下一格。

程序实现如下：

#include<bits/stdc++.h>
using namespace std;
int n,pd[100],used[100];//pd是判断是否用过这个数
void print()//输出函数
{
    int i;
    for(i=1;i<=n;i++)
    printf("%5d",used[i]);//保留五位常宽
    cout<<endl;
}
void dfs(int k)//深搜函数，当前是第k格
{
    int i;
    if(k==n) //填满了的时候
    {
        print();//输出当前解
        return;
    }
    for(i=1;i<=n;i++)//1-n循环填数
    {
        if(!pd[i])//如果当前数没有用过
        {
            pd[i]=1;//标记一下
            used[k+1]=i;//把这个数填入数组
            dfs(k+1);//填下一个
            pd[i]=0;//回溯
        }
    }
}
int main()
{
    cin>>n;
    dfs(0);//注意，这里是从第0格开始的！
    return 0;
}