dfs搜索算法，将要搜索的目标分为若干层，每层基于前几层的状态进行决策直到达到目标状态。
全排列问题。在回溯时清空标记。
void dfs(int x){
if(x==n+1){
for(auto x:ans)printf("%5d ",x);
puts("");
return;
}
for(int i=1;i<=n;i++){
if(vis[i])continue;
vis[i]=1;
ans.push_back(i);
dfs(x+1);
vis[i]=0;
ans.pop_back();
}
}
N皇后问题。维护四个标记，行、列、两条对角线。
void dfs(int x){
if(x==n+1){
if(++tot<4){
for(int i=1;i<=n;i++)cout<<a[i]<<' ';
cout<<'\n';
}
return;
}
for(int i=1;i<=n;i++){
if(b[i]||c[x+i]||d[x-i+n])continue;
a[x]=i;/*行*/
b[i]/*列*/=c[x+i]/*左下到右上对角线*/=d[x-i+n]/*左上到右下对角线*/=1;
dfs(x+1);
b[i]=c[x+i]=d[x-i+n]=0;
}
}
从给定集合中选取k个数，问和为素数的方案数。单独求素数要对2进行特判，先对a进行排序来去重。
void dfs(int x,int sum,int la){
if(x==k){
ans+=isprime(sum);
return;
}
for(int i=la;i<=n;i++)dfs(x+1,sum+a[i],i+1);
}
sort(a+1,a+1+n);
dfs(0,0,1);
体积n*pai的m层蛋糕，从下往上高度h和半径r必须递减，外表面积q，问s=q/pai的最小值。记录每层最小表面积和最小体积，倒序枚举每层的高度和半径。当前最小面积大于ans，或体积超出限制，或由体积得到的表面积大于ans则退出。
void dfs(int x/*第x层*/,int s/*表面积*/,int v/*体积*/,int lh/*上一层的高度*/,int lr/*上一层的半径*/){
if(!x){/*搜索完成*/
if(v==n)ans=min(ans,s);/*符合要求更新*/
return;
}
if(s+(n-v)/lr>ans||v+miv[x]>n||s+mis[x]>ans)return;/*三种剪枝*/
for(int i=lr-1;i>=x;i--){/*枚举半径*/
if(x==m)s=i*i;/*最底层直接累加*/
int re=min(lh-1,(n-v-miv[x-1])/(i*i));/*枚举高度*/
for(int j=re;j>=x;j--)dfs(x-1,s+2*i*j,v+i*i*j,j,i);
}
}
inline void main(){
cin>>n>>m;
for(int i=1;i<=m;i++)miv[i]=miv[i-1]+i*i*i,mis[i]=mis[i-1]+2*i*i;
dfs(m,0,0,n,sqrt(n));
cout<<(ans==INT_MAX?-1:ans);
}
一些同长小木棍被随意砍成几段，每段长不超过50，问原始木棍的最小可能长度。首先预处理总长度，保证答案可以被整除，从大到小长度递减枚举，拼接时从已用的木棍长度开始dfs，若某组拼接不成立且已拼接长度为0或当前长度+刚才枚举的长度之和为最终答案时，直接跳出循环，因为继续枚举更小值同样凑不完。
void dfs(int x,int sum,int goal,int p){
if(!x)cout<<goal,exit(0);/*枚举完了所有的木棍得到答案*/
if(sum==goal)return dfs(x-1,0,goal,ma),void();/*恰好拼出目标长度，dfs下一个木棍*/
for(int i=p;i>=mi;i--){/*倒序枚举长度*/
if(!buc[i]||i+sum>goal)continue;
buc[i]--;
dfs(x,sum+i,goal,i);
buc[i]++;
if(!sum||sum+i==goal)return;/*剪枝*/
}
}
inline void main(){
cin>>n;mi=N;
while(n--){
int a;cin>>a;
if(a>50)continue;
buc[a]++;tot+=a;ma=max(ma,a);mi=min(mi,a);
}
for(int i=ma,re=tot>>1;i<=re;i++)if(tot%i==0)dfs(tot/i,0,i,ma);
cout<<tot;/*原始长度超过一半就只能拼成一根*/
}
bfs搜索算法，用队列记录要处理的节点，vis[]记录是否访问过，初始时起点入队，每次取出队首，将相邻节点标记并入队，直到队列为空。
给定n*n网格，给出马的起点和终点，问最少步数。bfs即可，注意这里网格范围是[0,n-1]。
int bfs(int x,int y){
memset(vis,0,sizeof(vis));
vis[x][y]=1;
queue<node>q;
q.push((node){x,y,0});
while(!q.empty()){
int x=q.front().x,y=q.front().y,s=q.front().s;
q.pop();
if(x==edx&&y==edy)return s;
for(int i=0;i<8;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx<0||ty<0||tx>=n||ty>=n||vis[tx][ty])continue;
q.push((node){tx,ty,s+1});
vis[tx][ty]=1;
}
}
}
给定目标局面，上有黑白马，一个空格，询问一个局面能够在15步内达到目标局面，能则输出最小步数。IDA*搜索，估价函数设定为最有情况下达到目标的最少步数，即黑白棋子不同的数量，让马移动很麻烦，于是考虑让空格取移动。
inline int evaluate(int re=0){/*估价函数，最有情况是黑白棋子不同的数量*/
for(int i=1;i<=5;i++)for(int j=1;j<=5;j++)re+=a[i][j]!=b[i][j];
return re;
}
void IDAStar(int dep,int x,int y,int maxdep){
if(dep==maxdep){
if(!evaluate())flag=1;/*搜索成功*/
return;
}
for(int i=0;i<8;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx<1||ty<1||tx>5||ty>5)continue;
swap(a[x][y],a[tx][ty]);
if(evaluate()+dep<=maxdep)IDAStar(dep+1,tx,ty,maxdep);
swap(a[x][y],a[tx][ty]);
}
}
flag=false;
for(int maxdep=1;maxdep<=15;maxdep++){/*迭代加深深度上限*/
IDAStar(0,stx,sty,maxdep);
if(flag){
cout<<maxdep<<'\n';
break;
}
}
if(!flag)cout<<"-1\n";
给定方程sum(i=1->n)(k[i]*x[i]^p[i])=0，x[i]属于[1,m]，求方程解的个数,m<=150,n<=6。折半搜索，即双向dfs，要求搜索各项不能互相干扰，搜索状态可逆，即一个状态可以从两个方向得到，最后对答案序列进行合并，可以使用排序后二分、哈希表、双指针等。
void dfs(int l,int r,int sum,int*a,int&c){
if(l>r)return a[++c]=sum,void();
for(int i=1;i<=m;i++)dfs(l+1,r,sum+k[l]*po(i,p[l]),a,c);
}
inline void main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>k[i]>>p[i];
int mid=n>>1;
dfs(1,mid,0,a,ca);
dfs(mid+1,n,0,b,cb);
sort(a+1,a+1+ca);/*首先进行排序*/
sort(b+1,b+1+cb);
int l=1,r=cb;
for(;l<=ca&&r>=1;l++){
while(a[l]+b[r]>0)r--;/*找到满足条件的第一个位置，若不存在则下面while的y为0，答案不会更新*/
int x=1/*左边个数初始化是1*/,y=0/*右边初始化0，因为合法条件在右边判断*/,j=r;
while(j&&a[l]+b[j]==0)j--,y++;/*计算右边满足要求的个数*/
while(l<ca&&a[l]==a[l+1])l++,x++;/*计算左边满足要求的个数*/
ans+=x*y;/*乘法原理统计答案*/
}
cout<<ans;
}
//排序二分合并答案
sort(a+1,a+1+ca);
for(int i=1;i<=cb;i++)ans+=(upper_bound(a+1,a+1+ca,-b[i])-lower_bound(a+1,a+1+ca,-b[i]));
//hash表写法
void dfs(int l,int r,int sum,bool f){
if(l>r){
if(f){
if(mp.find(-sum)!=mp.end())ans+=mp[-sum];
}
else mp[sum]++;
return;
}
for(int i=1;i<=m;i++)dfs(l+1,r,sum+k[l]*po(i,p[l]),f);
}
记忆化搜索算法，记录已经遍历过的信息从而避免重复遍历，也是动态规划常见的实现方式，与递推类似。
普通01背包。查完一个状态后记录下来，再访问时直接利用，无需再次计算，空间换时间。
int dfs(int x,int v){
if(mp.find({x,v})!=mp.end())return mp[{x,v}];
if(x==n+1)return mp[{x,v}]=0;
int a=dfs(x+1,v)/*不选x*/,b=-1e7/*选x*/;
if(v>=c[x])b=dfs(x+1,v-c[x])+w[x];/*可以选x，剩余体积减少并更新贡献*/
return mp[{x,v}]=max(a,b);/*两者取min*/
}
A搜索算法，在图形平面上，对于多个节点的路径求出最低通过成本的算法。g,开始到当前的花费。g,估计的开始到当前的花费，由于bfs，一定有g=g。h,当前到结束的花费。h,估计的当前到结束的花费。f,开始到当前再到结束的总花费,f=g+h。f,估计的开始到当前再到结束的总花费,f=g+h=g+h*。
A算法根据f从小到大遍历搜索节点，在h<=h的前提下h尽量大。
k短路。先求出所有点到终点的距离dis[i]，d函数就是当前点的dis值，起点到当前点花费为t，则f=d*+g=dis+t。
#include<vector>
#include<queue>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<climits>
using namespace std;
const int N=1e6+6;
int dis[N],n,m,k;
bool in[N];
vector<pair<int,int>>v[N],v0[N];
struct node{
int pos,len;
inline bool friend operator<(const node&a,const node&b){
return a.len+dis[a.pos]>b.len+dis[b.pos];
}
};
namespace JRC{
void spfa(int s){
queue<int>q;
memset(dis,0x3f,sizeof(dis));
memset(in,0,sizeof(in));
dis[s]=0;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
in[x]=0;
for(auto y:v0[x])if(dis[y.first]>dis[x]+y.second){
dis[y.first]=dis[x]+y.second;
if(!in[y.first]){
in[y.first]=1;
q.push(y.first);
}
}
}
}
int AStar(int&k){
priority_queue<node>q;
q.push({n,0});
while(!q.empty()){
int x=q.top().pos,d=q.top().len;
q.pop();
if(x==1){
cout<<d<<'\n';
if(!--k)return 0;
}
for(auto y:v[x])q.push({y.first,d+y.second});
}
return k;
}
inline void main(){
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
v[a].push_back({b,c});
v0[b].push_back({a,c});
}
spfa(1);
AStar(k);
while(k--)cout<<"-1\n";
}
}
int main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0),JRC::main();return 0;}
IDA就是采用了迭代加深的A算法。
八数码。估价函数定义为位置不正确的数字的数量，加入最优性剪枝，当前枚举下一个状态若回到上一个状态肯定不是最优，于是dx[]、dy[]对称排列设计。
int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
inline int evaluate(int re=0){
for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)re+=(a[i][j]!=b[i][j]);
return re;
}
void IDAStar(int dep,int x,int y,int la,int maxdep){
if(dep==maxdep){
if(!evaluate())flag=1;
return;
}
if(flag)return;
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i];
if(tx<1||ty<1||tx>3||ty>3||la+i==3)continue;
swap(a[x][y],a[tx][ty]);
if(dep+evaluate()<=maxdep)IDAStar(dep+1,tx,ty,i,maxdep);
swap(a[x][y],a[tx][ty]);
}
}
给定一张由''和'/'组成的网格，要求左上到右下联通，问最小转动的数量。bfs，注意方格和格点的坐标和移动数组，不转动优先入队，使用双端队列，若终点坐标和起点坐标奇偶性不同则无解。
int dx[4]={-1,-1,1,1},dy[4]={1,-1,1,-1},cx[4]={-1,-1,0,0},cy[4]={0,-1,0,-1};
char c[5]="/\\\\/";
namespace JSY{
inline void bfs(int x,int y){
deque<pair<int,int>>q;
memset(dis,0x3f,sizeof(dis));
q.push_front({x,y});
dis[x][y]=0;
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop_front();
for(int i=0;i<4;i++){
int tx=x+dx[i],ty=y+dy[i],nx=x+cx[i],ny=y+cy[i];
if(tx<0||ty<0||tx>n||ty>m)continue;
if(a[nx][ny]==c[i]){
if(dis[tx][ty]<=dis[x][y])continue;
q.push_front({tx,ty});
dis[tx][ty]=dis[x][y];
}
else{
if(dis[tx][ty]<=dis[x][y]+1)continue;
q.push_back({tx,ty});
dis[tx][ty]=dis[x][y]+1;
}
}
}
}
构造一个尽量短的数列，满足a[0]=1,a[m]=n,单调递增，对于每一个k,1<=k<=m，存在i和j,0<=i,j<=k-1，i和j可以相等，是的a[k]=a[i]+a[j]。最短的长度，可以迭代加深搜索，注意剪枝，假设a[i]->a[i+1],max(a[i+1])=2a[i],max(a[i+2])=22*a[i],max(a[m])=2(m-i)a[i]，倒序枚举尽快得到n。
bool dfs(int x,int maxdep){
if(x>maxdep)return a[x-1]==n;
if(a[x-1]*(1<<(maxdep-x+1))<n)return 0;/*每一项最多是前一项的两倍*/
for(int i=x-1;i>=0;i--)for(int j=x-1;j>=i;j--){
int t=a[i]+a[j];
if(t>n||t<=a[x-1])continue;
a[x]=t;
if(dfs(x+1,maxdep))return 1;
}
return 0;
}