算法刷题笔记：搜索

发表于 更新于 分类于

基本技巧

广度优先搜索

常用 queue 作为队列

1
2
#include <queue>
queue<int> q;

常在计算最短路径时使用，拥有比 DFS 更好的时间复杂度

深度优先搜索

常用递归函数解决

剪枝策略：

  • 最优剪枝策略：当当前计算的答案已经不可能更优时，直接停止计算

标记技巧

在求路径时，一定要注意标记，避免重复走某一个的情况：

  • DFS 在进入下一个函数前标记
  • BFS 在进入队列的同时进行标记

在二维平面上做标记不一定得用二维数组，也可以用多个一维数组来表示下标为 i 的占用情况：

用数组解决“往周围格子走”

1
2
3
4
5
6
7
for (int i=0;i<4;i++){
    // 把每次可以走的偏移存在 dx dy 中
    int xx = x + dx[i],yy = y + dy[i];
    if (xx>=0 && yy>=0){ // 对每一格的判断条件
		...
    }
}

八皇后问题

棋子不能出现在同一行同一列以及同一对角线（ k = 1 和 k = -1 的直线）

难点：标记占用的格子，如果直接用二维数组进行标记，会导致确定是否有标记时 时间复杂度较高

解决方法：

  • 用一个一维数组 c[i]，若 c[i] 为 1 表示第 i 列已经有占用的了
  • 用一个一维数组 d[i]，若 d[i] 为 1 表示 row+col=irow + col = i 的对角线已被占用（即通过 y=−x+by = -x + b 中的截距 bb 来定位唯一的对角线）
  • 用一个一维数组 e[i]，若 e[i] 为 1 表示 row−col+n=irow - col + n = i 的对角线已被占用（即通过 y=x+by = x + b 中的截距 bb 来定位唯一的对角线），此处加 n 是为了保证结果为正
1
2
3
4
5
6
7
8
9
10
11
12
13
void search(int r) {
	if (r == n + 1) {
		ans ++;
        return;
	}
	for (int j = 1; j <= n; j ++) {
		if (!c[j] && !d[r+j] && !e[r-j+n]) {
			c[j] = 1; d[r+j] = 1; e[r-j+n] = 1;
			search(r + 1);
			c[j] = 0; d[r+j] = 0; e[r-j+n] = 0;
		} 
	}
}

障碍迷宫问题

简单的 DFS 问题，但要注意一些处理的技巧和易错的细节。

处理技巧：

  • 二维数组多开两行两列并初始化为障碍（常用 1 表示），这样可以避免判断边界情况

    1
    2
    3
    4
    5
    6
    for (i = 0; i <= n+1; i ++) {
        g[i][0] = g[i][m + 1] = 1;
    }
    for (i = 0; i <= m+1; i ++) {
        g[0][i] = g[n+1][i] = 1;
    }

易错细节：

  • 终止条件除了到达终点之外，还有 x 和 y 坐标是否小于 0 或超过最大值、是否遇到障碍、是否已经访问过
  • 在退出一个 dfs 函数前，需要进行回溯，即将访问过的标记还原为未访问