日常训练之：BFS&&DFS（洛谷题）

雨点打透心脏的1/2处 2023-06-20 06:30 1阅读 0赞

# 日常训练之：BFS&&DFS #

--------------------

## [一、洛谷P1118：数字三角形][P1118] ##

--------------------

一看题目就知道是个DFS  
但是最开始TLE了三个点。。。。。  
看了大佬们的题解，发现：我去，这不就是**杨辉三角**吗，可以用杨辉三角预处理啊  
于是便有了下面的代码：

#include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #include<map>
    #include<queue>
    #define INF 0x3f3f3f3f
    #define ll long long
    using namespace std;
    int n,sum;
    int f[15][15];
    int num[15];
    int vis[15];
    int flag;
    void print(){
        
        printf("%d",num[1]);
        for(int i=2;i<=n;i++){
        
            printf(" %d",num[i]);
        }
        cout<<endl;
        return ;
    }
    void dfs(int step,int ans){
        
        if(ans>sum||flag)
            return ;
        if(ans==sum&&step==n+1){
        
            flag=1;
            print();
            return ;
        }
        for(int i=1;i<=n;i++){
        
            if(vis[i]==0){
        
                num[step]=i;
                vis[i]=1;
                dfs(step+1,ans+i*f[n][step]);
                vis[i]=0;
            }
        }
    }
    int main(){
        
        scanf("%d%d",&n,&sum);
        f[1][1]=1;
        for(int i=2;i<=n;i++){
        
            for(int j=1;j<=i;j++){
        
                f[i][j]=f[i-1][j]+f[i-1][j-1];
            }
        }
        memset(vis,0,sizeof(vis));
        flag=0;
        dfs(1,0);
        return 0;
    }

--------------------

## [二、洛谷P1434：滑雪][P1434] ##

--------------------

又是一道搜索题，开始就觉得必须得用**记忆化搜索**，不然暴搜，绝对会TLE  
但是还是不知道如何下手，还是题目做少了，不然不至于这样，后面才有了下面代码

#include<cstdio>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #include<map>
    #include<queue>
    #define INF 0x3f3f3f3f
    #define ll long long 
    using namespace std;
    int n,m;
    int mp[110][110];
    int dis[110][110];             //记忆化搜索
    int dir[4][2]={
        -1,0,0,1,1,0,0,-1};
    int dfs(int x,int y){
        
        if(dis[x][y]!=1)
            return dis[x][y];
        int b=0;
        for(int k=0;k<4;k++){
        
            int fx=x+dir[k][0];
            int fy=y+dir[k][1];
            if(mp[x][y]>mp[fx][fy])
                b=max(b,dfs(fx,fy));
        }
        dis[x][y]=max(dis[x][y],b+1);
        return dis[x][y];
    }
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                scanf("%d",&mp[i][j]);
                dis[i][j]=1;
            }
        }
        int maxdis=0;
        for(int i=1;i<=n;i++){
        
            for(int j=1;j<=m;j++){
        
                maxdis=max(maxdis,dfs(i,j));
            }
        }
        //getchar();
        printf("%d\n",maxdis);
        //getchar();
        return 0;
    }

--------------------

## [三、洛谷P1433：吃奶酪][P1433] ##

--------------------

开始读题，不知道为什么最先想到的是BFS，难道是由于最少距离？？  
又是一道DFS，这题开始的确没啥思路，看了题解后发现，如果加个**距离预处理**会是什么样子呢,这个感觉有点想不到。。。。

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<vector>
    #include<map>
    #include<queue>
    #define INF 0x3f3f3f3f
    #define ll long long 
    using namespace std;
    int n;
    double x[20],y[20];
    int vis[20];
    double dis[20][20];
    double ans=99999999.0;
    void dfs(int i,int now,double len){
        
        if(len>ans){
        
            return ;
        }
        if(i==n){
        
            ans=min(ans,len);
            return ;
        }
        for(int k=1;k<=n;k++){
        
            if(vis[k]==0){
        
                vis[k]=1;
                dfs(i+1,k,len+dis[now][k]);
                vis[k]=0;
            }
        }
    }
    int main(){
        
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%lf%lf",&x[i],&y[i]);
        }
        x[0]=0,y[0]=0;
        for(int i=0;i<=n;i++){
        
            for(int j=0;j<=n;j++){
        
                dis[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
            }
        }
        memset(vis,0,sizeof(vis));
        dfs(0,0,0.0);
        //getchar();
        printf("%.2f\n",ans);
        //getchar();
        return 0;
    }

--------------------

## [四、洛谷P1074：靶形数独][P1074] ##

--------------------

有点难，待补…

[P1118]: https://www.luogu.com.cn/problem/P1118
[P1434]: https://www.luogu.com.cn/problem/P1434
[P1433]: https://www.luogu.com.cn/problem/P1433
[P1074]: https://www.luogu.com.cn/problem/P1074