Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode N-Queens II

Leetcode algorithms 第 52 题:N-Queens II。

题目

Follow up for N-Queens problem.

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

解答

同样是N皇后问题,不过这里只需要求所有解的总数,应该是更加简单,算法跟N-Queens 一题相同。

具体代码如下:

class Solution {
public:
    const static int mx = 10000;
    bool vsy[mx], vsd1[2*mx], vsd2[2*mx]; //列、主对角线、副对角线是否已有皇后
    
    int dfs(int x, int n)
    { //当前行数,N大小
        if (x == n) return 1;
        
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (!vsy[i] && !vsd1[x+i] && !vsd2[n+x-i-1]) //列及两条对角线均没有皇后
            {
                vsy[i] = vsd1[x+i] = vsd2[n+x-i-1] = true;
                cnt += dfs(x+1, n);
                vsy[i] = vsd1[x+i] = vsd2[n+x-i-1] = false; //回溯
            }
        }
        return cnt;
    }
    int totalNQueens(int n) {
        return dfs(0, n);
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论