[LeetCode] 52. N-Queens II

轉自LeetCode

Follow up for N-Queens problem.

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

<Solution>

這題和 N-Queens 一模一樣，解法也是相同

差別在於這次只要計數就好，每找到一次解，就把 ans 加一，這樣就可以了

code 如下

	class Solution {
	public:
	int totalNQueens(int n) {
	int ans = 0;
	vector<int> state(n, -1);
	dfs(0, state, ans);
	return ans;
	}
	void dfs(const int &row, vector<int> &state, int &ans) {
	int n = state.size();
	//> find an answer, ending condition
	if(row == n) {
	++ans;
	return;
	}
	//> try possible answer
	for(int c = 0; c < n; c++) {
	if(isValid(row, c, state)) {
	state[row] = c;
	dfs(row+1, state, ans);
	state[row] = -1;
	}
	}
	}
	bool isValid(const int &row, const int &col, const vector<int> &state) {
	for(int r = 0; r < row; r++) {
	if(state[r] == col || abs(row - r) == abs(col - state[r])) {
	return false;
	}
	}
	return true;
	}
	};

view raw nQueensII.cpp hosted with ❤ by GitHub