首页 > 代码库 > LeetCode52 N-Queens II

LeetCode52 N-Queens II

题目:

Follow up for N-Queens problem.

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

技术分享

 

分析:

跟昨天的题目一样的思路也能做,不知道为什么叫follow-up,明天再来研究一下解法优化。

代码:

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

 

LeetCode52 N-Queens II