当前位置：首页 > news >正文

蓝桥杯高频考点——搜索（含C++源码）

news 2025/3/26 10:19:10

搜索

P1443 马的遍历
- 满分代码及思路
- - solution (BFS)
P9241 [蓝桥杯 2023 省 B] 飞机降落
- 满分代码及思路
- - solution（DFS）
买瓜
- 满分代码及思路
- - solution1（DFS）
  - solution 2（双向DFS）
老鼠吃奶酪
- 满分代码及思路
- - 遇到的问题
  - solution（满分代码）
结语

P1443 马的遍历

题目描述

有一个 $\times m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 $n, m, x, y$ 。

输出格式

一个 $\times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $- 1$ ）。

输入输出样例 #1

输入 #1

3 3 1 1

输出 #1

0    3    2    
3    -1   1    
2    1    4

说明/提示

数据规模与约定

对于全部的测试点，保证 $\leq x \leq n \leq 400$ ， $\leq y \leq m \leq 400$ 。

满分代码及思路

非常好的视频讲解

//基本思路：
宽搜，一开始我觉得是深搜，但其实不是，题目希望的是我们输出最小的步数拿第一个点举例子我们希望马尽可能地去找到它在目前位置上能到的点并做出标记，不断的向四周扩散，如果遇到之前标记过的点或者遇到边界就之间跳过这次循环就好
//但如果是深搜一条路走到黑，很有可能会把我们原来一步能走到的点标记为more

//我觉得如果硬要用深搜写也是可以的只不过在标记的时候需要取一个步数的最小值，而且我感觉有可能会超时，估计需要剪枝优化才能AC

//想清楚上面之后还有就是

//我觉得这题难点在于马是跟象棋中一样走的是日字型
//假如这个棋盘足够大马在正中心
//我们需要模拟八个方向的情况用两个偏移量数组来模拟马的跳跃

solution (BFS)

#include <bits/stdc++.h>
using namespace std;
//基本思路：宽搜，一开始我觉得是深搜，但其实不是，题目希望的是我们输出最小的步数 拿第一个点举例子 我们希望马尽可能地去找到它在目前位置上能到的点 并做出标记，不断的向四周扩散，如果遇到之前标记过的点或者遇到边界就之间跳过这次循环就好
//但如果是深搜一条路走到黑，很有可能会把我们原来一步能走到的点标记为more//我觉得如果硬要用深搜写也是可以的 只不过在标记的时候需要取一个步数的最小值，而且我感觉有可能会超时，估计需要剪枝优化才能AC//想清楚上面之后 还有就是//我觉得这题难点在于马是跟象棋中一样 走的是日字型 
//假如这个棋盘足够大 马在正中心 
//我们需要模拟八个方向的情况 用两个偏移量数组来模拟马的跳跃
int dx[8]={-1,-2,-2,-1,1,2,2,1};//将马视为中心（原点）左边负右边正
int dy[8]={-2,-1,1,2,2,1,-1,-2};
const int N=410;
struct house{
int x;
int y;
};
int s[N][N];//棋盘
int n,m;
//马的出生点
queue <house>q;//存储马的坐标
int main()
{int x0,y0;cin>>n>>m>>x0>>y0;memset(s,-1,sizeof(s));//把所有格子都初始化为-1s[x0][y0]=0;//出生点当然是第0步啦house tmp={x0,y0},p;q.push(tmp);//把初始状态放进队中while(!q.empty()){tmp=q.front();q.pop();for(int i=0;i<8;i++)//宽搜一下这个点的八种走法{int x=dx[i]+tmp.x;int y=dy[i]+tmp.y;//某一种走法之后的坐标if(s[x][y]!=-1||x>n||x<1||y>m||y<1)//判断状态是否合法{continue;//跳过这次选择的方向}//合法情况 我们需要干两件事://1.标记 2.放进队列s[x][y]=s[tmp.x][tmp.y]+1;//目前的要设置的步数在之前的基础上+1；p={x,y};//存一下放进队列q.push(p);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<s[i][j]<<"    ";}cout<<endl;}return 0;
}

P9241 [蓝桥杯 2023 省 B] 飞机降落

.## 题目描述

$N$ 架飞机准备降落到某个只有一条跑道的机场。其中第 $i$ 架飞机在 $T_{i}$ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 $D_{i}$ 个单位时间，即它最早可以于 $T_{i}$ 时刻开始降落，最晩可以于 $T_{i}+D_{i}$ 时刻开始降落。降落过程需要 $L_{i}$ 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 $N$ 架飞机是否可以全部安全降落。

.## 输入格式

输入包含多组数据。

第一行包含一个整数 $T$ ，代表测试数据的组数。

对于每组数据，第一行包含一个整数 $N$ 。

以下 $N$ 行，每行包含三个整数 $T_{i},D_{i},L_{i}$ 。

.## 输出格式

对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

.## 输入输出样例 #1

.### 输入 #1

.### 输出 #1

YES
NO

.## 说明/提示

【样例说明】

对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

【评测用例规模与约定】

对于 $\%$ 的数据， $\leq 2$ 。

对于 $\%$ 的数据， $\leq T \leq 10$ ， $\leq N \leq 10$ ， $\leq T_{i},D_{i},L_{i} \leq 10^{5}$ 。

蓝桥杯 2023 省赛 B 组 D 题。

满分代码及思路

我的理解：首先一上来就问我们这么多飞机怎么安排，能不能成功？
我需要想哪架飞机先降落，哪架飞机要盘旋，什么情况下会失败？什么情况下最优？what a mess! ! !
这我哪知道呢？
所以我们需要把这个大的问题转化成若干相同的子问题，我们只需要处理好一个或者两个剩下的去交个递归就好
下面我用时刻和时间的概念为大家解析一下这道题
读完题目我们就可以知道对于一架飞机，我们最早是不是在T时刻可以降落最晚在T+D时刻降落，再晚点就坠机了孩子们，我们枚举每一种降落顺序假设其中有一种可行
那么顺序都安排好了我们需要知道什么时候安排手头上的这架飞机降落这是这道题目的关键！
假设前一架飞机PRE降落完成的时刻为pre.time 我们这架飞机P的降落时刻为p.time,
1.如果p.time>pre.time 也就是比较好的情况，不用盘旋到了直接落就行那么我们降落的时间就是p.time
2.如果p.time<pre.time 这时候我们的飞机P就得在天上再呆一会直到PRE降落完毕，也就是说此时的降落时间就是pre.times对吧
综上我们的降落时间就呼之欲出了 max{p.time,pre.time} (代码中使用的是库函数max所以是括号)

基本思路图解：
在这里插入图片描述

solution（DFS）

#include <bits/stdc++.h>
using namespace std;
const int N =10+9;//防止越界
int n;//有多少架飞机
//int T,D,L;//分别表示降落时刻，能盘旋的时间，降落的时间
//考虑到这题这三个数据可以代表一架飞机的属性 可以考虑采用结构体来实现struct plane{
int t;
int d;
int l;
}p[N];
bool s[N];//每架飞机的状态
//我们需要知道几架飞机成功降落 和前一架飞机降落的时间
bool dfs(int x,int time)
{if(x>=n){return true;}//递归出口//枚举每种降落顺序for(int i=0;i<n;i++){if(!s[i])//这架飞机没有安排过{s[i]=true;if(p[i].t+p[i].d<time){//回溯s[i]=false;return false;}int next=max(p[i].t,time)+p[i].l;if(dfs(x+1,next)){return true;//后续的飞机都可以顺利降落}s[i]=false;}}return false;//所有降落方案都不能成功降落；}
int main()
{int T;//测试的组数cin>>T;while(T--){cin>>n;for(int i=0;i<n;i++){cin>>p[i].t>>p[i].d>>p[i].l;}if(dfs(0,0)){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}for(int i=0;i<n;i++){s[i]=false;}}return 0;}

买瓜

在这里插入图片描述
题目链接

满分代码及思路

首先我们看到这行这数据太小了吧我感觉大体上就是暴力枚举所有情况

在这里插入图片描述

其实跟前面的思路本质上差不多，这题上来就问能不能通过给定的一车重量不一定相同的瓜凑到某一个特定重量m，而且这个小蓝还TM是个忍者能正好劈开一半 wtf？这个太难了呀，问题太大了
我们还是得把目光转移到某一个瓜上，对于这个瓜我们只有三种处理方式，
1 整个放到篮子里
2 切一半放篮子里
3. 不选

好搞到这里基本上差不多了，这个西瓜虽然最多30个，我们每个瓜对应3种选择就像一颗树吧，对于每一颗瓜就是一个结点而每个节点又有三种选择那我们直接这么写的话就是 3的30次方是一个很大的数字有可能超时啊（实际也是如此）

那么我们是不是就要想到剪枝优化

在回溯章节我们其实就学过剪枝这个操作（全排列集合问题）我的对应文章

在买瓜这题里，我们可以剪三次：

1 当目前的方案并不优于已有的合法方案时也没有必要再搜索下去了
举个例子，因为我们要求要劈西瓜的次数要尽可能少（省一半卖不掉就可惜了）比如说我们劈了两次找到了一个可行的方案那么我们是不是现在的目标就是看看能不能只劈开一个西瓜就达到目的
2 如果当前的重量加上后面所有瓜的重量的总和都达不到我们要的m
说明没必要再继续搜索下去了
3 如果总重量已经超出了m也没有必要继续搜了
因为我们要正好m斤多一点就要翻脸了
（买瓜的是个nc 小蓝也是个肺雾能正好劈一半不能劈一点）

solution1（DFS）

#include <bits/stdc++.h>using namespace std;
const int N =30+10;
int n,m;
int a[N],s[N];
int ans=INT_MAX;
bool cmp(int x,int y)
{return x>y;
}
//需要三个参数分别表示当前切到第几个瓜 重量 切的刀数
void dfs(int u,double w,int cnt)
{if(w==m){ans=min(cnt,ans);//当前合法方案的最小值return;}//如果遍历完所有瓜了的时候之间返回if(u>=n) return;//当目前的方案并不优于已有的合法方案时也没有必要再搜索下去了if(cnt>=ans)return;//如果总重量已经超出了m也没有必要继续搜了if(w>m)return;//利用我们构造的后缀和数组s[N]判断 如果当前的重量加上后面所有瓜的重量的总和都达不到mm//说明没办法满足 直接返回if(w+s[u]<m) return;//对于每个瓜有三种选择//1.选但是不切dfs(u+1,w+a[u],cnt);//2.选而且切一下dfs(u+1,w+a[u]/2.0,cnt+1);//3.不选dfs(u+1,w,cnt);
}
int main()
{cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i];}//贪心 先枚举大的瓜，以保证切的刀术尽可能少sort(a,a+n,cmp);//构造反向的前缀和数组for(int i=n-1;i>=0;i--){s[i]=s[i+1]+a[i];}dfs(0,0.0,0);
if(ans==INT_MAX)
{ans=-1;
}
cout<<ans<<endl;return 0;
}

solution 2（双向DFS）

对于双向DFS这个概念我还是在labuladong的算法笔记中见过，但是只是了解并不会写，
这题我们的思路就是先对前一半也就是n/2的瓜dfs一下枚举所有可能的情况然后在对剩余的一半DFS一下

思路：

1 划分瓜的集合：将所有的瓜分成两部分，前 n/2 个瓜和后 n - n/2 个瓜。
2 第一次 DFS：对前 n/2 个瓜进行 DFS，记录下所有可能的重量和对应的最少刀数。
3 第二次 DFS：对后 n - n/2 个瓜进行 DFS，对于每一种可能的重量和刀数，在第一次 DFS 记录的结果中查找是否有可以组合成目标重量 m 的情况，并更新最小刀数。
4 输出结果：如果最终找到满足条件的方案，则输出最小刀数；否则输出 -1。

#include <bits/stdc++.h>
using namespace std;
const int N = 30 + 10;
int n, m;
int a[N];
int ans = INT_MAX;
// 存储前半部分瓜的所有可能重量和对应的最少刀数
unordered_map<double, int> mp;// 对前半部分瓜进行 DFS
void dfs1(int u, double w, int cnt) {if (u >= n / 2) {if (mp.find(w) == mp.end()) {mp[w] = cnt;} else {mp[w] = min(mp[w], cnt);}return;}// 1. 选但是不切dfs1(u + 1, w + a[u], cnt);// 2. 选而且切一下dfs1(u + 1, w + a[u] / 2.0, cnt + 1);// 3. 不选dfs1(u + 1, w, cnt);
}// 对后半部分瓜进行 DFS
void dfs2(int u, double w, int cnt) {if (u >= n) {double target = m - w;if (mp.find(target) != mp.end()) {ans = min(ans, cnt + mp[target]);}return;}// 1. 选但是不切dfs2(u + 1, w + a[u], cnt);// 2. 选而且切一下dfs2(u + 1, w + a[u] / 2.0, cnt + 1);// 3. 不选dfs2(u + 1, w, cnt);
}int main() {cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i];}// 对前半部分瓜进行 DFSdfs1(0, 0.0, 0);// 对后半部分瓜进行 DFSdfs2(n / 2, 0.0, 0);if (ans == INT_MAX) {ans = -1;}cout << ans << endl;return 0;
}

老鼠吃奶酪

在这里插入图片描述
题目链接

满分代码及思路

遇到的问题

下面是我最初的代码一个样例没过几乎全部超时但基本思路是对的
问题在于在原代码中，深度优先搜索会对很多重复的状态进行多次计算，而记忆化搜索可以通过记录已经计算过的状态，避免重复计算

修改思路：

状态表示：使用一个整数来表示已经访问过的奶酪点的集合（状态压缩），同时记录当前所在的奶酪点，用一个二维数组来存储从某个状态和当前点出发到遍历完所有奶酪点的最短距离。

递归函数：在递归函数中，首先检查当前状态是否已经计算过，如果是则直接返回结果，否则进行深度优先搜索并记录结果。

基本思路：

#include <bits/stdc++.h>
using namespace std;
double ans=1e9;
const int N=15+10;
bool st[N];//避免走回头路
int n;//给的奶酪数量
int a[N][2];//用来存储奶酪坐标 也可以用vector但是得定义一个结构体point
//基本思路：观察到奶酪的范围最多就15个 感觉大概率深搜暴力枚举,
// 因为题目需要的是最少的距离 也就是说，我们只需要每次走完一条路线
//与已有的最优方案取一次最小值就好 最后输出这个最小值 所以最初我们的答案ans要初始化成最大值 这样才能不断动态的更新
void dfs(int pos,int deep,double len)//分别表示当前的位置
{if(deep==n){ans=min(ans,len);return;}for(int i=1;i<=n;i++){if(st[i]){continue;//如果这个点走过就直接跳过}//如果没走过//1.标记st[i]=true;//改变长度double dx=a[i][0]-a[pos][0];double dy=a[i][1]-a[pos][1];double d=sqrt(dx*dx+dy*dy);dfs(i,deep+1,len+d);//回溯st[i]=false;}
}
int main()
{cin>>n;for(int i=1;i<=n;i++){cin>>a[i][0]>>a[i][1];}dfs(0,0,0);cout<<ans<<endl;
}

solution（满分代码）

#include <bits/stdc++.h>
using namespace std;
const int N = 15 + 10;
const double INF = 1e9;
int n;
double a[N][2]; // 修改为 double 类型
double memo[1 << N][N]; // 记忆化数组// 计算两点之间的距离
double dist(int i, int j) {double dx = a[i][0] - a[j][0];double dy = a[i][1] - a[j][1];return sqrt(dx * dx + dy * dy);
}// 记忆化搜索函数
double dfs(int state, int pos) {// 如果已经遍历完所有奶酪点if (state == (1 << n) - 1) {return 0;}// 如果该状态已经计算过，直接返回结果if (memo[state][pos] != -1) {return memo[state][pos];}double ans = INF;for (int i = 0; i < n; i++) {// 如果该点未被访问过if ((state & (1 << i)) == 0) {double newDist = dist(pos, i) + dfs(state | (1 << i), i);ans = min(ans, newDist);}}// 记录结果memo[state][pos] = ans;return ans;
}int main() {cin >> n;if (n == 0) { // 处理边界情况：没有奶酪点cout << fixed << setprecision(2) << 0.00 << endl;return 0;}for (int i = 0; i < n; i++) {cin >> a[i][0] >> a[i][1];}// 初始化记忆化数组for (int i = 0; i < (1 << n); i++) {for (int j = 0; j < n; j++) {memo[i][j] = -1;}}double ans = INF;// 把 (0, 0) 当作第 n 个点a[n][0] = 0;a[n][1] = 0;// 从 (0, 0) 出发，枚举第一个到达的奶酪点for (int i = 0; i < n; i++) {double startDist = dist(n, i);ans = min(ans, startDist + dfs(1 << i, i));}// 输出结果，保留 2 位小数cout.precision(2);cout << fixed << ans << endl;return 0;
}