DFS搜索
例一:N皇后问题
N*N的方格放置N个皇后,使不互相攻击(不在同一行,列,斜线)
求有多少可行案例
#include<iostream> #include<cmath> int n,x[15],cnt=0; //x[i]中i表示行数,值表示列数,比构造二维数组更方便 using namespace std; bool check(int h) //check函数表判断当前位置是否符合规则 { for(int i=1;i<h;i++) { //判断是否位于同一行或同一斜线 if(x[i]==x[h]||abs(h-i)==abs(x[h]-x[i]))//行,列相减的值相同表示斜率相同,表示在同一斜线上 return 0; } return 1; } bool pd(int h) //pd函数表示判断单次搜索是否到底,若到底则返回 { if(h>n) return 1; else return 0; } void dfs(int h) //dfs搜索,h表示行数 { if(pd(h)) //若到底 { cnt++; //可行案例+1 return; //回溯 } else{ //若没到底 for(int i=1;i<=n;i++) //搜索每一行的位置(每一列) { x[h]=i; //放在当前位置 if(check(h)) //判断当前位置是否符合条件 dfs(h+1); //若符合,搜索下一行 else continue; //若不符合,搜索此行的下一个值 } } } int main() { cin>>n; dfs(1); //从第一行开始 cout<<cnt<<endl; return 0; }
例二:DFS实现组合型枚举
对于每一个数,都有选和不选两种状态。
//用dfs实现组合型枚举 #include<iostream> #include<vector> using namespace std; int m,n; vector<int> number; void dfs(int x) { //剪枝 if(number.size()>m||number.size()+n-x+1<m) //超过m或加上剩下所有不满m,直接返回 return; if(x>n) //搜索到底部 { for(int i=0;i<number.size();i++) cout<<number[i]<<" "; cout<<endl; return; } number.push_back(x);//x选 dfs(x+1); //看下一个 number.pop_back(); //x不选 dfs(x+1); //看下一个 } int main() { cin>>n>>m; dfs(1); return 0; }