蓝桥杯训练之dfs开胃菜

years_gg

📅 发布于：2024-10-18 🔄 已更新：2024-10-18

编辑文章删除文章

## 蓝桥杯训练之dfs开胃菜

众所周知蓝桥杯是一个非常简单的编程比赛，是初学者都可以去尝试挑战的比赛，因此我不希望大家有太多的压力，不要去作弊等等。

我发这篇博客的目的呢，其实是想看看社团这个网站实际上到底有多少人再看，也分享一下自己的学习过程，帮助学弟学妹扩展一下视野。你们可以当做技术博客看也好，当成故事分享博客也好。

对于学校的比赛很多都是可以报销的，在算法这块，基本上你加入社团，每次周六和周天的课程坚持下去，就有机会获得比赛资格（天梯赛等等），等你加入后，你就可以光明正大的出去了，去看看其他的学校，看看与其他985和211的差距。有时候比赛的作用可能不仅仅是让你获得奖项，而是在这一路上的收获和感悟。

唔，开始准备蓝桥杯吧，希望拿个国奖，同时在这里稍微分享一下学习记录。其中打蓝桥杯我们只需要准备好dfs和bfs、二分等等这些基础的知识，就差不多可以了。<br/>

什么？你说数据结构？应该暂且用不到太多，至少省一基本不用太多，去了解一下STL，知道有哪些容器，变学变练习就可以了。

下面我们来用一个蓝桥杯国赛的dfs来开个胃。这个题我的评价是学过dfs，加上练习了一些就可以挑战了<br/>

[题目链接：](https://www.lanqiao.cn/problems/89/learning/?page=1&first_category_id=1&second_category_id=3)

>首先这个题目的意思是在一个二维平面里面，让你去规划一条合适的路线从左上角到右下角，同时在走的过程中，你会向上和向左各种射出一根箭，而且走过的路不能重复走。现在给你在衡坐标和纵坐标上射上箭的数量，即已知箭靶数字，求骑士的行走路径。<br/>

首先我们了解一下什么是dfs，即深度优先搜索，就是真不撞蓝墙不回头，走到不能再走了，才换一条路。<br/>

学习dfs首先你得知道递归，即当前这个函数里面在调用这个函数，自己调用自己。在本题中，我们可以走四个方向，在走了之后我们又可以走四个方向，同时要注意条件，最后我们直到终于找到正确的路径为止，这就跟递归很像。

这里我来分享一下做dfs我会思考的点，首先是它的条件有哪些，比如这个题是一个N大小的平面，那么肯定坐标不能超过0和N,还有题目说走过的路不能继续走，那么要用一个数组去记录哪些点走过，此外每走一步会向上和向左各种射出一箭，也就是说没有射箭的路径不会走，有了这些限制条件我们就可以开始写代码了。

```
#include <bits/stdc++.h>//万能头文件
using namespace std;
int n,h[21],l[21],maps[21][21],vis[21][21];
bool flag = false;//记录是否已经找到正确路径
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//定义可以走的方向
vector<int> anss;//记录路径
void dfs(int x, int y){
	if(flag) return;//如果找到路径了，就不用继续了
	if(x<0||x>=n||y<0||y>=n) return;//跑到地图范围外了，不用继续了
	if(vis[x][y]) return;//已经访问过了，不用继续了
	if(h[y]<=0||l[x]<=0) return;//这条路径上横坐标和纵坐标不能射箭，说明该路径不对，不能继续了
	vis[x][y] = 1;
	h[y]--,l[x]--;
	anss.push_back(maps[x][y]);//记录走过的路径，修改相应的变化，如该横坐标上的最上边已经射了一箭，还需要射箭的次数减少了，该路径访问过了
	if(x==n-1&&y==n-1){//到达最后的位置了，可以判断是否为答案
		bool flag1 = true;//判断是否满足条件：地图上的箭都被射满
		for(int i=0;i<n;i++){ 
			if(h[i]>0||l[i]>0) flag1 = false;//但凡有一个没有射箭就是不对的
		}
		if(flag1){//对的
			flag = true;//把Flag设置为true,意思是找到答案了
			for(int i=0;i<anss.size();i++){//按照题意输出结果
				if(i!=anss.size()-1) cout << anss[i] << " ";
				else cout << anss[i] << endl;
			}
			return;
		}
	}
	for(int i=0;i<4;i++){//不断向四个方向去衍生
		int xx = x+dx[i],yy = y+dy[i];
		dfs(xx,yy);
	}
		h[y]++,l[x]++;//衍生完了，还是没有找到答案，恢复变之前的样子
		anss.pop_back();
		vis[x][y]=0;
}

int main(){//主函数
	cin >> n;
	for(int i = 0; i < n; i++) cin >> h[i];//记录行和列射出的箭
	for(int i = 0; i < n; i++) cin >> l[i];
	int jishu = 0;
	for(int i = 0; i < n; i++){//由于要输出路径，我们按照路径的排布去记录到maps数组里面到时候可以直接放入向量vector(数组)
		for(int j = 0; j < n; j++){
			maps[i][j] = jishu++;
		}
	}
	dfs(0, 0);//开始dfs，为什么会是两个零，因为我们这题dfs只用记录横坐标和纵坐标，具体看题目需要哪些条件记录当前的递归的情况
	return 0;
}
```
从上面我们可以看到dfs主要是记录当前状况去递归，递归时要给出终止条件（不能继续递归的条件和找到结果的条件），当没有终止条件触发时去修改要求的条件变化（比如你用vis数组记录该下标是否访问过，1为访问过，0没有访问，当你去递归某条路径的时候，你不一定找到答案，那么你之前做出的操作就要撤回），然后给出递归的方向，在本题中可以向上向左，向右，向下，因此for循环4次。最后撤销修改的条件。

简单来说dfs用递归来写，在这个递归函数里面，先写退出的条件，在写找到结果的条件，在用循环表示有哪些可能，在其中注意一些题目条件的处理就可以了。

最后希望这个网站可以不断改进，优化，可以成为我们学校大家知道的网站之一。

liu
18 10月 2024 21:40

👍👍👍
回复
liu
18 10月 2024 21:40

👍👍👍
回复
liu
18 10月 2024 21:40

👍👍👍
回复
liu
18 10月 2024 21:40

👍👍👍
回复
殇
18 10月 2024 23:25

👍👍👍
回复
殇
18 10月 2024 23:25

👍👍👍
回复
殇
18 10月 2024 23:25

👍👍👍
回复
Xavier.L
19 10月 2024 20:08

👍👍👍
回复

蓝桥杯训练之dfs开胃菜

评论

发表评论