算法概述：搜索，类似于枚举，从头结点开始，搜索发现有一些路可以走，先选择一条，走到一个结点处，重复上述过程，一直走到不能走为止，然后返回上一个结点，选择第二条路，一直检索知道将头结点所有的路走完。
算法图像
如图所示，从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++版）在线评测系统
分析：每一组输出要按数字的升序输出，各组数据也要按字典序升序输出，故可以考虑搜索来枚举所有的可能性
代码
#includeusing 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#include 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;
}
}
}
