题目描述
n皇后问题
样例
n=4的情况
.Q..
...Q
Q...
..Q.
..Q.
Q...
...Q
.Q..
算法
(回溯) $O(n^n)$
从第0层搜到第n-1层, 我们先用一个数组col[i] 表示第i列是否被使用过.
同时还要判断两条斜线是否被使用过,用pie 和 la这两个unordered_map表示
比如(1, 2), (2,3) 在一条斜线上 我们发现 1-2 = 2-3,即pie[-1] = true
同时(2,4),(3,3) 在一条斜线上, 我们发现2+4 = 3+3, 即la[6] = true
时间复杂度分析:O(n^n)
C++ 代码
#include <iostream>
#include <cstring>
#include <unordered_map>
using namespace std;
int row[9];
bool col[9];
unordered_map<int, bool> pie, la;
void dfs (int n, int step){
if (step==n){
for (int i=0; i<n; i++){
for (int j=0; j<n; j++) {
if (row[i]==j) cout << 'Q';
else cout << '.';
}
cout << endl;
}
cout << endl;
return;
}
for (int i=0; i<n; i++)
{
if (!col[i] && pie.find(step-i)==pie.end() && la.find(i+step)==la.end() ) {
row[step] = i;
col[i] = true;
pie[step-i] = true;
la[i+step] = true;
dfs(n, step+1);
row[step] = -1;
col[i] = false;
pie.erase(step-i);
la.erase(i+step);
}
}
}
int main(){
int n;
cin >> n;
dfs(n, 0);
return 0;
}
老哥,问下,pie.find(step-i)==pie.end()这个pie.end()是啥情况
pie.find(step-i)==pie.end()你这段代码应该对应 “比如(1, 2), (2,3) 在一条斜线上 我们发现 1-2 = 2-3,即pie[-1] = true”这句话吧 但是还是没看大懂
在c++语法中的意思就是没找到的意思,也就是一撇,斜线的位置没有放置皇后
在一撇上的所有点 的 横纵坐标之差是一样的, 在一捺上的所有点的 横纵坐标之和一样的。 step对应当前垂直方向坐标,i对应水平方向坐标, 根据减后的差值是否在map里面出现判断这条斜线是否出现过
dalao,为啥col只要用数组,但是pie和la却要用unordered_map?
哈哈,我是为了方便处理负数。 因为做减法时可能小于0,你也可以取绝对值,这样就能用数组了
哦,谢谢