LeetCode問題解(105):N-Queens II
タイトル:
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
問題:
N-Queen Iとは一つの問題の二つの質問です.
C++版:
Java版:
Python版:
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
問題:
N-Queen Iとは一つの問題の二つの質問です.
C++版:
class Solution {
private:
int results = 0;
public:
int totalNQueens(int n) {
if(n == 0)
return results;
vector<int> location(n, -1);
trace(location, 0, n);
return results;
}
void trace(vector<int>& location, int level, int n) {
if(level == n) {
results++;
return;
}
for(int i = 0; i < n; i++) {
if(isValid(location, level, i)) {
location[level] = i;
trace(location, level + 1, n);
location[level] = -1;
}
}
}
bool isValid(vector<int>& location, int row, int col) {
for(int i = 0; i < row; i++) {
if(location[i] == col || abs(row - i) == abs(location[i] - col))
return false;
}
return true;
}
};
Java版:
public class Solution {
private int results = 0;
public int totalNQueens(int n) {
if(n == 0)
return results;
int[] location = new int[n];
for(int i = 0; i < n; i++)
location[i] = -1;
trace(location, n, 0);
return results;
}
private void trace(int[] location, int n, int level) {
if(level == n) {
results++;
return;
}
for(int i = 0; i < n; i++) {
if(isValid(location, level, i)) {
location[level] = i;
trace(location, n, level + 1);
location[level] = -1;
}
}
}
private boolean isValid(int[] location, int row, int col) {
for(int i = 0; i < row; i++) {
if(location[i] == col || Math.abs(row - i) == Math.abs(location[i] - col))
return false;
}
return true;
}
}
Python版:
class Solution:
# @return a list of lists of string
def totalNQueens(self, n):
#results = 0
if n == 0:
return 0
location = [-1 for i in range(n)]
results = [0]
def trace(location, n, level):
if level == n:
results[0] += 1
return
for i in range(n):
if isValid(location, level, i):
location[level] = i
trace(location, n, level+1)
location[level] = -1
def isValid(location, row, col):
for i in range(row):
if location[i] == col or abs(row - i) == abs(location[i] - col):
return False
return True
trace(location, n, 0)
return results[0]