如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
最近接触了一些简单的 DFS 与 BFS 问题，虽然谈不上对这两个算法有多深刻的理解，本着好记性不如烂笔头的观点，来总结一下我对处理这种问题的经验。
一 DFS
1 排列组合型问题
什么是排列组合型问题？
比如要求 1 ~ n 的全排列，或者随机输出任意多个，或者制定了输出 m 个（不重复）等。
这类问题我们可以使用 DFS 暴力枚举，虽说是暴力，但是也有技巧。先给出这三种题的模板题：
我们来看看这三种题解法的核心代码：
void dfs(int u)
{
// 这里是 u == n 而不是 u == n - 1 因为 n - 1 的位置还没有选择
if(u == n)
{
for(int i = 0; i < n; ++i)
if(st[i] == 1) printf("%d ", i + 1);
printf("\n");
return;
}
st[u] = 2;
dfs(u + 1); // 第一个分支：不选
st[u] = 0; // 回溯
st[u] = 1;
dfs(u + 1); // 第二个分支：选
st[u] = 0; // 回溯
}
void dfs(int u, int start)
{
// 当前已经选出 u - 1 个数，可以选的数的个数为 n - start + 1
// 如果 u - 1 + n - start + 1 < m 表示后面的数不够 m 个可以提前返回
if(u + n - start < m) return;
if(u == m + 1)
{
for(int i = 1; i <= m; ++i) printf("%d ", way[i]);
puts("");
return;
}
for(int i = start; i <= n; ++i)
{
way[u] = i;
dfs(u + 1, i + 1);
way[u] = 0; // 恢复现场
}
}
void dfs(int u)
{
// n 个数全部枚举完
if(u > n)
{
for(int i = 1; i <= n; ++i)
printf("%d ", state[i]);
puts("");
return;
}
for(int i = 1; i <= n; ++i)
{
// 如果 i 没有被枚举
if(!used[i])
{
state[u] = i;
used[i] = true;
dfs(u + 1); // 枚举下一位
used[i] = false; // 回溯
}
}
}
总结来说
- 指数型枚举 重点在 选或不选
- 组合型枚举 重点再 选哪些
- 排列行枚举 重点在 选择没有没选过的
这三个问题中，排列型枚举最好理解，最难理解的是组合型枚举。
对于排列来说，把 n 个数排列成不同的 n 个数，等价于我有 n 个带编号的空位，给 n 不同的，带编号的个小朋友排座的问题。我们可以按 每个数可以放在哪一位 来枚举，也可以按 每一位可以放那个数 来枚举。重要的是 顺序 。解决的方法往往是 回溯，回溯，就要记得 恢复现场。
组合型枚举中，要求从 n 个数中选 m 个，并且选出来的数不能重复（比如 2 1 3 和 1 2 3）。观察发现，重复在于这 m 个数的排列中的两个元素位置发生了交换。如果我们能相出一种办法不让它们交换，那这个问题就迎刃而解了。
对于这个问题来说，1 ~ n 是升序的，那么我们做出规定，下枚举下一个数时，一定要比当前这个数大。比如在枚举 1 后，下一位必须从 2 开始枚举。这样，上面的 2 1 3 这种情况就不会出现了。
下面我们可以应用我们学到的枚举策略来思考下面的问题：
我们依次看一下这两道题的核心代码：
1）
vector<vector<int>> permuteUnique(vector<int>& nums)
{
n = nums.size();
path.resize(n), st.resize(n, false);
sort(nums.begin(), nums.end());
dfs(nums, 0, 0);
return ans;
}
void dfs(vector<int>& nums, int u, int start)
{
if(u == n)
{
ans.push_back(path);
return;
}
// 枚举每个数组元素可以放在哪一位
for(int i = start; i < n; ++i)
{
if(!st[i])
{
st[i] = true;
path[i] = nums[u];
if(u + 1 < n && nums[u + 1] == nums[u]) dfs(nums, u + 1, i + 1);
else dfs(nums, u + 1, 0);
st[i] = false;
}
}
}
2）
vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
sort(nums.begin(), nums.end());
dfs(nums, 0);
return ans;
}
void dfs(vector<int>& nums, int u)
{
if(u == nums.size())
{
ans.push_back(path);
return;
}
int k = 0;
while(u + k < nums.size() && nums[u + k] == nums[u]) k++;
// 每个数有 [0, k] 种选择
for(int i = 0; i <= k; ++i)
{
// 向后走 k 位
dfs(nums, u + k);
path.push_back(nums[u]);
}
// 回溯
for(int i = 0 ; i <= k; ++i)
path.pop_back();
}
这一次的全排列枚举和指数型枚举都有了重复。
对于 1 2 2 的全排列，如果我们按照老办法得到的结果会有 1 2 2 和 1 2 2 。这是因为第一个 2 可以放在前面一次，也可以放在后面一次。 造成重复的关键就在于同样的数字可以在 第 2 位放多次。想到了这一点，解决办法就很简单了：对于每一位来说，相同的数字我们只搜索一次。
对于 1 2 2 的指数型排列，会有 2 ,2, 1 2, 1 2 等。对于每一个数来说，我们都有选或不选两种情况，所以对于第二位和第三位的 2 来说，我们都可以分别选一次。
其实，对于指数型枚举的选或不选我们可以说的再清晰一点，就是 选0个或选1个，这里的 1 是因为前面的问题最多只有 1 个相同的数。想到这里，这道题也就很简单了，对于同一个出现了 k 次的数，我们有 [0 ~ k] 这 k + 1 种选择方法。
2 DFS 求解精确覆盖问题
什么是精确覆盖问题？（我也不懂，google 吧
下面给出几道经典的精确覆盖问题：
八皇后问题很巧妙，具体的思路过程可以网上搜一下或者期待下日后我的博客讲解（也许不会更
这类问题最重要的就是 回溯
给出这两道题的核心代码：
1)
#include<cstdio>
using namespace std;
// 对角线最大值为 2n - 1
const int N = 20;
int n;
char g[N][N];
bool col[N], bg[N], ubg[N];
// u 是行号，我们按行枚举，确保行不会重复
void dfs(int u)
{
if(u == n)
{
for(int i = 0; i < n; ++i) puts(g[i]);
puts("");
return;
}
// 枚举列
for(int i = 0; i < n; ++i)
{
// u + i 为主对角线，n - i + u 为副对角线
// 主对角线的函数为：y = -x + b b = y + x
// 副对角线的函数为：y = x + b b = y - x
if(!col[i] && !bg[u + i] && !ubg[n - i + u])
{
col[i] = bg[u + i] = ubg[n - i + u] = true;
g[u][i] = 'Q';
dfs(u + 1);
g[u][i] = '.';
col[i] = bg[u + i] = ubg[n - i + u] = false;
}
}
}
int main(void)
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
g[i][j] = '.';
dfs(0);
return 0;
}
2)
class Solution {
public:
bool row[9][9] = {false}, col[9][9] = {false}, cells[3][3][9] = {false};
void solveSudoku(vector<vector<char>>& board)
{
for(int i = 0; i < 9; ++i)
for(int j = 0; j < 9; ++j)
if(board[i][j] != '.')
{
int k = board[i][j] - '1';
row[i][k] = col[j][k] = cells[i / 3][j / 3][k] = true;
}
dfs(board, 0, 0);
}
bool dfs(vector<vector<char>>& board, int x, int y)
{
if(y == 9) y = 0, x++;
if(x == 9) return true;
if(board[x][y] != '.') return dfs(board, x, y + 1);
for(int i = 0; i < 9; ++i)
{
if(!row[x][i] && !col[y][i] && !cells[x / 3][y / 3][i])
{
board[x][y] = i + '1';
row[x][i] = col[y][i] = cells[x / 3][y / 3][i] = true;
if(dfs(board, x, y + 1)) return true;
row[x][i] = col[y][i] = cells[x / 3][y / 3][i] = false;
board[x][y] = '.';
}
}
return false;
}
};
精确覆盖问题都可以用一个叫 dancing links 的数据结构来优化，有奇效。
3 找到一个解问题
上面我们用 DFS 求解的问题多是找到所有解，我们也会遇到是否存在解（找到一个解）的问题。这类问题在写法上有一个套路就是：
if(dfs(...)) return true;
bla bla...
return false;
经典例题有这两道：
给出核心代码：
1)
class Solution
{
public:
vector<char> allows[10][10];
bool pyramidTransition(string bottom, vector<string>& allowed)
{
for(auto s : allowed)
{
int a = s[0] - 'A', b = s[1] - 'A';
allows[a][b].push_back(s[2]);
}
return dfs(bottom, "");
}
bool dfs(string& last, string now)
{
// 到达第一层，只有一个元素
if(last.size() == 1) return true;
// 向上一层
if(now.size() + 1 == last.size())
return dfs(now, "");
// 每一层的第 i 个数由下一层的 i 和 i + 1 决定
int fir = now.size(), sec = fir + 1;
char cfir = last[fir], csec = last[sec];
// 遍历组成 now 当前一位 的所有可能
for(auto c : allows[cfir - 'A'][csec - 'A'])
{
now += c;
if(dfs(last, now)) return true;
now.pop_back();
}
return false;
}
};
2)
class Solution {
public:
int n, m, len;
string word;
bool exist(vector<vector<char>>& board, string _word)
{
word = _word;
n = board.size(), m = board[0].size(), len = word.size();
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(dfs(board, i, j, 0))
return true;
return false;
}
bool dfs(vector<vector<char>>& board, int x, int y, int u)
{
if(board[x][y] != word[u]) return false;
if(u == len - 1) return true;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
board[x][y] = '*';
for(int i = 0; i < 4; ++i)
{
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;
if(dfs(board, a, b, u + 1)) return true;
}
board[x][y] = word[u];
return false;
}
};
4 剪枝
剪枝目前只遇到了一个经典问题：
class Solution {
public:
vector<bool> st;
int n;
bool makesquare(vector<int>& nums)
{
n = nums.size();
if(!n) return false;
st.resize(n);
// 如果和不能被 4 整除，直接返回 false
int sum = 0;
for(int i = 0; i < n; ++i)
sum += nums[i];
if(sum % 4) return false;
// 排序，从大到小枚举所有木棒
sort(nums.begin(), nums.end(), greater<int>());
return dfs(nums, 0, 0, sum / 4);
}
// u：当前枚举到哪一位 cur 当前长度，len 每一根木棒的长度
bool dfs(vector<int>& nums, int u, int cur, int len)
{
if(cur == len) u++, cur = 0;
if(u == 4) return true;
for(int i = 0; i < n; ++i)
{
if(!st[i] && cur + nums[i] <= len)
{
st[i] = true;
if(dfs(nums, u, cur + nums[i], len)) return true;
st[i] = false;
// 跳过所有和当前长度重复的
while(i + 1 < n && nums[i + 1] == nums[i]) i++;
// 如果凑边的第一根或最后一根火柴失败，则直接返回
if(!cur || cur + nums[i] == len) return false;
}
}
return false;
}
};
5 其他 DFS 问题
这两道 DFS 问题比较复杂代码可以参考 点击这里
二 BFS
BFS 问题长用来求解最短，最少 的问题。
BFS 相比 DFS 代码更加长，空间复杂度更高，但是往往都是套用模板的“傻瓜式做法”。唯一需要绕弯的地方就是如果将 状态的转移转化为距离 。
1 BFS 求解最短路径问题
模板题：
代码：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
#define x first
#define y second
const int N = 110;
typedef pair<int, int> PII;
int n, m;
int g[N][N], dict[N][N];
bool st[N][N];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void bfs(int a, int b)
{
PII q[N * N];
int hh = 0, tt = -1;
q[++tt] = {a, b};
st[a][b] = true;
dict[a][b] = 0;
while(hh <= tt)
{
PII t = q[hh++];
for(int i = 0; i < 4; ++i)
{
int r = t.x + dx[i], c = t.y + dy[i];
if(r < 0 || r >= n || c < 0 || c >= m) continue;
if(g[r][c] == 1 || st[r][c]) continue;
q[++tt] = {r, c};
st[r][c] = true;
dict[r][c] = dict[t.x][t.y] + 1;
if(r == n - 1 && c == m - 1)
{
printf("%d\n", dict[r][c]);
return;
}
}
}
}
int main(void)
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
scanf("%d", &g[i][j]);
bfs(0, 0);
return 0;
}
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 210;
int T, R, C;
char g[N][N]; // 地图
int dist[N][N];// 步数 -1 表示未入队
int bfs(PII Start, PII End)
{
queue<PII> q;
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
q.push(Start);
memset(dist, -1, sizeof dist);
dist[Start.x][Start.y] = 0; // 起点
while(q.size())
{
PII t = q.front();
q.pop();
for(int i = 0; i < 4; ++i)
{
int a = t.x + dx[i], b = t.y + dy[i];
if(a < 0 || a >= R || b < 0 || b >= C) continue;
if(dist[a][b] != -1) continue; // 被访问过
if(g[a][b] == '#') continue;
dist[a][b] = dist[t.x][t.y] + 1;
if(End == make_pair(a, b)) return dist[a][b];
q.push(make_pair(a, b));
}
}
return -1;
}
int main(void)
{
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &R, &C);
for(int i = 0; i < R; ++i) scanf("%s", g[i]);
PII Start, End;
// 寻找开始和结束位置
for(int i = 0; i < R; ++i)
{
for(int j = 0; j < C; ++j)
{
if(g[i][j] == 'S') Start = {i, j};
else if(g[i][j] == 'E') End = {i, j};
}
}
int distance = bfs(Start, End);
if(distance == -1) cout << "oop!" << endl;
else cout << distance << endl;
}
return 0;
}
一个进阶的版本是地图变为三维，思路完全一样：
2 变型题
第一道题如果直接对每个 1 BFS 是会超时的，正确的做法是对所有的 0 BFS 直到找完所有的 1
第二道题我们在 BFS 的同时记录岛屿和临海的岛屿的数量，最后比较是否相同来判断海岛是非会被淹没。
第三道题我们采取从边界向中心 BFS，从而判断那些 o 不会变为 x
3. 特殊的 dist 数组
第一题 d 记录的是从字符串 start 变化到 end 的过程中，每一个字符串是几步变化而来的。
unordered_map<string, int> d;
第二题，dist 记录的是 beginWord 可以一步变化到字典中的哪个一个字符串，最终变化到 endWord 的距离
unordered_map<string, int> dist;
第三题，dist 记录的是 0 需要多少个完全平方数的和可以变为 n
vector<int> dist(n + 1, INT_MAX);