【N-Queens】cpp

题目：

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[

 [".Q..",  // Solution 1

  "...Q",

  "Q...",

  "..Q."],

 ["..Q.",  // Solution 2

  "Q...",

  "...Q",

  ".Q.."]

]

代码：

class Solution {

public:

        static vector<vector<string> > solveNQueens(int n)

        {

            vector<vector<string> > ret;

            if ( n== ) return ret;

            vector<string> tmp;

            vector<bool> colUsed(n,false);

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

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

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

            return ret;

        }

        static void dfs(

            vector<vector<string> >& ret,

            vector<string>& tmp,

            int n,

            vector<bool>& colUsed,

            vector<bool>& diagUsed1,

            vector<bool>& diagUsed2 )

        {

            const int row = tmp.size();

            if ( row==n )

            {

                ret.push_back(tmp);

                return;

            }

            string curr(n,'.');

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

            {

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

                {

                    colUsed[col] = !colUsed[col];

                    diagUsed1[col+n--row] = !diagUsed1[col+n--row];

                    diagUsed2[col+row] = !diagUsed2[col+row];

                    curr[col] = 'Q';

                    tmp.push_back(curr);

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

                    tmp.pop_back();

                    curr[col] = '.';

                    diagUsed2[col+row] = !diagUsed2[col+row];

                    diagUsed1[col+n--row] = !diagUsed1[col+n--row];

                    colUsed[col] = !colUsed[col];

                }

            }

        }

};

tips：

深搜写法：

1. 找到一个解的条件是tmp的长度等于n

2. 在一列中遍历每个位置，是否能够放置Q，并继续dfs；返回结果后，回溯tmp之前的状态，继续dfs。

一开始遗漏了对角线也不能在有超过一个Q的条件，补上之后就AC了。

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

第二次过这道题，string(n, '.')一直写成了string('.', n)，改过来就AC了。

class Solution {

public:

        vector<vector<string> > solveNQueens(int n)

        {

            vector<vector<string> > ret;

            if ( n< ) return ret;

            vector<string> tmp;

            vector<bool> colUsed(n, false);

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

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

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

            return ret;

        }

        static void dfs(

            vector<vector<string> >& ret,

            vector<string>& tmp,

            int n,

            vector<bool>& colUsed,

            vector<bool>& r2l,

            vector<bool>& l2r)

        {

            if ( tmp.size()==n )

            {

                ret.push_back(tmp);

                return;

            }

            int r = tmp.size();

            string row(n, '.');

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

            {

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

                colUsed[i] = true;

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

                l2r[i+r] = true;

                row[i] = 'Q';

                tmp.push_back(row);

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

                tmp.pop_back();

                row[i] = '.';

                colUsed[i] = false;

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

                l2r[i+r] = false;

            }

        }

};

巴特西

【N-Queens】cpp

最新文章

热门文章