C++一本通基础算法：深度优先搜索（DFS）

算法概述：搜索，类似于枚举，从头结点开始，搜索发现有一些路可以走，先选择一条，走到一个结点处，重复上述过程，一直走到不能走为止，然后返回上一个结点，选择第二条路，一直检索知道将头结点所有的路走完。

算法图像

 如图所示，从1开始，发现可以到达2，开始递归调用，到达2的位置，然后发现，从2可以到达3，再递归调用，到达3，发现3不能再走了，返回到2，发现从2还可以到4，递归调用到达4，发现4也不能走，再次回到2，……，直到2所有的路都走完以后，返回到1，发现从1可以到6，……，当6所有的路径也走完之后，回到1，此时1已经没有任何可以走的路径了，搜索结束。

算法特点：和枚举一样要计算所有的结果，但与枚举不同的是，枚举的循环层数一定，但深度优先搜索的层数不为定值。

搜索部分代码的一般格式

void dfs (int x,int p) {	//x代表当前搜索层数，p决定下一次递归的大范围 
	if ( ) {           		//如果满足终止条件（找到一组解） 
					   		//执行操作 
		return;				//返回上一个函数 
	}
	for (int i = p + 1; ;i++) {
		if ( ) {			//如果当前i满足递归条件 
							//更新条件数组 
			dfs (x + 1,i);  //递归 
							//回溯，将条件数组变回原样（有时可以省略） 
		}
	}
}

题目链接

信息学奥赛一本通（C++版）在线评测系统

分析：每一组输出要按数字的升序输出，各组数据也要按字典序升序输出，故可以考虑搜索来枚举所有的可能性

代码

#include <iostream>
using namespace std;

int n, r, a[22], l = 0;

void search (int x,int y) {
	if (y == r) {
		for (int i = 0;i < l;i++) {
			if (a[i] / 10 == 0) cout << "  " << a[i];
			else cout  << " " << a[i];
		}
		cout << endl;
		return;
	}
	else {
		for (int i = x + 1;i <= n - r + y + 1;i++) {
			a[l++] = i;
			search(i,y + 1);
			a[--l] = 0;
		}
	}
}

int main () {
	cin >> n >> r;
	search (0,0);
	return 0;
}

题目链接

信息学奥赛一本通（C++版）在线评测系统

分析：走迷宫，从当前位置向前后左右四个方向走，先判断四个位置是否是墙，是否走过，或越界，如果都没有，那么走向这个位置。如果搜索结束后还没有搜索到终点位置，则无法走到。

代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int w[4][2] = {0,1,1,0,0,-1,-1,0},ha,hb,la,lb;
bool m[N][N],flag = 0; 

void dfs (int x,int y) {
	if (x == hb && y == lb) {
		flag = 1;
		return;
	}
	for (int i = 0;i < 4;i++) {
		int nx = x + w[i][0],ny = y + w[i][1];
		if(m[nx][ny]) {
			m[nx][ny] = 0;
			dfs(nx,ny);
		}
	}
}

int main () {
	int n, k;
	cin >> k;
	while (k--) {
		memset (m,0,sizeof(m));
		flag = 0;
		cin >> n;
		for (int i = 1;i <= n;i++) {
			for (int j = 1;j <= n;j++) {
				char u;
				cin >> u;
				if (u == '.') m[i][j] = 1;
				else m[i][j] = 0;
			}
		}
		cin >> ha >> la >> hb >> lb;
		ha++;hb++;la++;lb++;
		if (!m[ha][la] || !m[hb][lb]) cout << "NO" << endl;
		else {
			dfs(ha,la);
			if (flag) cout << "YES" << endl;
			else cout << "NO" << endl;
		}
	}
	return 0;
} 

敲黑板

搜索最阴间难的题目：八皇后问题

皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 × 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

分析：

行：所有的皇后都不在一行上，不妨我们从第一行开始，每行只放置一个皇后，这样即可保证皇后不能在同一行的问题。

列：建立一个布尔数组，每放置一个皇后，就把皇后所处列的这一项设为1，在放置皇后之前，先判断这个皇后所在列的这一项是否为1.

从左上到右下的对角线：

观察这个表格可知，如果两个方格的行与列的差相同，则这两个方格位于同一条对角线上。

从右上到左下的对角线：

同理，观察表格可知，如果两个方格的行与列的和相同，则这两个方格位于同一条对角线上。

八皇后代码（dfs部分）

int a[93][8];
bool lx[20],rx[20],s[10];
int p,k[9];

void search (int h) {
	if (h > 8) {
		p++;
		for (int i = 0;i < 8;i++) {
			a[p][i] = k[i];                //a[p]为八皇后的第p组解，八皇后问题共有92组解
		}
		return;
	}
	for (int i = 1;i <= 8;i++) {
		if (!lx[i + h] && !rx[h - i + 8] && !s[i]) {
			lx[i + h] = 1;
			rx[h - i + 8] = 1;
			s[i] = 1;
			k[h - 1] = i;
			search (h + 1);
			k[h - 1] = 0;
			lx[i + h] = 0;
			rx[h - i + 8] = 0;
			s[i] = 0;
		}
	}
}