一. 题目描述
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
二. 题目分析
题目与N-Queens的方法基本相同,但比后者更为简单,因为题目只要求输出合适解的个数,不需要打印所有解,代码要比上一题简化很多。设一个全局变量,每遍历到底部一次就增1。
三. 示例代码
#include <iostream>
#include <vector>
using namespace std;
class Solution
{
public:
int totalNQueens(int n)
{
this->row = vector<int>(n, ); // 行信息
this->col = vector<int>(n, ); // 列信息
result = ;
dfs(, n, result); // 深搜
return result;
}
private:
int result; // 存放打印的结果
vector<int> row; // 记录每一行哪个下标是Q
vector<int> col; // 记录每一列是否已有Q
void dfs(int r, int n, int & result) // 遍历第r行,棋盘总共有n行
{
if (r == n) // 可遍历到棋盘底部,计数器加1
++result;
int i, j;
for (i = ; i < n; ++i)
{
if (col[i] == )
{
for (j = ; j < r; ++j)
if (abs(r - j) == abs(row[j] - i))
break;
if (j == r)
{
col[i] = ; // 标记第i列,已存在Q
row[j] = i; // 第j行的第i个元素放入Q
dfs(r + , n, result); // 遍历第r + 1行
col[i] = ;
row[j] = ;
}
}
}
}
};
四. 小结
N-Queens的后续题目N-Queens II,比前一题简化许多,因为只要求输出解的个数,不需要输出所有解的具体状况。