文章目录
前言
一、DFS是什么？
二、例题，模板
1.AcWing842. 排列数字
本题分析
AC代码
2.AcWing 843. n-皇后问题
本题分析
AC代码
三、时间复杂度
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：DFS，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。
一、DFS是什么？
DFS即深度优先搜索，不同于BFS，DFS会一路走到头，然后再回溯，DFS可以搜到结果，但这个结果可能不是最优解，这个也是我们需要明确的.
二、例题，模板
1.AcWing842. 排列数字
本题链接：AcWing842. 排列数字
本博客给出本题截图：
本题分析
本题是按位填写
dfs(0);代表从第0位开始（即未开始）p数组中存的是每一位的值，s数组存的是该数是否已经填写过了，比如已经用过了i这个数，对应成代码就是s[i] = true;填写完数字之后要执行dfs(u + 1);，就是继续dfs下一位，最后记得要恢复现场s[i] = false
AC代码
#include <cstdio> using namespace std; const int N = 10; int p[N], n; bool s[N]; void dfs(int u) { if (u == n) { for (int i = 0; i < n; i ++ ) printf("%d ", p[i]); puts(""); } for (int i = 1; i <= n; i ++ ) { if (!s[i]) { s[i] = true; p[u] = i; dfs(u + 1); s[i] = false; } } } int main() { scanf ("%d", &n); dfs(0); return 0; }
2.AcWing 843. n-皇后问题
本题链接：AcWing 843. n-皇后问题
本博客给出本题截图：
本题分析
本题需要记录：行，列，对角线，反对角线是否有元素，故需要开4个bool数组
这里我们具体来说一下对角线和反对角线的表示方法：
首先来看一下我们建立的x和y轴：
再来看对角线：
再来看反对角线：
AC代码
#include <cstdio> using namespace std; const int N = 20; char g[N][N]; bool row[N], col[N], dg[N], udg[N]; int n; void dfs(int x, int y, int s) { if (y == n) x ++, y = 0; if (x == n) { if (s == n) { for (int i = 0; i < n; i ++ ) puts(g[i]); puts(""); } return; //这里注意需要加return，否则会一直dfs下去导致爆内存 } dfs(x, y + 1, s); if (!row[x] && !col[y] && !dg[x + y] && !udg[y - x + n]) { row[x] = col[y] = dg[x + y] = udg[y - x + n] = true; g[x][y] = 'Q'; dfs(x, y + 1, s + 1); row[x] = col[y] = dg[x + y] = udg[y - x + n] = false; g[x][y] = '.'; } } int main() { scanf("%d", &n); for (int i = 0; i < n; i ++ ) for (int j = 0; j < n; j ++ ) g[i][j] = '.'; dfs(0, 0, 0); return 0; }
三、时间复杂度
关于DFS算法的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
