2016年7月22日星期五

[LeetCode] #51 N-Queens


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;
    }
}


没有评论:

发表评论