问题描述
Given an integer n, return the number of distinct solutions to the n-queens puzzle.
给你一个整数n
,请计算可以构成N
皇后棋盘的总数量。
举个例子:
Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
解法1
类似题:
思路一样,找到答案时直接ans++
即可。
来看下实现:
class Solution {
int ans = 0;
int N = 40;
char[][] g = new char[N][N];
boolean[] col = new boolean[N];
boolean[] dg = new boolean[N];
boolean[] udg = new boolean[N];
private void dfs(int r, int n){
if (r == n){
ans++;
return;
}
for (int c = 0; c < n; c++){
if (!col[c] && !dg[c + r] && !udg[c - r + n]){
g[r][c] = 'Q';
col[c] = true; dg[c + r] = true; udg[c - r + n] = true;
dfs(r + 1, n);
col[c] = false; dg[c + r] = false; udg[c - r + n] = false;
g[r][c] = '.';
}
}
}
public int totalNQueens(int n) {
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
g[i][j] = '.';
}
}
dfs(0, n);
return ans;
}
}
Enjoy it !
一位喜欢提问、尝试的程序员
(转载本站文章请注明作者和出处 姚屹晨-yaoyichen)