蓝桥杯倒计时 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;
}