DFS——C++

 dfs称为深度优先搜索是一种搜索算法。

具体算法讲解可以参考

https://blog.csdn.net/qq_63055790/article/details/133961017

例题：https://www.acwing.com/activity/content/problem/content/905/

#include<iostream>
using namespace std;
 
const int N=10;
int n;
int path[N];
bool st[N];
 
void dfs(int u)
{
    if(u==n)
    {
        //已经遍历完成
        for(int i=0;i<n;i++)
        {
            cout<<path[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    
    //未完成遍历
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            //恢复现场
            st[i]=false;
            path[u]=0;
        }
    }
}
 
int main()
{
    scanf("%d",&n);
    dfs(0);
    
    return 0;
}
 

例题：https://www.acwing.com/activity/content/problem/content/906/

#include<iostream>
using namespace std;
 
const int N=20;
char q[N][N];
bool con[N],du[N],ndu[N];
int n;
 
void dfs(int u)
{
    //边界结束情况
    if(u==n)
    {
        for(int i=0;i<n;i++)
        {
            for (int j=0;j<n;j++)
            {
                cout<<q[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
        return ;
    }
    
    //dfs赋值情况
    for(int i=0;i<n;i++)
    {
        if(con[i]!=1 && du[u+i]!=1 &&ndu[n+u-i]!=1)
        {
            //本行的本空可以填
            q[u][i]='Q';
            con[i]=du[u+i]=ndu[n+u-i]=1;
            dfs(u+1);
            //恢复现场
            q[u][i]='.';
            con[i]=du[u+i]=ndu[n+u-i]=0;
        }
    }
    
    
}
 
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            q[i][j]='.';
        }
    }
    
    dfs(0);
    
    return 0;
}