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;
}