浅析深度优先搜索1

kkrcffTr3 · 2022-11-27 11:13:27 · 个人记录

深度优先搜索

• 例题

有三个字母，三个空位（如下图）

求有多少种排列方法

这道题，首先我们想到的是枚举：

for (char i='a';i<='c';i++){
    for (char j='a';j<='c';i++){
        for (char k='a';k<='c';k++){
            cout<<i<<j<<k;
            cout<<endl;
        }
    }
}

这样很OK，但是如果是n个空呢？

让我们想想，不定量，那只能用递归了呀

void dfs(int d){
    for (char i='a';i<=s;i++){
        a[d]=i;
        dfs(d+1);
    }
}

那边界呢？

边界肯定是d>n呀

void dfs(int d){
    if (d>n){

        return ;
    }
    for (char i='a';i<=s;i++){
        a[d]=i;
        dfs(d+1);
    }
}

那输出呢？

void dfs(int d){
    if (d>n){
        for(int i=1;i<=n;i++){
            cout<<a[i];
        }
        cout<<endl;
        return ;
    }
    for (char i='a';i<=s;i++){
        a[d]=i;
        dfs(d+1);
    }
}

ok，递归部分已经OK了

main（）大家都会写吧

全代码：

#include <bits/stdc++.h>
using namespace std;
int n;
char s;
char a[100];
void dfs(int d){
    if (d>n){
        for(int i=1;i<=n;i++){
            cout<<a[i];
        }
        cout<<endl;
        return ;
    }
    for (char i='a';i<=s;i++){
        a[d]=i;
        dfs(d+1);
    }
}
int main(){
    cin>>n>>s;
    dfs(1);
    return 0;
}