【N-Quens II】cpp

题目：

Follow up for N-Queens problem.

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

代码：

class Solution {

public:

        int totalNQueens(int n)

        {

            int ret = ;

            if ( n== ) return ret;

            vector<bool> colUsed(n,false), diagUsed1(*n-,false), diagUsed2(*n-,false);

            Solution::dfs(ret, , n, colUsed, diagUsed1, diagUsed2);

            return ret;

        }

        static void dfs( int &ret, int row, int n, vector<bool>& colUsed, vector<bool>& diagUsed1, vector<bool>& diagUsed2 )

        {

            if ( row==n ) { ret++; return; }

            for ( size_t col = ; col<n; ++col ){

                if ( !colUsed[col] && !diagUsed1[col+n--row] && !diagUsed2[col+row] )

                {

                    colUsed[col] = diagUsed1[col+n--row] = diagUsed2[col+row] = true;

                    Solution::dfs(ret, row+, n, colUsed, diagUsed1, diagUsed2);

                    diagUsed2[col+row] = diagUsed1[col+n--row] = colUsed[col] = false;

                }

            }

        }

};

tips：

如果还是用深搜的思路，这个N-Queens II要比N-Queens简单一些，可能是存在其他的高效解法。

===========================================

第二次过这道题，经过了N-Queens，这道题顺着dfs的思路就写下来了。

class Solution {

public:

        int totalNQueens(int n)

        {

            int ret = ;

            if ( n< ) return ret;

            vector<bool> colUsed(n, false);

            vector<bool> r2l(*n-, false);

            vector<bool> l2r(*n-, false);

            Solution::dfs(ret, n, , colUsed, r2l, l2r);

            return ret;

        }

        static void dfs(

            int& ret,

            int n,

            int index,

            vector<bool>& colUsed,

            vector<bool>& r2l,

            vector<bool>& l2r)

        {

            if ( index==n )

            {

                ret++;

                return;

            }

            for ( int i=; i<n; ++i )

            {

                if ( colUsed[i] || r2l[i-index+n-] || l2r[i+index] ) continue;

                colUsed[i] = true;

                r2l[i-index+n-] = true;

                l2r[i+index] = true;

                Solution::dfs(ret, n, index+, colUsed, r2l, l2r);

                colUsed[i] = false;

                r2l[i-index+n-] = false;

                l2r[i+index] = false;

            }

        }

};