[Leetcode] N-Queens II

男娘i 2021-12-03 07:27 197阅读 0赞

Follow up for N-Queens problem.

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

![8-queens.png][]

跟上一题一样，改下结果的显示方式。

1 class Solution {
     2 public:
     3     bool isValid(vector<string> &board, int x, int y) {
     4         for (int i = 0; i < x; ++i) {
     5             if (board[i][y] == 'Q') return false;
     6         }
     7         for (int i = 0; i < board.size(); ++i) {
     8             for (int j = 0; j < board.size(); ++j) {
     9                 if (i != x && j != y && i-j == x-y && board[i][j] == 'Q')
    10                     return false;
    11                 if (i != x && j != y && i+j == x+y && board[i][j] == 'Q')
    12                     return false;
    13             }
    14         }
    15         return true;
    16     }
    17     
    18     void solveHelper(int &res, vector<string> &board, int idx) {
    19         if (idx == board.size()) {
    20             ++res;
    21             return;
    22         }
    23         for (int i = 0; i < board.size(); ++i) {
    24             board[idx][i] = 'Q';
    25             if (isValid(board, idx, i)) {
    26                 solveHelper(res, board, idx + 1);
    27             }
    28             board[idx][i] = '.';
    29         }
    30     }
    31     
    32     int totalNQueens(int n) { 
    33         int res = 0;
    34         vector<string> board;
    35         string row;
    36         for (int i = 0; i < n; ++i) {
    37             row.push_back('.');
    38         }
    39         for (int i = 0; i < n; ++i) {
    40             board.push_back(row);
    41         }
    42         solveHelper(res, board, 0);
    43         return res;
    44     }
    45 };

转载于:https://www.cnblogs.com/easonliu/p/3672326.html

[8-queens.png]: http://www.leetcode.com/wp-content/uploads/2012/03/8-queens.png