[leetcode] 51. N-Queens (递归）

递归，经典的八皇后问题。

利用一位数组存储棋盘状态，索引表示行，值为-1表示空，否则表示列数。

对行进行搜索，对每一行的不同列数进行判断，如果可以摆放符合规则，则摆放，同时遍历下一行。

遍历过程中，若已经遍历了n行，则保存该状态。

Runtime: 4 ms, faster than 91.35% of C++ online submissions for N-Queens.

class Solution

{

  public:

    vector<vector<string>> res;

    vector<int> queen;

    int N;

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

    {

        queen = vector<int>(n, -);

        N = n;

        helper();

        return res;

    }

    void helper(int pi)

    {

        if (pi == N)

        {

            pushit();

            return;

        }

        for (int j = ; j < N; j++)

        {

            if (valid(pi, j))

            {

                queen[pi] = j;

                helper(pi + );

                queen[pi] = -;

            }

        }

    }

    bool valid(int pi, int pj)

    {

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

        {

            if (queen[i] == pj || abs(queen[i] - pj) == pi - i)

                return false;

        }

        return true;

    }

    void pushit()

    {

        vector<string> temp;

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

        {

            string str;

            for (int j = ; j < N; j++)

                str.push_back('.');

            str[queen[i]] = 'Q';

            temp.push_back(str);

        }

        res.push_back(temp);

    }

};

巴特西

[leetcode] 51. N-Queens (递归）

最新文章

热门文章