蓝桥杯倒计时 36天-DFS练习

飞机降落

思路：贪心+暴搜。

#include<bits/stdc++.h>

using namespace std;
const int N = 10;
int t,n;
//这题 N 比较小，可以用暴力搜搜复杂度是 T×N*N!
struct plane{
    int t,d,l;
}p[N];
bool vis[N];//用来记录每个飞机是否访问
bool dfs(int dep,int last){
    if(dep==n){//当枚举完所有飞机到叶子节点则说明有满足条件的情况。
        return true;//只要一个 true 所有都 true
    }
    
    for(int i=0;i<n;i++){//枚举每个飞机
        int t = p[i].t,d = p[i].d,l = p[i].l;
        if(!vis[i]&&t+d>=last){//没访问过并且上一架飞机将落后可以降落
            vis[i]=true;//标记访问
            if(dfs(dep+1,max(t,last)+l))return true;//需要判断极限条件是否成立
            vis[i]=false;//回溯还原
        }
    }
    return false;//只要一个 false 所有都 false
}

int main( ){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>p[i].t>>p[i].d>>p[i].l;
        }
        memset(vis, false, sizeof vis);//还原标志位
        if(dfs(0,0))puts("YES");
        else puts("NO");
    }
    return 0;
}

仙境诅咒

思路：图的 DFS

#include<bits/stdc++.h>
using namespace std;
int n,d;
const int N = 1e3+10;

struct god{
    int x,y;
}gods[N];//输入每个神仙的坐标

bool vis[N];//判断神仙是否中毒

double dis(int i,int j){//求两个神仙间的欧式距离
    int x1 = gods[i].x,x2 = gods[j].x;
    int y1 = gods[i].y,y2 = gods[j].y;
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
//搜索以第 id 个中毒的神仙能感染周围哪些神仙
void dfs(int id){
    vis[id]=true;//标记第 id 个神仙中毒
    for(int i=0;i<n;i++){
        if(!vis[i]&&dis(id,i)<=d)dfs(i);//如果神仙没有搜索过，并且他在其他神仙的毒圈内，就需要以他为圆心进行搜索。
    }
}

int main( ){
    cin>>n;
    for(int i=0;i<n;i++)cin>>gods[i].x>>gods[i].y;
    cin>>d;
    dfs(0);
    for(int i=0;i<n;i++)cout<<(vis[i]?"1":"0")<<'\n';
    return 0;
}

小怂爱水洼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e2+5;
int n,m;
int vis[N][N],a[N][N];
typedef long long LL;
int dy[4]={0,1,0,-1};
int dx[4]={1,0,-1,0};
//在同一片水洼内搜索
void dfs(int x,int y,LL &sum){
    //保存新水洼的水量，并且设置已经访问过
    sum += 1ll*a[x][y];
    vis[x][y] = true;
    //向水洼四周搜索
    for(int i=0;i<=3;i++){
        int nx = dx[i]+x;
        int ny = dy[i]+y;
        //不能越界，不能访问过，并且要有水量，否则跳过该坐标
        if(nx<=0||nx>=n+1||ny<=0||ny>=m+1||!a[nx][ny]||vis[nx][ny])continue;
        dfs(nx,ny,sum);
    }
}
int main( ){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];//输入矩阵
        }
    }
    long long result =0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            LL sum = 0;
            dfs(i,j,sum);//对每个大水洼进行求和，ij 是水洼坐标，sum 存每个大水洼的水量和
            result = max(result,sum);//result 是总的最大的水洼
        }
    }
    cout<<result;
    return 0;
}

串变换

思路：数据范围k 为 7 用暴搜做。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 25;//数组的最大条件
int n,k;//串的长度为 n，操作次数 k
string s,t;//源串和目的串
int op[N],x[N],y[N];//操作数和操作码
vector<int> path;//用来存操作次序(全排列)
bool st[N];//用来记录是否访问过
bool res;//用来记录最后答案

void update(){
    //得到全排列的值进行操作看是否能得到目的串
    string str = s;
    for(int i=0;i<path.size();i++){
        int j = path[i];
        int a = op[j],b = x[j], c = y[j];
        if(a==1){
            str[b] = (str[b] - '0' + c) % 10 + '0';
        }else swap(str[b],str[c]);
    }
    res |= str==t;
}

void dfs(int u)
{
    if (u == k + 1)
    {
        update();
        return;
    }
    //全排列代码
    for (int i = 1; i <= k; ++ i )
        if (!st[i])
        {
            st[i] = true;
            path.push_back(i);
            dfs(u + 1);
            path.pop_back();
            st[i] = false;
        }
    //防止搜索一些值，叶节点没搜索到
    dfs(k + 1);
}
int main()
{
    cin >> n >> s >> t >> k;
    for (int i = 1; i <= k; ++ i )
        cin >> op[i] >> x[i] >> y[i];
    
    dfs(1);
    
    cout << (res? "Yes": "No") << endl;
    
    return 0;
}