dfs的模板

注意bool判断是否走过这个点并注意回溯的处理。
注意条件判断和边界问题。

//边界判断即剪枝
if(chk()) return;
if(over(BianJie)) return;

if(bool = false)//未搜索过
  bool = true;
  //赋值或纪录
  dfs(n + 1);
  //复原赋值即回溯
  bool = false;

dfs 小例题

题目
给定一个整数 n，将数字 1～n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。

ac代码

#include<iostream>

using namespace std;

const int N  = 1e6;

bool chk[N];
int res[N];
int n;

void dfs (int num){
    if(num == n){
        for(int i = 0; i < num;i ++ ) cout<<res[i]<<‘ ‘;
        cout<<endl;
        return;
    }
    
    for(int i = 1;i <= n;i ++){
        if(!chk[i]){
            chk[i] = true;
            
            res[num] = i;
            
            dfs(num + 1);
            
            chk[i] = false;
        }
    }
}

int main(){
    cin >> n;
    
    dfs(0);
    
    return 0;
}

n皇后问题题解

#include<iostream>

using namespace std;

const int N = 20;

int n;
char res[N][N];
bool col[N],dg[N],udg[N];

void dfs(int u){
    if( u == n ){
        for(int i = 0;i <n ;i ++ )puts(res[i]);
        cout<<endl;
        return;
    }
    
    for(int i = 0;i < n;i ++){
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){
            col[i] = dg[u + i] = udg[n - u + i] = 1;
            res[u][i] = ‘Q‘;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = 0;
            res[u][i] = ‘.‘;
        }
    }
}

int main(){
    cin>>n;
    
    for(int i = 0 ;i < n;i ++)
        for(int j = 0;j < n;j ++)
            res[i][j] = ‘.‘;
            
    dfs(0);
    
    return 0;
}

小tips

• 当处在第i列第u行时，正对角线下标为u + i，反对角线为n - u + i;

基础算法学习--dfs和bfs

原文：https://www.cnblogs.com/Xuuxxi/p/14619465.html