[Leetcode] N-Queens II

Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
 
前の問題と同じように、結果の表示方法を変更します.

 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 };