<目录

深度优先搜索 \(\sf\small\color{gray}Depth\ First\ Search\)

基本思想

基于递归的 执着 的枚举算法
\(\hspace{2cm}\)——\(\sf\small\color{black}David\)

这句话里有三个关键词。
\(\boxed{\sf递归}\boxed{\sf\textit{执着}}\boxed{\sf枚举}\)

枚举

枚举，可谓是解决问题的基本思路了。
在一个范围内，所有的情况我都给你算一边，不就完啦？
可是如果人算，那就太浪费劳动力了。
所以，计算机的超强计算能力便派上用场了。

递归

如何基于递归呢？
每一次枚举，他都有一个状态。
如果这个状态是多维的，
不基于递归，就是一堆 for ，
基于递归，就是一个清清爽爽的函数了。
每一次执行函数，都处理一维的状态，
多递归几层，就把繁琐的多维状态处理掉了。

执着

为什么说它是执着的呢？
只要没有枚举完，
或者没有达到目标态，
它就停不下来。
这就是 执着 。

遍历树

DFS的遍历树大概长这样：

分类

按照我的理解，将其分为两类。

穷举

穷举，就是把所有的情况都算一遍，通过每一次的结果，得出最后的结果。

字符全排列

输入一行字符串（符合字典序），长度不超过10位，请按字典序输出所有的排列情况以及总的排列种数。保证有所字符不会重复。

全排列，就是和原串相同有着相同的元素，可是又不同于原串的有序串。
字符串的每一位都和另一位可以组成一种不同的情况，所以一位就是一维。
注意的是，当你枚举完了某一位上的字符，再换字符的的时候，你会很容易的想到，应该把原来的字符给换掉。
暂停！ 这一点很重要。你换掉字符的过程，被称之为 \(\sf\color{red}回溯\) 。
回溯是进入的反义词。当进入完成时，你就需要回来，也就是回溯。
依照递归函数三要素，我们来分析：

调用自身

需要使用 for 循环枚举所有字符，如果此字符还没被用，就进入下一层枚举。

for(int i=0;i<len;i++)
{
	...
	odd(...);
	...
}

状态转移

需要转移的肯定是层数以及用过的字符。

for(int i=0;i<len;i++)
{
	if(have[i])	continue;
	ans[t]=in[i],have[i]=true;
	odd(t+1);
	ans[t]=0,have[i]=false;
}

递归边界

什么时候撞南墙呢？显然，如果我已经枚举完了，那么枚举就结束了。

if(t==len)
{
	sum++;
	for(int i=0;i<len;i++)
		printf("%c ",ans[i]);
	printf("\n");
	return;
}

完整代码

#include<cstdio>
#include<cstring>
char ans[11],in[11];
bool have[11];
int len,sum;
void odd(int t)
{
	if(t==len)
	{
		sum++;
		for(int i=0;i<len;i++)
			printf("%c ",ans[i]);
		printf("\n");
		return;
	}
	for(int i=0;i<len;i++)
	{
		if(have[i])	continue;
		ans[t]=in[i],have[i]=true;
		odd(t+1);
		ans[t]=0,have[i]=false;
	}
}
int main()
{
	scanf("%s",&in);
	len=strlen(in);
	odd(0);
	printf("%d",sum);
	return 0;
}

复杂状态转移

有些时候，状态不只是光 +1 就好，可能是向上走，可能是转个圈……

走迷宫

给一张地图， N 表示变长， . 表示空地， # 表示墙壁，请问是 YES 否 NO 可以从一个点 (x1,y1) 走到另一个点 (x2,y2) ？

这一道题的状态明显比穷举的要复杂，有 x 和 y 两个维度的状态了。
只是转移方式和目标态不一样，其他的都差不多。

调用自身+状态转移

放在一起写吧。

坐标控制

为了好写，装进数组。

const int D[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

出图

出图就不好玩了。

bool outmap(int x,int y)
	{return (x<0||x>=n||y<0||y>=n);}

转移+回溯

用 Map[x][y] 标记是否走过，防止转圈。

for(int i=0;i<4;i++)
{
	const int Nx=x+D[i][0];
	const int Ny=y+D[i][1];
	if(outmap(Nx,Ny))
		continue;
	if(map[Nx][Ny])
		continue;
	map[x][y]=true;
	maze(Nx,Ny);
	map[x][y]=false;
}

目标态

目标态是终点，所以终点是南墙。

if(finish)	return;
if(x==hb&&y==lb)
{
	printf("YES\n");
	finish=true;
	return;
}

完整代码

#include<cstdio>
#include<iostream>
#include<cstring>
bool map[105][105],finish=false;
int n,ha,la,hb,lb;
const int D[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void scanmap()
{
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
		{
			char o;
			std::cin>>o;
			if(o=='.')
				map[i][j]=false;
			else if(o=='#')
				map[i][j]=true;
		}
	return;
}
bool outmap(int x,int y)
{
	return (x<0||x>=n||y<0||y>=n);
}
void maze(int x,int y)
{
	if(finish)
		return;
	if(x==hb&&y==lb)
	{
		printf("YES\n");
		finish=true;
		return;
	}
	for(int i=0;i<4;i++)
	{
		const int Nx=x+D[i][0];
		const int Ny=y+D[i][1];
		if(outmap(Nx,Ny))
			continue;
		if(map[Nx][Ny])
			continue;
		map[x][y]=true;
		maze(Nx,Ny);
		map[x][y]=false;
	}
	return;
}
int main()
{
	int k;
	scanf("%d",&k);
	for(int i=0;i<k;i++)
	{
		memset(map,false,sizeof map);
		finish=false;
		scanf("%d",&n);
		scanmap();
		scanf("%d%d%d%d",&ha,&la,&hb,&lb);
		if(map[ha][la]==true||map[hb][lb]==true)
		{
			printf("NO\n");
			continue;
		}
		map[ha][la]=true;
		maze(ha,la);
		if(!finish)
			printf("NO\n");
	}
	return 0;
}

算法优劣

照例，我们来谈谈算法优劣。
DFS 编程难度非常小，是顺推的。
可是它有着递归函数所给的累赘……
复杂度过不去啊。

完结散花^_