AKSZ-dfs

深搜

回溯
剪枝
连通性判断
搜索解空间，找最优解

#include<bits/stdc++.h>
using namespace std;
int n,k,a[15],vis[100005];
void dfs(int x){
	if(x>n){
		for(int i=1;i<=n;i++){
			cout<<a[i]<<" ";
		}
		puts("");
		
		return ;
	}
	for(int i=1;i<=k;i++){
		if(!vis[i]){
			vis[i]=1;
			a[x]=i;
			dfs(x+1);
			vis[i]=0;//有大用，防重复又防bug
		}
		
	}
}
int main(){
	cin>>k>>n;
	dfs(1); 
	return 0;
}

深搜加剪枝

using namespace std;
int n,a,b,k[205],ans=-1,vis[205];
void dfs(int l,int x){
	if(l==b){
		if(ans==-1){
			ans=x;
			return ;
		}
		else{
			ans=min(ans,x);
			return;
		}
		
	}
    if(ans!=-1&&x>ans){
        return;
    }
	if(l+k[l]<=n&&!vis[l+k[l]]){
        vis[l+k[l]]=1;
        dfs(l+k[l],x+1);
        vis[l+k[l]]=0;
    }
	if(l-k[l]>=1&&!vis[l-k[l]]){
        vis[l-k[l]]=1;
        dfs(l-k[l],x+1);
        vis[l-k[l]]=0;
    }
}
int main(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>k[i];
	dfs(a,0);
	cout<<ans;
	return 0;
}

经典八皇后

#include<bits/stdc++.h>
using namespace std;
int n,cnt,col[15],vis[15];
void dfs(int x){
	if(x>n){
		if(cnt<3){
			for(int i=1;i<=n;i++){
				cout<<col[i]<<" ";
			}
			puts("");
		}
		cnt++;
		return ;
	}
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			int flag=1;
			for(int j=1;j<x;j++){
				if(x-i==j-col[j]||x+i==j+col[j]){
					flag=0;
					break;
				}
			}
			if(flag){
				col[x]=i;
				vis[i]=1;
				dfs(x+1);
				vis[i]=0;
			}
		}
	}
}
int main(){
	cin>>n;
	dfs(1);
	cout<<cnt;
	return 0;
}

排列组合

加法原理

选$a~z+0~9=26+10=36$

乘法原理

$$20选3=20*19*18$$