力扣 困难 52.N皇后II
文章目录
- 题目介绍
- 题解
题目介绍
题解
法一：返回51题N皇后List的长度
法二：
class Solution {
private int n, ans;
private boolean[] onPath, diag1, diag2;
public int totalNQueens(int n) {
this.n = n;
onPath = new boolean[n];
diag1 = new boolean[n * 2 - 1];
diag2 = new boolean[n * 2 - 1];
dfs(0);
return ans;
}
private void dfs(int r) {
if (r == n) {
ans++; // 找到一个合法方案
return;
}
for (int c = 0; c < n; c++) {
int rc = r - c + n - 1;
if (!onPath[c] && !diag1[r + c] && !diag2[rc]) {
onPath[c] = diag1[r + c] = diag2[rc] = true;
dfs(r + 1);
onPath[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场
}
}
}
}