1. 题目
2. 读题(需要重点注意的东西)
思路:全排列的思想,在每一行中,判断这列col、斜线dg,反斜线udg是否存放了queen,如果存放了,就不能再放了;否则可以放,然后将其对应的col、dg、udg都置为true,表示已经放了一个queen了。
3. 解法
---------------------------------------------------解法---------------------------------------------------
#include <iostream>
using namespace std;
const int N = 20;
// col列,dg斜线,udg反斜线
// g[N][N]用来存图
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
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 ++ )
if (!col[i] && !dg[u + i] && !udg[n + u - i]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n + u - i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n + u - i] = false; // 恢复现场
g[u][i] = '.';
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
g[i][j] = '.';
dfs(0);
return 0;
}
可能存在的问题
1. 递归思想
如果对上述代码中递归思想有不理解的同学,可以参考下文 **4. 可能有帮助的前置习题** 。
-
dg、udg下标怎么选择的?
最重要的就是理解,dg[ b ] ,对于每个点,算出来b相同的点,是在同一条斜线或者反斜线上的。b表示的是这条斜线或反斜线的截距。dg[ b ]、udg[ b ]表示一条对角线,其中 b 是截距;dg与udg数组表示:具有相同截距的点,在同一条对角线上
那么关键是这个 b 的值如何选择呢?
给定了这个点的 i 和 u,画图得到
因此,
1. 对于dg,可以算出b = u - i
因为可能存在负数,而数组下标不能是负数,因此给了一个偏移量n
最后得到 b = n + u - i;
3. 对于udg,b = u + i
对应在代码中为cpp if (!col[i] && !dg[u + i] && !udg[n + u - i])
4. 可能有帮助的前置习题
5. 所用到的数据结构与算法思想
6. 总结
dfs的应用之一,推荐在理解dfs的思想的基础上,好好的理解并掌握递归的思想。
看懂了,不过dg应该是b = u + i吧