N-Queens II
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
solution:
#include <iostream> #include <iomanip> #include <list> using namespace std; //board is 0 for avaliable positons, 1 for the other int board[100][100]; int queenPos[100]; int N; int solutionNum = 0; void dfs(int k) { if(k == N) {//the last queen has been put properly solutionNum++; return; } for(int i = 0;i < N;i++) { //search for a postion for the current queen bool flag = true; if(board[i][k] == 0) { list<int> lastX, lastY; //this is a good postion for the k th column queen. queenPos[k] = i;//in the ith row, kth column //change the board state to mark its attark region. for(int j = 0;j < N;j++) { if(board[i][j] == 0) { board[i][j] = 1; lastX.push_back(i); lastY.push_back(j); // cout << i << " " << j << endl; } if(board[j][k] == 0) { board[j][k] = 1; lastX.push_back(j); lastY.push_back(k); //cout << j << " " << k << endl; } // if(i - j >= 0 && k - j >= 0 && board[i - j][k - j] == 0) { //left up lastX.push_back(i - j); lastY.push_back(k - j); board[i - j][k - j] = 1; //cout << i -j << " " << k - j << endl; } if(i - j >= 0 && k + j < N && board[i - j][k + j] == 0) { lastX.push_back(i - j); lastY.push_back(k + j); board[i - j][k + j] = 1; //cout << i -j << " " << k + j << endl; } if(i + j < N && k - j >= 0 && board[i + j][k - j] == 0) { lastX.push_back(i + j); lastY.push_back(k - j); board[i + j][k - j] = 1; // cout << i + j << " " << k - j << endl; } if(i + j < N && k + j < N && board[i + j][k + j] == 0) { lastX.push_back(i + j); lastY.push_back(k + j); board[i + j][k + j] = 1; // cout << i + j << " " << k + j << endl; } } //cout << "put the " << k << " queen at " << i << " size = " << lastX.size() << endl; dfs(k + 1); //cout << "size = " << lastX.size() << endl; //back to the previous state. int num = lastX.size(); for(int t = 0;t < num;t++) { int x = lastX.front(); lastX.pop_front(); int y = lastY.front(); lastY.pop_front(); board[x][y] = 0; // cout << x << " " << y << endl; } } else continue; } } //return the total number of distinct solutions for N-Queens problem. int totalNQueens(int n) { N = n; solutionNum = 0; for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) board[i][j] = 0; dfs(0); return solutionNum; } int main() { for(int i = 0;i < 100;i++) memset(board[i], 0, sizeof(int) * 100); memset(queenPos, 0, sizeof(int) * 100); for(int i = 1;i < 14;i++) { totalNQueens(i); cout << "solutionNum = " << solutionNum << endl << endl; } return 0; }
[LeetCode] N-Queens II,布布扣,bubuko.com
原文:http://www.cnblogs.com/changchengxiao/p/3825379.html