public class Solution {
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
if (n <= 0) {
return result;
}
helper(result, new ArrayList<Integer>(), n);
return result;
}
private void helper(List<List<String>> result, List<Integer> path, int n) {
if (path.size() == n) {
result.add(generateResult(path));
return;
}
for (int i = 0; i < n; i++) {
if (isValid(path, i)) {
path.add(i);
helper(result, path, n);
path.remove(path.size() - 1);
}
}
}
private List<String> generateResult(List<Integer> path) {
List<String> result = new ArrayList<String>();
for (int i = 0; i < path.size(); i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < path.size(); j++) {
if (j == path.get(i)) {
sb.append('Q');
} else {
sb.append('.');
}
}
result.add(new String(sb));
}
return result;
}
private boolean isValid(List<Integer> path, int pos) {
for (int i = 0; i < path.size(); i++) {
if (path.get(i) == pos || path.get(i) == pos - path.size() + i
|| path.get(i) == pos + path.size() - i) { // Attn!
return false;
}
}
return true;
}
}
2016年7月22日星期五
[LeetCode] #51 N-Queens
订阅:
博文评论 (Atom)
没有评论:
发表评论