ThinkChat🤖让你学习和工作更高效,注册即送10W Token,即刻开启你的AI之旅 广告
**一. 题目描述** 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, 0); // 行信息 this->col = vector<int>(n, 0); // 列信息 result = 0; dfs(0, 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 = 0; i < n; ++i) { if (col[i] == 0) { for (j = 0; j < r; ++j) if (abs(r - j) == abs(row[j] - i)) break; if (j == r) { col[i] = 1; // 标记第i列,已存在Q row[j] = i; // 第j行的第i个元素放入Q dfs(r + 1, n, result); // 遍历第r + 1行 col[i] = 0; row[j] = 0; } } } } }; ~~~ **四. 小结** N-Queens的后续题目N-Queens II,比前一题简化许多,因为只要求输出解的个数,不需要输出所有解的具体状况。