[数据结构与算法]深度优先搜索

浅谈深度优先搜索

所谓深度优先搜索，指的是搜索时，一直向下搜索，直到无路可走时，再返回到上一步，继续寻找新的出路。（详情可见《啊哈算法》P73）
例如，将1，2，3这三个数字全排列，可以先将第一位数字填好，然后填第二位数字，再然后填第三位，当填完第三位时，此时无路可走了，就返回到第二位数字，看有不有其它的数字能填第二位，如果没有，则继续往上回退。
图1显示了将1，2，3全排列时，深搜形成的搜索树，绿色箭头表示搜索的路径。

例题：XTUOJ1270

Unique Digit Number

题目描述

数位不同的数是指所有数位上的数码都不一样的数，比如“123”三个数码1,2,3，都不一样，所以是数位不同的数；但是“1232”中有两个相同的数码2，所以不是。请写一个程序，计算第几个符合条件的数是什么？

输入

每行输入一个整数 $n(1\le n\le 8877691)$。

样例输入

1
10
100
8877691

样例输出

0
9
120
9876543210

思路

这道题可以利用深度优先搜索算法，将二位数、三位数、…十位数的全排列全部找出来，存进数组。

C代码（900MS）

#include <stdio.h>
#include <string.h>
typedef __int64 IT64;
IT64 num_ans[8877692];  //用于保存找到的数字
int path[20];   //用于存储当前已经保存的全排列方案
int st[20];     //用于记录数字i是否已经被使用过，如果没被使用，则位0，被使用了则为1
int cnt;        //记录已经找到的答案个数
void dfs(int dis,int max_dis)
{
    if(dis==max_dis)  //当深搜到最大深度时，此时无路可走，说明已经找到全排列方案，将该方案存入数组
    {                 //这里是递归结束条件
        IT64 ans = 0;
        for(int i = 0 ; i < max_dis ; i++)
        {
            ans *= 10;
            ans += path[i];
        }
        num_ans[cnt++] = ans;
    }
    else
    {
        for(int num = 0; num <= 9 ; num++)
        {
            if(dis==0)   //特判，如果当前数字是第一位
            {
                if(num!=0 && !st[num])  //第一位不能为0，并且数字num没有被用过，才能继续递归
                {
                    st[num] = 1;        //将num标记为已经使用，这样往下递归时才不会出现重复数字
                    path[dis] = num;
                    dfs(dis+1,max_dis); //递归调用进入下一层
                    st[num] = 0;        //回溯时，应该归还已经使用的数字
                }
            }
            else
            {
                if(!st[num])
                {
                    st[num] = 1;        //将num标记为已经使用，这样往下递归时才不会出现重复数字
                    path[dis] = num;
                    dfs(dis+1,max_dis); //递归调用进入下一层
                    st[num] = 0;        //回溯时，应该归还已经使用的数字
                }
            }
        }
    }
}
int main()
{
    num_ans[cnt++] = 0;
    for(int u = 1; u <= 10 ; u++)
    {
        memset(st,0,sizeof st);   //按字节将st数组初始化为0
        dfs(0,u);                 //从0位开始深搜，最大搜索深度为n
    }
    IT64 n;
    while (scanf("%I64d",&n)!=EOF)
    {
        printf("%I64d\n",num_ans[n-1]);
    }
    return 0;
}

优化版（600MS）

在最后计算答案时进行了优化

#include <stdio.h>
typedef long long ll;
int cnt;
const int N = 8877700;
ll ans[N];
bool st[11];
inline void get_ans(int c, ll x);
int m;
int main()
{
    int n;
    ans[++ cnt] = 0;
    for(int i = 1; i < 11; ++ i){
        m = i;
        get_ans(0, 0);
    }
    while(scanf("%d", &n) != EOF){
        printf("%I64d\n", ans[n]);
    }
    return 0;
}
inline void get_ans(int c, ll x)
{
    if(c == m) return;
    for(int i = 0; i <= 9; ++ i){
        if(!st[i]){
            st[i] = true;
            ll g = (x << 3) + (x << 1) + i;
            if(c + 1 == m) ans[cnt ++] = g;
            if(i || c) get_ans(c + 1, g);
            st[i] = false;
        }
    }
}