题解 | #N皇后问题#
N皇后问题
https://www.nowcoder.com/practice/c76408782512486d91eea181107293b6
描述
N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。
数据范围: 1 \le n \le 91≤n≤9
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n!)O(n!)
例如当输入4时，对应的返回值为2，
对应的两种四皇后摆位如下图所示：
class Solution {
public:
/**
*
* @param n int整型 the n
* @return int整型
*/
int a[10];//保存第几行的皇后在哪，如a[6]=2表示第6行的皇后在第2列
int cnt = 0;//计数器
//判断该该位置能否插入皇后
bool check(int row, int i) {
for (int j = 1; j <= row; ++j) {
if (a[j] == i) return false;//同一列不行
if (a[j] + j == (row + i)) return false;//反斜线不行
if (a[j] - j == i - row) return false;//正斜线不行
}
return true;
}
//深度优先搜索
void dfs(int row,int n) {
//当行数超过n，则摆法数+1
if (row == n + 1) {
cnt++;
return;
}
//对当前行的每一列进行判断
for (int i = 1; i <= n; ++i) {
if (check(row, i)) {
a[row] = i;
dfs(row + 1,n);
a[row] = 0;
}
}
}
int Nqueen(int n) {
dfs(1,n);
return cnt;
}
};
#n皇后#
凡岛公司福利 613人发布
查看7道真题和解析