首页 > 其他 > 详细

52. N-Queens II

时间:2017-05-11 10:01:53      阅读:341      评论:0      收藏:0      [点我收藏+]

Problem statement:

Follow up for N-Queens problem.

Now, instead outputting board configurations, return the total number of distinct solutions.

技术分享

Solution:

Compare with 51. N-Queens, this problem wants the number of  possible solutions. It also belongs to DFS, however, it belongs to another DFS template.

The return value of DFS function should be an integer instead of void. In each level DFS, the return value should be the sum of lower level result. The return value of final result is the DFS result from 0.

class Solution {
public:
    int totalNQueens(int n) {
        vector<string> solu(n, string(n, 0));
        return NQueens(solu, 0, n, n);
    }
private:
    int NQueens(vector<string>& solu, int row, int col, int n){
        if(row == n){
            return 1;
        }
        int cnt = 0;
        for(int i = 0; i < col; i++){
            if(isvalid(solu, row, i, n)){
                solu[row][i] = Q;
                cnt += NQueens(solu, row + 1, col, n);
                solu[row][i] = .;
            }
        }
        return cnt;
    }
    bool isvalid(vector<string>& solu, int row, int col, int n){
        for(int i = row - 1, left = col - 1, right = col + 1; i >= 0; i--, left--, right++){
            if(solu[i][col] == Q || (left >= 0 && solu[i][left] == Q) || (right < n && solu[i][right] == Q)){
                return false;
            }
        }
        return true;
    }
};        

 

52. N-Queens II

原文:http://www.cnblogs.com/wdw828/p/6839358.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!