leetcode52 N-Queens II

52. N-Queens II

Total Accepted: 41407 Total Submissions: 107148 Difficulty: Hard

Follow up for N-Queens problem.

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

AC代碼：

class Solution 
{
public:
    int row[105];  //記錄每一行皇後的位置

    bool issafe(const int &i, const int &j, const int &n)
    {
        for (int k = 1; k < i; ++k)
            if (j == row[k] || abs(i - k) == abs(j - row[k]))
                return false;
        return true;
    }

    void findPos(const int &i, const int &n, int &ans) //i表示已經放置到第i行，j表示皇後在第i行放置于j
    {
        for (int j = 1; j <= n; ++j)
        {
            if (i > n)
                return;
            if (issafe(i, j, n)) //判斷目前位置是否可以放皇後
            {
                if (i == n)     //皇後已放到最後一行，找到一種解法，ans + 1
                {
                    ++ans;
                    continue;
                }
                row[i] = j;
                findPos(i + 1, n, ans);
                row[i] = 0;
            }
        }
    }

    int totalNQueens(int n)
    {
        if (1 == n)
            return 1;
        int ans = 0;
        memset(row, 0, sizeof(row));
        for (int i = 1; i <= n; ++i)   //在第一行依次放置皇後
        {
            row[1] = i;
            findPos(2, n, ans);
        }
        return ans;
    }
};