所谓深搜(也叫回溯法)就是采用的是“一直往下走,走不通了就掉头,换一条路再往下走”
总结来说就是递归的枚举
一直往深处走,直到找到解或者走不下去为止
主要步骤:
1.构建一个递归函数,函数参数应该最起码包括题目需求使用的参数
2.找到边界,递归函数里首先列出递归结束的条件,即满足要求或者超出范围
3.接着列出所有可能移动或者变化的路径
void dfs(int step,...){
for(int i=1;i<=n;i++){
if(a[i]!=0){
b[sss+1]=i;
a[i]=0;//标记
ss(sss+1);
a[i]=1;//回溯
}
}