[Leetcode] N-Queens II
7565 ワード
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
前の問題と同じように、結果の表示方法を変更します.
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 };