DFS 综合练习第四课魔法王国的终极挑战——简化版 N 皇后这一课我们把前面学过的 DFS 知识全部串起来前面三课我们已经学会了第一课枚举所有可能学会了选择。第二课金币凑数、勇士爬台阶学会了记录方案、检查结果。第三课勇闯魔法地图学会了检查条件、避免走进死胡同。今天我们要挑战一个经典的算法问题——N 皇后问题。我们先不挑战 8×8 的大棋盘而是从简单的 4×4 棋盘开始。只要弄懂这道题将来再挑战更大的棋盘就有了基础一、故事开始四位皇后的魔法棋盘魔法王国举办了一场棋盘挑战赛。棋盘有 4 行、4 列需要放置 4 位皇后并且满足一个重要规则任何两位皇后都不能互相攻击。在国际象棋中皇后可以沿着横线、竖线和斜线移动。因此两位皇后不能处于同一行、同一列或同一条斜线上。我们把规则拆成三个孩子容易理解的要求规则一不能同行每一行只能放一位皇后。规则二不能同列已经有皇后的列不能再放另一位皇后。规则三不能同斜线两位皇后如果沿着斜线相连就会发生冲突。我们的任务是找出所有合法的摆放方案并统计一共有多少种。注意这道题不是让我们随便摆四位皇后而是要把所有符合规则的方案都找出来一个也不能漏二、先不写代码我们应该怎样思考还记得前面学过的“岔路口”吗每次来到一个岔路口我们都尝试不同的选择。这一次我们不再决定“选还是不选”而是来到第几行就决定这一行的皇后放在哪一列。比如第一行有 4 个选择假设第一位皇后放在第 1 行、第 1 列。接下来轮到第二行。第二行也有四个位置可以尝试但有些位置已经不合法了。第 1 列和第一位皇后同列不行第 2 列和第一位皇后在斜线上不行第 3 列没有同行、同列或斜线冲突可以继续尝试。第 4 列也没有冲突可以继续尝试。我们只沿着合法的选择继续往下探索。如果后来发现无论怎样摆都无法完成任务就退回上一行换一个位置。这就是 DFS 在这道题里的工作方式选择一个位置 → 检查是否合法 → 记录选择 → 继续下一行如果走不通就退回来换位置。三、给电脑准备一本“皇后位置记录本”如果我们每次都把棋盘画出来电脑会不会很累其实我们只需要用一个数组就能记录每位皇后的位置。int col[5];这里使用下标1、2、3、4表示第几行数组里的数字表示皇后所在的列。例如记录本就是第几行对应第几列。例如col[2] 4的意思就是第二行的皇后放在第四列。这样我们就不必保存整个棋盘只用几个数字就能记住摆放方案。四、最重要的一步怎样检查皇后是否合法假设我们正在给第row行摆放皇后。前面几行的皇后已经摆好了我们只需要检查它和前面每一位皇后有没有冲突。检查一是不是在同一列如果col[row] col[i]就说明当前皇后和第i行的皇后在同一列发生冲突。例如第 1 行在第 2 列第 3 行也想放在第 2 列。两位皇后在同一列所以不合法。检查二是不是在同一条斜线上这是本题最关键的知识点看下面这个例子我们用一个规律判断斜线两位皇后所在行的距离等于它们所在列的距离就在同一条斜线上。例如第一位皇后在第 1 行、第 2 列第二位皇后在第 3 行、第 4 列。行号相差 3-1 2列号相差 4-2 2。两个距离相等因此在同一条斜线上不能这样摆放。代码里可以这样判断if (row - i col[row] - col[i] || row - i col[i] - col[row]) { return false; }为了让代码更简洁我们也可以使用绝对值if (row - i abs(col[row] - col[i])) { return false; }这里的abs()是求绝对值。例如abs(-2)的结果是2。五、把 DFS 的五个动作串起来这道题里DFS 不再是一个陌生的东西而是我们熟悉的“岔路口探险”。其中剪枝可以理解为发现这条路已经不可能成功就不再浪费时间继续走。例如某位皇后已经和前面的皇后在同一列了就没必要再摆后面的皇后了。我们直接放弃这个选择换下一列。六、完整 C 参考程序接下来我们把刚才的想法变成代码。建议同学们自己先猜一猜每个函数负责什么再一起阅读。#include iostream #include cstdlib using namespace std; const int N 4; // col[row] 表示第 row 行的皇后所在的列 int col[N 1]; int cnt 0; // 检查当前行的皇后是否合法 bool check(int row) { for (int i 1; i row; i) { // 检查是否在同一列 if (col[row] col[i]) { return false; } // 检查是否在同一条斜线上 if (row - i abs(col[row] - col[i])) { return false; } } return true; } // 从第 row 行开始摆放皇后 void dfs(int row) { // 四行都摆好了找到一种完整方案 if (row N 1) { cnt; cout 方案 cnt ; for (int i 1; i N; i) { cout col[i] ; } cout endl; // 打印棋盘 for (int i 1; i N; i) { for (int j 1; j N; j) { if (col[i] j) { cout Q ; } else { cout . ; } } cout endl; } cout endl; return; } // 尝试把皇后放在当前行的每一列 for (int c 1; c N; c) { // 选择并记录位置 col[row] c; // 检查合法合法才继续搜索 if (check(row)) { dfs(row 1); } // 恢复记录尝试下一列 col[row] 0; } } int main() { dfs(1); cout 一共找到 cnt 种方案 endl; return 0; }七、逐步追踪电脑是怎样找到第一种方案的先看程序最开始的调用dfs(1);意思是从第一行开始摆放皇后。我们用一张表跟着电脑走一遍。当前行尝试位置检查结果下一步第 1 行第 1 列合法进入第 2 行第 2 行第 1 列同列冲突剪枝第 2 行第 2 列斜线冲突剪枝第 2 行第 3 列合法进入第 3 行第 3 行逐列尝试都无法完成返回第 2 行第 2 行第 4 列合法重新探索第 3 行这说明了一个重要道理第一行放在第 1 列并不代表后面一定有解。如果这一条路走不通DFS 就会回到前面的岔路口换一个选择。它不会因为前面已经花了时间就死守错误的方案。最终程序会找到两种合法方案。程序的主要输出如下方案 12 4 1 3 . Q . . . . . Q Q . . . . . Q . 方案 23 1 4 2 . . Q . Q . . . . . . Q . Q . . 一共找到 2 种方案这里用Q表示皇后用.表示空格。注意程序输出的是两种不同的合法摆法不是只找到两位皇后。八、最后把五个知识点讲透1. 选择for (int c 1; c N; c)每一行都尝试第 1、2、3、4 列。这就是 DFS 的岔路口。2. 记录col[row] c把当前皇后的位置记下来后面的皇后才能根据它检查冲突。3. 检查check(row)检查同列和同斜线。每次只需要检查当前皇后与前面几行的皇后。4. 剪枝if (check(row))只有合法的选择才能进入下一行。不合法的选择直接放弃不继续搜索。5. 恢复col[row] 0当前选择探索完毕后清除这一行的记录接着尝试下一列。否则之前的选择可能会影响后面的探索。九、课后练习试着自己当一回 DFS 探险家练习一理解数组如果col[3] 4代表什么A、第三列放了第四位皇后B、第三行的皇后放在第四列C、第四行的皇后放在第三列答案B。col[3] 表示第三行的皇后所在列。练习二理解剪枝如果当前皇后与前面某位皇后在同一列应该怎么办继续摆下一行把已经摆好的皇后全部删除放弃当前列尝试下一列答案C。当前选择不合法就放弃它尝试下一列。练习三理解恢复为什么尝试完一个位置后要执行col[row] 0清除当前行的旧记录方便尝试其他位置让程序马上结束把皇后移动到第 0 列答案A。恢复记录避免旧选择干扰后面的探索。十、这一课的记忆口诀每行选一列先记再检查合法往下走不合法就剪枝走完要恢复找到答案就记录。这就是 DFS 综合运用的完整过程。从子集、排列、组合到金币凑数、爬台阶再到网格、迷宫和 N 皇后我们一直在做同一件事尝试选择记录状态检查条件继续探索走不通就返回。同学们真正掌握了这个思路以后遇到新的搜索题就不只是背代码而是能够自己分析有哪些选择怎样判断合法什么时候继续什么时候返回这才是学习 DFS 最重要的收获。
DFS 综合练习第四课魔法王国的终极挑战——简化版 N 皇后这一课我们把前面学过的 DFS 知识全部串起来前面三课我们已经学会了第一课枚举所有可能学会了选择。第二课金币凑数、勇士爬台阶学会了记录方案、检查结果。第三课勇闯魔法地图学会了检查条件、避免走进死胡同。今天我们要挑战一个经典的算法问题——N 皇后问题。我们先不挑战 8×8 的大棋盘而是从简单的 4×4 棋盘开始。只要弄懂这道题将来再挑战更大的棋盘就有了基础一、故事开始四位皇后的魔法棋盘魔法王国举办了一场棋盘挑战赛。棋盘有 4 行、4 列需要放置 4 位皇后并且满足一个重要规则任何两位皇后都不能互相攻击。在国际象棋中皇后可以沿着横线、竖线和斜线移动。因此两位皇后不能处于同一行、同一列或同一条斜线上。我们把规则拆成三个孩子容易理解的要求规则一不能同行每一行只能放一位皇后。规则二不能同列已经有皇后的列不能再放另一位皇后。规则三不能同斜线两位皇后如果沿着斜线相连就会发生冲突。我们的任务是找出所有合法的摆放方案并统计一共有多少种。注意这道题不是让我们随便摆四位皇后而是要把所有符合规则的方案都找出来一个也不能漏二、先不写代码我们应该怎样思考还记得前面学过的“岔路口”吗每次来到一个岔路口我们都尝试不同的选择。这一次我们不再决定“选还是不选”而是来到第几行就决定这一行的皇后放在哪一列。比如第一行有 4 个选择假设第一位皇后放在第 1 行、第 1 列。接下来轮到第二行。第二行也有四个位置可以尝试但有些位置已经不合法了。第 1 列和第一位皇后同列不行第 2 列和第一位皇后在斜线上不行第 3 列没有同行、同列或斜线冲突可以继续尝试。第 4 列也没有冲突可以继续尝试。我们只沿着合法的选择继续往下探索。如果后来发现无论怎样摆都无法完成任务就退回上一行换一个位置。这就是 DFS 在这道题里的工作方式选择一个位置 → 检查是否合法 → 记录选择 → 继续下一行如果走不通就退回来换位置。三、给电脑准备一本“皇后位置记录本”如果我们每次都把棋盘画出来电脑会不会很累其实我们只需要用一个数组就能记录每位皇后的位置。int col[5];这里使用下标1、2、3、4表示第几行数组里的数字表示皇后所在的列。例如记录本就是第几行对应第几列。例如col[2] 4的意思就是第二行的皇后放在第四列。这样我们就不必保存整个棋盘只用几个数字就能记住摆放方案。四、最重要的一步怎样检查皇后是否合法假设我们正在给第row行摆放皇后。前面几行的皇后已经摆好了我们只需要检查它和前面每一位皇后有没有冲突。检查一是不是在同一列如果col[row] col[i]就说明当前皇后和第i行的皇后在同一列发生冲突。例如第 1 行在第 2 列第 3 行也想放在第 2 列。两位皇后在同一列所以不合法。检查二是不是在同一条斜线上这是本题最关键的知识点看下面这个例子我们用一个规律判断斜线两位皇后所在行的距离等于它们所在列的距离就在同一条斜线上。例如第一位皇后在第 1 行、第 2 列第二位皇后在第 3 行、第 4 列。行号相差 3-1 2列号相差 4-2 2。两个距离相等因此在同一条斜线上不能这样摆放。代码里可以这样判断if (row - i col[row] - col[i] || row - i col[i] - col[row]) { return false; }为了让代码更简洁我们也可以使用绝对值if (row - i abs(col[row] - col[i])) { return false; }这里的abs()是求绝对值。例如abs(-2)的结果是2。五、把 DFS 的五个动作串起来这道题里DFS 不再是一个陌生的东西而是我们熟悉的“岔路口探险”。其中剪枝可以理解为发现这条路已经不可能成功就不再浪费时间继续走。例如某位皇后已经和前面的皇后在同一列了就没必要再摆后面的皇后了。我们直接放弃这个选择换下一列。六、完整 C 参考程序接下来我们把刚才的想法变成代码。建议同学们自己先猜一猜每个函数负责什么再一起阅读。#include iostream #include cstdlib using namespace std; const int N 4; // col[row] 表示第 row 行的皇后所在的列 int col[N 1]; int cnt 0; // 检查当前行的皇后是否合法 bool check(int row) { for (int i 1; i row; i) { // 检查是否在同一列 if (col[row] col[i]) { return false; } // 检查是否在同一条斜线上 if (row - i abs(col[row] - col[i])) { return false; } } return true; } // 从第 row 行开始摆放皇后 void dfs(int row) { // 四行都摆好了找到一种完整方案 if (row N 1) { cnt; cout 方案 cnt ; for (int i 1; i N; i) { cout col[i] ; } cout endl; // 打印棋盘 for (int i 1; i N; i) { for (int j 1; j N; j) { if (col[i] j) { cout Q ; } else { cout . ; } } cout endl; } cout endl; return; } // 尝试把皇后放在当前行的每一列 for (int c 1; c N; c) { // 选择并记录位置 col[row] c; // 检查合法合法才继续搜索 if (check(row)) { dfs(row 1); } // 恢复记录尝试下一列 col[row] 0; } } int main() { dfs(1); cout 一共找到 cnt 种方案 endl; return 0; }七、逐步追踪电脑是怎样找到第一种方案的先看程序最开始的调用dfs(1);意思是从第一行开始摆放皇后。我们用一张表跟着电脑走一遍。当前行尝试位置检查结果下一步第 1 行第 1 列合法进入第 2 行第 2 行第 1 列同列冲突剪枝第 2 行第 2 列斜线冲突剪枝第 2 行第 3 列合法进入第 3 行第 3 行逐列尝试都无法完成返回第 2 行第 2 行第 4 列合法重新探索第 3 行这说明了一个重要道理第一行放在第 1 列并不代表后面一定有解。如果这一条路走不通DFS 就会回到前面的岔路口换一个选择。它不会因为前面已经花了时间就死守错误的方案。最终程序会找到两种合法方案。程序的主要输出如下方案 12 4 1 3 . Q . . . . . Q Q . . . . . Q . 方案 23 1 4 2 . . Q . Q . . . . . . Q . Q . . 一共找到 2 种方案这里用Q表示皇后用.表示空格。注意程序输出的是两种不同的合法摆法不是只找到两位皇后。八、最后把五个知识点讲透1. 选择for (int c 1; c N; c)每一行都尝试第 1、2、3、4 列。这就是 DFS 的岔路口。2. 记录col[row] c把当前皇后的位置记下来后面的皇后才能根据它检查冲突。3. 检查check(row)检查同列和同斜线。每次只需要检查当前皇后与前面几行的皇后。4. 剪枝if (check(row))只有合法的选择才能进入下一行。不合法的选择直接放弃不继续搜索。5. 恢复col[row] 0当前选择探索完毕后清除这一行的记录接着尝试下一列。否则之前的选择可能会影响后面的探索。九、课后练习试着自己当一回 DFS 探险家练习一理解数组如果col[3] 4代表什么A、第三列放了第四位皇后B、第三行的皇后放在第四列C、第四行的皇后放在第三列答案B。col[3] 表示第三行的皇后所在列。练习二理解剪枝如果当前皇后与前面某位皇后在同一列应该怎么办继续摆下一行把已经摆好的皇后全部删除放弃当前列尝试下一列答案C。当前选择不合法就放弃它尝试下一列。练习三理解恢复为什么尝试完一个位置后要执行col[row] 0清除当前行的旧记录方便尝试其他位置让程序马上结束把皇后移动到第 0 列答案A。恢复记录避免旧选择干扰后面的探索。十、这一课的记忆口诀每行选一列先记再检查合法往下走不合法就剪枝走完要恢复找到答案就记录。这就是 DFS 综合运用的完整过程。从子集、排列、组合到金币凑数、爬台阶再到网格、迷宫和 N 皇后我们一直在做同一件事尝试选择记录状态检查条件继续探索走不通就返回。同学们真正掌握了这个思路以后遇到新的搜索题就不只是背代码而是能够自己分析有哪些选择怎样判断合法什么时候继续什么时候返回这才是学习 DFS 最重要的收获。
（containerd cri-docker 做 container runtime）)
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
