红鲤鱼与绿鲤鱼与驴 残血回归

之前递归一直没学好，感觉总是绕不过那个弯，所以就一直不敢碰DFS，今天终于鼓起勇气，看遍了n多视频和文章后，好像有点感觉了

深度优先搜索 DFS ：沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

伪代码：

void dfs(状态A){
    if(A不合法)
        return ;
    if(A为目标状态)
        输出
    if(A不为目标状态)
        dfs(A+*)  //递归调用
}

好像理解了 then 做题找感觉

#include <iostream>
#include<cstdio>
using namespace std;
int a[101],b[101],n;
void print()
{
    int i;
    for(i=1;i<=n;i++)
    {
        cout<<"    "<<a[i];
    }
    cout<<endl;
}
inline void dfs(int i) 
{

    int j;
    if(i==n+1)
    {
        print();
        return;
    }
    for(j=1;j<=n;j++)
    {
        if(b[j]==0)
        {
            a[i]=j;
            b[j]=1;
            dfs(i+1);
            b[j]=0;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    dfs(1);
    return 0;
}

  • P1036 选数
    https://www.luogu.com.cn/problem/P1036

    #include<iostream>
#include<cmath>
using namespace std;
int n,k,cnt=0,sum=0;
int zls[25];
int zspd(int a){
  int q=(int)sqrt(a);
  for(int i=2;i<=q;i++)
      if(a%i==0)
          return 0;
  return 1;
}
void dfs(int x,int y){
  if(x>k){
      if(zspd(sum))
          cnt++;    
      return ;
  }
  for(int i=y+1;i<=n;i++){
      sum+=zls[i];
      dfs(x+1,i);
      sum-=zls[i];
  }
} 
int main(){
  cin>>n>>k;
  for(int i=1;i<=n;i++)
      cin>>zls[i];
  dfs(1,0);
  cout<<cnt;
  return 0;
}

  • AcWing165 小猫爬山
    https://www.acwing.com/problem/content/167/

#include<iostream>
#include<algorithm>
using namespace std;
int n,w;
int c[20],p[20];
int ans=1e9;
bool cmp(int a,int b){
    return a>b;
}
void dfs(int x,int cnt){
    if(cnt>=ans)
        return ;
    if(x==(n+1)){
        ans=min(ans,cnt);
        return ;
    }
    for(int i=1;i<=cnt;i++){
        if(p[i]+c[x]<=w){
            p[i]+=c[x];
            dfs(x+1,cnt);
            p[i]-=c[x];
        }
    }
    p[cnt+1]=c[x];
    dfs(x+1,cnt+1);
    p[cnt+1]=0;

}
int main(){
    cin>>n>>w;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    sort(c+1,c+1+n,cmp);
    dfs(1,0);
    cout<<ans;
    return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
char a[105][105];
int n,m,ans;
int fx[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}};
void dfs(int x,int y){
    a[x][y]='.';
    int xx,yy;
    for(int i=0;i<8;i++){
        xx=x+fx[i][0];
        yy=y+fx[i][1];
        if(xx>0 && xx<=m && yy>0 && yy<=n && a[xx][yy]=='@')
            dfs(xx,yy);
    }
}
int main(){
    while(cin>>m>>n&&(n||m)){
        ans=0;
        memset(a,0,sizeof(a));
        for(int i=1;i<=m;i++)
            cin>>a[i]+1;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]=='@'){
                    ans++;
                    dfs(i,j);
                }
        cout<<ans<<endl;
    }
    return 0;
}

自言自语Part：
自闭小魏无话可说
Good Luck！