特别的DFS，pony.ai一面出的题目：给定两个正整数a, b (<= 10^18)。可以置换a数中每个数位的位置，求能够得到的比b小的最大的数。不允许前导0
注意这里递归和回溯的次数，时间复杂度是O(n)
DFS
DFS是一种枚举所有完整路径来遍历所有情况的搜索方法。最佳实现方法：递归。当然也可以自建栈代替递归，但是往往较麻烦，递归相当于调用系统栈，本质一样。
其中一类DFS问题的解法：给定一个序列，枚举这个序列所有的子序列（可以不连续）。
例1：01背包问题的DFS解法
对于每一个物品，DFS有两个分支，遍历所有的分支。当选择物品的综合超过背包容量，说明该路径走入了死胡同，则需要回到最近的一个岔道口。核心代码如下。
注意到每件物品都有两种选择，故时间复杂度是O(2^n)，优化的点有，在sumW+W[index]小于V时再进入迭代
void DFS(int index,int sumW,int sumC){
if(index==n){已经完成物品选择的处理}
DFS(index+1,SumW,sumC);//不选第index件物品
DFS(index+1,SumW+W[index],sumC+C[index]);//选第index件物品
}
例2：N个整数中选择K个数的和等于X的所有方案，冲突的话选择其平方和最大的一个。用向量记录添加进方案当中的元素，进入DFS下一步的时候将元素入栈。
void DFS(int index,int nowK,int sum,int sumSqu){
if(nowk==k&&sum==x){
if(sumSqu>maxsumSqu){
maxsumSqu=sumSqu;
ans=tmp;
}
return;
}
if(index==n||nowk>k||sum>x)return;
//在DFS递归前和递归后分别设置状态和取消状态，是回溯的典型特征。
//选择index元素
tmp.push_back(A[index]);
DFS(index+1,nowk+1,sum+A[index],sumSqu+A[index]*A[index]);
tmp.pop_back();
//不选index
DFS(index+1,nowk,sum,sumSqu);
}
阿哈算法：将问题形象化为降1-n编号的扑克牌放入n个盒子中，用book[]数组记录该数字已经放过。
#define maxn 100
int n;
vector<int> book(maxn,0),vec(maxn);
//step表示现在放第step个盒子，n表示全排列总数
void DFS(int step){
if(step>n)return;
for(int i=1;i<=n;i++){
if(!book[i]){
book[i]=1;
vec[step]=i;
DFS(step+1);
book[i]=0;//DFS关键一步，收回刚放的牌
}
}
}
DFS的伪代码如下：
dfs(int step){
判断边界
尝试每一种可能{
标记数组记录该次选择
DFS(step+1)
取消标记数组的选择
}
返回
}
DFS和BFS配合vis数组，都可以用来求解连通域的个数
邓书改进迭代版本，原版见cppSTL。
/*书中写的虽然代码短，但是不好理解是如何实现的，我根据自己的思路写的这个，思路很清晰
感觉没必要为了少几行代码将思路搞得很不一般，就像归并排序一样，末尾有元素剩余单独处理就好
循环不变性：初始进入循环的是有效元素，每次根据在栈中有没有找到相同元素判断是否可以入栈
入栈情况：
当栈满时，意味着找到了一种结果，记录并输出。然后y不变，x++，当然，如果x也到了最大值，就要回溯（此时的回溯必定可以找到有元素的x非最大值，因为此前的元素各不相同）
栈不满时，y++,x=0
不入栈的情况：
x没达到最大值，x++即可
x达到了最大值，回溯，回溯到的元素不是第一行最大值时，x++即可，否则，退出循环。这是循环退出的唯一条件
*/
#include<iostream>
#include"string.h"
using namespace std;
//试探回溯法解八皇后问题
struct Queen{
int x,y;
Queen(int xx=0,int yy=0):x(xx),y(yy){}
Queen(Queen& b){x=b.x;y=b.y;}
bool operator==(Queen b){
return x==b.x||y==b.y||x+y==b.x+b.y||x-y==b.x-b.y;
}
};
int find(Queen* solu,Queen& q,int lo,int hi){//查找范围[lo,hi),找不到返回hi
for(int i=lo;i<hi;i++){
if(solu[i]==q)return i;
}
return hi;
}
void placeQueens(int N){
Queen* solu=new Queen[N];int top=0;
//用数组模拟栈,入栈solu[top++]=q;出栈q=solu[--top];
int nsolu=0;//记录满足条件的答案的数量
Queen q(0,0);
solu[top++]=q;q.y++;
//不断的试探回溯,忒休斯的绳索是栈，入栈是进一步，出栈是退一步
while(1){
//循环不变性：初始进入循环的q是有效的
//首先判断q应该前进（入栈）还是后退（出栈）
int r=find(solu,q,0,top);
if(r==top){//前进
solu[top++]=q;
//判断是否满足题意，确保下一次循环内的元素满足条件
if(top==N){//得到满足题意的一个结果
nsolu++;
for(int i=0;i<N;i++)printf("%d ",solu[i].x);
printf("\n");
//得到下一个有效点，回溯，以进入下一次循环
while(q.x==N-1&&top>0)q=solu[--top];
q.x++;
}else{
q.y++;q.x=0;
}
}else{
if(q.x==N-1){//说明此种情况不符合条件，应回溯
while(q.x==N-1&&top>0)q=solu[--top];
if(top==0&&q.x==N-1)break;
else q.x++;
}else{
q.x++;
}
}
}
cout<<nsolu;
}
int main(){
//freopen("d:\\CodeBlockSpace\\input.txt","r",stdin);
placeQueens(8);
return 0;
}
递归版本
class Solution {
public:
vector<vector<int> > ans;
vector<vector<string> > strans;
vector<int> tmp;
vector<bool> vis;
bool conflicted(vector<int>& tmp,int x){
for(int i=0;i<tmp.size();i++){
if(x==tmp[i])return false;
if(tmp.size()+x==i+tmp[i])return false;//斜对角线
if(tmp.size()-x==i-tmp[i])return false;//正对角线
}
return true;
}
void solve(int step,int n){
if(step==n){
ans.push_back(tmp);
//cout<<ans[0][0]<<endl;
return;
}
for(int i=0;i<n;i++){
if(!vis[i]){
if(conflicted(tmp,i)){
vis[i]=true;
tmp.push_back(i);
solve(step+1,n);
tmp.pop_back();
vis[i]=false;
}
}
}
}
vector<vector<string>> solveNQueens(int n) {
vis.resize(n,false);
fill(vis.begin(),vis.end(),false);
int step=0;
solve(step,n);
for(int i=0;i<ans.size();i++){
vector<string> strtmp;
for(int j=0;j<ans[i].size();j++){
string s;
for(int k=0;k<n;k++){
if(ans[i][j]==k)s+="Q";
else s+=".";
}
strtmp.push_back(s);
}
strans.push_back(strtmp);
}
return strans;
}
};
//思路相同，但是相对更加简单点的方法
//8皇后问题
#define N 8
vector<int> v(N,0);//表示每一行中皇后的位置
int cnt=0;
bool conflict(int step){
_for(i,0,step){
if(v[i]==v[step]||v[i]-i==v[step]-step||v[i]+i==v[step]+step)
return true;
}
return false;
}
void DFS(int step){
if(step==N){
_for(i,0,N){
printf("%d ",v[i]);
}
printf("\n");
cnt++;
return;
}
_for(i,0,N){
v[step]=i;
if(!conflict(step))
DFS(step+1);
}
}
int main(int argc, char** argv) {
int step=0;
DFS(step);
cout<<cnt<<endl;
return 0;
}
BFS
相比DFS用递归系统栈实现，BFS用自建队列实现。
void BFS(int s){
queue<int> q;
q.push(s);
while(!q.empty()){
取出队首元素top
访问队首元素top
将队首元素出队
将top的下一层未入队的节点入队，并标记为已入队
}
}
用BFS求m*n矩阵中连通域的个数。（注意，这里可以用x[4],y[4]枚举四个方向）
迷宫中求S到T的最少步数，用BFS，并且记录节点深度（S深度为0，然后每一层深度是上一层+1）
队中元素时是结构体的注意事项，如果直接在队列汇中存储结构体，那么，对队列中的副本的修改不会影响原元素。这就是说，如果需要对队列中的元素进行修改，最好在队列中存储元素的编号而非元素本身，如果数组的话则是下标。
BFS判断是否是满二叉树，将空节点也入队，如果出队的是空节点，而此时已经出队了n个元素，则是满二叉树
m*n图中的最短路径问题，都可以用BFS来最方便实现