冻葱Tewi
一个菜鸡。
冻葱Tewi
NOIP填坑记-深度优先搜索

在一个暑假的怠惰之后,肠子都悔青了得我开始紧张(?)的复习。顺便把自己复习进度和心得放在这里,供自己闲时查阅。如果这些文字能对你产生些许帮助,我将深感荣幸。

·什么是深度优先搜索

深度优先搜索(Depth-First-Search,简称DFS)是一种强力的搜索算法。它是一种利用回溯的思想进行的搜索——一条路走到最深处,不通了就调头,知道搜索到结果或是搜索完全部情况/全图。

深搜一直都是骗分的一大利器(?),熟练运用DFS是每一个蒟蒻的基本功。在我这个大蒟蒻写完几道模拟题恢复了一下代码能力之后,就赶紧再撸了几道深搜题压了压惊。

·深度优先搜索的基本思想

对于一个包含了全部情况的树,从某一个节点开始,对于与它相连的所有子节点,如果子节点还有子节点,则向深处搜索;如果“触底”,则处理并返回。

在处理有环的图时,需要注意不要陷进环里形成一个死循环。常用方法有建立一个形如bool visited[MAX]的数组来判断是否已经搜索过(就是染色了)。

·深度优先搜索的伪代码

void dfs(情况 u)
{
	if 递归边界 return;
	if 搜索完成 return;
	
	记录当前状态;
	
	for( u的所有"更深"的下一步情况v)
	{
		if(v不越界) dfs(v); 
	} 
	
	状态还原;
	
	//此时,情况u及更深的情况已经搜索完毕
	return; 
}

其中,递归边界就是指一些满足了就是越界了的条件。当达到递归边界,就说明u不满足条件,应该直接返回。

·深度优先搜索的例题

洛谷p1605为例,该题就是一道十分模板的DFS题目。这里配合我的代码来演示DFS在具体代码中的用法,若有不足之处欢迎斧正。

#include <cstdio>
#include <memory.h>
using namespace std;

const int MAX=51;
int n=0,m=0,t=0,zx=0,zy=0,sx=0,sy=0,fx=0,fy=0;
int tot=0;
int visited[MAX][MAX];

void dfs(int x,int y)
{
	if(x>n||y>m||x<1||y<1)return;//递归边界
	if(visited[x][y])return;//已经访问过
	if( x==fx && y==fy )//搜索到终点
	{
		tot++;//记录情况
		return;
	}	
	
	visited[x][y]=1;//记录当前状态
	dfs(x+1,y);//搜索几种更深的情况
	dfs(x-1,y);
	dfs(x,y+1);
	dfs(x,y-1);
	visited[x][y]=0;//回溯,状态还原
	return;//完成了当前节点及更深处的搜索
}

int main()
{
	memset(visited,0,sizeof(visited));
	
	scanf("%d%d%d%d%d%d%d",&n,&m,&t,&sx,&sy,&fx,&fy);
	for(int i=0;i<t;i++)
	{
		scanf("%d%d",&zx,&zy);
		visited[zx][zy]=1;
	}
	
	dfs(sx,sy);
	
	printf("%d\n",tot);
	
	return 0;
}

以上就是DFS的一些基本知识,利用DFS还可以做很多有趣和奇妙的事情,深搜也有很多不同的变种和情况。深度优先搜索虽然容易上手,但是还是需要多多练习才能熟练掌握,直到体会到深度优先搜索的精髓之处。

冻葱Tewi,于2017.9

赞赏
本站采用BY-NC-SA-4.0 国际许可协议, 转载请保留出处。
https://dctewi.com/wp-content/uploads/2019/02/head-croped-small-middle-300x300.jpg

冻葱Tewi

文章作者

这个站点的蒟蒻站长~欢迎大家来晃悠!

发表评论

textsms
account_circle
email

冻葱Tewi

NOIP填坑记-深度优先搜索
在一个暑假的怠惰之后,肠子都悔青了得我开始紧张(?)的复习。顺便把自己复习进度和心得放在这里,供自己闲时查阅。如果这些文字能对你产生些许帮助,我将深感荣幸。 ·什么是深…
扫描二维码继续阅读
2017-09-20
标签云
隐藏
变装