DFS 与回溯

DFS (Depth First Search)，即深度优先搜索，常在暴力枚举使用，顾名思义就是一直搜到结尾再回头，其本质是利用栈实现。

回溯算法的模板：

void dfs(int k) // k 代表递归层数或者要填第几个空
{
	if (所有空已经填完) {
		判断最优解/记录答案；
		return;
	}
	for (枚举该空的选项) {
		if (选项合法) {
			记录下这个空（保存现场）;
			dfs(k + i);
			取消这个空（恢复现场）；
		}
	}
}

示例：四阶数独

给出 $4\times4$ 方格，要求每个格子只能填写 $1\sim4$ 的整数，且每行、每列和四等分更小的方形格子都恰好由 $1\sim4$ 组成，请问有多少种合法写法？

给出解法：

#include <iostream>
#include <cstdio>
using namespace std;
#define SIZE 5
int a[SIZE * SIZE], n = 16, ans = 0;
int b1[SIZE][SIZE], b2[SIZE][SIZE], b3[SIZE][SIZE]; // 记录每行，每列，四小块的放置情况
void dfs(int x) {
	if (x > n) {
		ans++; // 成功填满方格，记录合法情况
		return;
	}
	int row = (x - 1) / 4 + 1; // 获取行号 1 ~ 4
	int col = (x - 1) % 4 + 1; // 获取列号 1 ~ 4
	int block = (row - 1) / 2 * 2 + (col - 1) / 2 + 1; // 获取小块号 1 ~ 4
	for (int i = 1; i <= 4; ++i) {
		if (!b1[row][i] && !b2[col][i] && !b3[block][i]) { // 若该处未放置
			a[x] = i; // 在整个方格记录放置位置及数字
			b1[row][i] = 1, b2[col][i] = 1, b3[block][i] = 1; // 标识已放置
			dfs(x + 1); // 填下一个
			b1[row][i] = 0, b2[col][i] = 0, b3[block][i] = 0; // 恢复未放置
		}
	}
}

int main() {
	dfs(1);
	cout << ans;
	return 0;
}

这个例题为我们展示了 DFS 算法以及回溯算法的运用，需要多加体会。

BFS

BFS (Breadth First Search)，即广度优先搜索，顾名思义是从出发点逐渐扩散，寻找最短路径，常用于“最小”“最短”的情景，使用队列实现。先将初始状态压入空队列，每次再取出队首，找出队首所能转移到的状态，全部压入队列，如此反复直到队列为空。

BFS 的一般形式如下：

Q.push(初始状态);
while (!Q.empty()) {
	State u = Q.front(); // 取出队首状态 u
	Q.pop(); // 出队
	for (枚举所有可拓展状态) { // 找到所有 u 的可达状态 v
		if (状态合法) { // 如未访问等
			Q.push(v); // 入队（可能需要维护某些信息）
		}
	}
}

示例：马的遍历

有一个 $n\times m$ 的棋盘，给定马的坐标，要求计算马到达棋盘任意一点最少要走几步。

给出解法：