关于LeetCode上N皇后II的疑问

Question

class Solution {
private:
int res=0;
void backtrack(int row, vector& temp) {
if (row == temp.size()) {
res++;
return;
}
int n = temp[row].size();
for (int col = 0; col < n; col++) {
if (!vaild(temp, row, col)) {
continue;
}
temp[row][col] = ‘Q’;
backtrack(row + 1,temp);
temp[row][col] = ‘.’;
}
}
bool vaild(vector& temp, int row, int col) {
int n = temp.size();
for (int i = 0; i < n; i++) {
if (temp[i][col] == ‘Q’) {
return false;
}
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i–, j++) {
if (temp[i][j] == ‘Q’) {
return false;
}
}
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i–, j–) {
if (temp[i][j] == ‘Q’) {
return false;
}
}
}
return true;
}
public:
int totalNQueens(int n) {
vectortemp(n, string(n, ‘.’));
if (n == 0)return res;
backtrack(0, temp);
return res;
}
};
这是我提交的正确的代码，我觉得下面这个样例不能通过

Answer 1

提问者 我是笨笨蛋 2020-08-09 18:50:18

因为N皇后II的判定条件是只能走1步或N-1步，用我提交的代码的话，每一条直线上不能出现重复的皇后

• liuyubobobo #1

  你的意思是对于 n = 5，你的盘面也应该是一个解？

• 提问者 我是笨笨蛋 回复 liuyubobobo #2

  是的！

• liuyubobobo #3

  我明白了，你的意思是后面的注解：她横、竖、斜都可走一或 N-1 步，所以在 n = 5 的时候，皇后应该不能走两步三步四步？如果是这个问题，这个问题后面的注解是错误的。皇后可以走任意多步。

点开查看后面1条评论

Answer 2

liuyubobobo 2020-08-09 18:49:51

抱歉，我还是没有理解你的问题。N 皇后 II 问题是输入一个 n，输出这个 n 皇后问题解的个数。所以测试用例应该是一个数字 n，而不是一个盘面。

你画一个盘面，这个盘面什么意思？