搜索与图论（1）

闲时记录 / 2023-05-07 / 原文

DFS深度优先遍历

回溯、剪枝、对应一条搜索树

全排列问题

#include <iostream>
#include <algorithm>
using namespace std ;

const int N = 10 ; 

int n; 
int path[N] ; // 存方案的
bool st[N] ; //true表示当前数组已被用过

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 ; //恢复现场
        }
}

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

n-皇后问题

#include <iostream>
#include <algorithm>
using namespace std ;
const int N = 20 ; 
int n; 
char g[N][N] ; // 存方案的
bool l[N], zx[N], fx[N] ; //列 正对角线（左上到右下） 反对角线

void dfs(int u)
{
    if( u==n ) { // 摆了n个皇后，满足题意
        for(int i=0; i<n ; i++) puts(g[i]); 
        cout<<endl; 
        return ; 
    }
    
    for(int i=0; i<n; i++) // 枚举第u行 皇后放在哪一列
        if( !l[i] && !zx[u+i] && !fx[n-u+i] ) // 没用过 坐标转化参考 y=x+b 则 b=y-x，不能是负数 改成 b=y-x+n 
        {
            g[u][i] = 'Q' ; 
            l[i] = zx[u+i] = fx[n-u+i] = true ; // 都标为用过了  y=-x+b 则 b = x+y 
            dfs(u+1) ; 
            l[i] = zx[u+i] = fx[n-u+i] = false ; //恢复现场
            g[u][i] = '.'  ;
        }
}

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